How To Implement a Stack in C Programming

In computer science, a stack is an abstract data structure that follows the Last In, First Out (LIFO) principle. It is widely used in algorithm design and programming for tasks like evaluating expressions, managing function calls, and performing undo operations. This tutorial will guide users through implementing a stack in C using arrays, providing clear examples of common stack operations such as push, pop, and peek. By the end of this tutorial, users will understand how to efficiently manage stacks in C and apply this data structure in real-world scenarios.

What is a Stack in Programming?

A stack in programming is a collection of elements with two main operations:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the element from the top of the stack.

Other useful operations include:

• Peek: Retrieves the top element without removing it.
• isFull: Checks if the stack is full (in cases of fixed-size stacks).
• isEmpty: Checks if the stack is empty.

In this tutorial, a C implementation of the stack will be created using an array, covering the push, pop, and peek operations.

Stack Data Structure Overview

A stack follows a simple concept:

• Think of a stack like a stack of plates. You can only add (push) a plate at the top or remove (pop) the plate at the top. 
• The stack operates under the LIFO principle, meaning the last item added is the first one to be removed.

In C, stacks can be implemented using arrays or linked lists. This tutorial will focus on using an array-based implementation.

Why Use Stacks?

Stacks are used in various real-world applications, including:

• Function call management (recursive function calls are placed on the call stack).
• Expression evaluation (infix, postfix, and prefix expressions).
• Backtracking algorithms (for example, the depth-first search algorithm).

Stack Operations

• Push: Adds an element to the stack.
• Pop: Removes the topmost element.
• Peek: Looks at the topmost element without removing it.
• isFull: Checks if the stack has reached its maximum capacity.
• isEmpty: Checks if the stack is empty.

These operations will be explained and implemented step-by-step in the sections below.

Implementing a Stack Using Arrays

To implement stack operations effectively, it's important to start by setting up the underlying data structure. This will ensure that the stack can handle various operations like pushing and popping elements.

Defining the Stack Structure

In C, a stack can be represented using an array with fixed capacity. To manage the stack, you'll need to keep track of the current top element and define the size of the stack.

#include <stdio.h>
#include <stdlib.h>

#define MAX 5

// Stack structure definition
struct Stack {
    int items[MAX];  // Array to store stack elements
    int top;         // To track the top element
};

// Function to initialize the stack
void initStack(struct Stack* s) {
    s->top = -1;  // Set top to -1, meaning the stack is initially empty
}

Implementing the Push Operation

The push operation adds a new element to the top of the stack, provided the stack isn't full.

// Function to push an element to the stack
void push(struct Stack* s, int value) {
    if (s->top == MAX - 1) {
        printf("Stack is full. Cannot push %d\n", value);
    } else {
        s->top++;
        s->items[s->top] = value;
        printf("Pushed %d to stack\n", value);
    }
}

Implementing the Pop Operation

The pop operation removes and returns the topmost element of the stack. If the stack is empty, the pop operation should notify the user.

// Function to pop an element from the stack
int pop(struct Stack* s) {
    if (s->top == -1) {
        printf("Stack is empty. Cannot pop.\n");
        return -1;  // Return -1 as an indicator of error
    } else {
        int poppedValue = s->items[s->top];
        s->top--;
        printf("Popped %d from stack\n", poppedValue);
        return poppedValue;
    }
}

Implementing the Peek Operation

The peek operation returns the top element without removing it. It’s useful when you want to view the topmost element without modifying the stack.

// Function to peek at the top element of the stack
int peek(struct Stack* s) {
    if (s->top == -1) {
        printf("Stack is empty. No top element.\n");
        return -1;
    } else {
        printf("Top element is %d\n", s->items[s->top]);
        return s->items[s->top];
    }
}

Checking if the Stack is Full or Empty

For completeness, two utility functions, isFull and isEmpty, are often implemented to check the stack’s state.

// Function to check if the stack is full
int isFull(struct Stack* s) {
    return s->top == MAX - 1;
}

// Function to check if the stack is empty
int isEmpty(struct Stack* s) {
    return s->top == -1;
}

Example Code for Stack Implementation

Below is a complete example that demonstrates how to use the stack operations.

#include <stdio.h>
#include <stdlib.h>

#define MAX 5

// Stack structure definition
struct Stack {
    int items[MAX];
    int top;
};

// Function declarations
void initStack(struct Stack* s);
void push(struct Stack* s, int value);
int pop(struct Stack* s);
int peek(struct Stack* s);
int isFull(struct Stack* s);
int isEmpty(struct Stack* s);

int main() {
    struct Stack myStack;
    initStack(&myStack);

    push(&myStack, 10);
    push(&myStack, 20);
    push(&myStack, 30);
    peek(&myStack);
    pop(&myStack);
    peek(&myStack);

    return 0;
}

// Function definitions
void initStack(struct Stack* s) {
    s->top = -1;
}

void push(struct Stack* s, int value) {
    if (isFull(s)) {
        printf("Stack is full. Cannot push %d\n", value);
    } else {
        s->top++;
        s->items[s->top] = value;
        printf("Pushed %d to stack\n", value);
    }
}

int pop(struct Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty. Cannot pop.\n");
        return -1;
    } else {
        int poppedValue = s->items[s->top];
        s->top--;
        printf("Popped %d from stack\n", poppedValue);
        return poppedValue;
    }
}

int peek(struct Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty. No top element.\n");
        return -1;
    } else {
        printf("Top element is %d\n", s->items[s->top]);
        return s->items[s->top];
    }
}

int isFull(struct Stack* s) {
    return s->top == MAX - 1;
}

int isEmpty(struct Stack* s) {
    return s->top == -1;
}

Common Stack Use Cases

Stacks are employed in various areas in computer programming:

• Function Call Management: The call stack tracks function calls and returns.
• Expression Evaluation: Stacks are used in parsing algorithms like converting infix to postfix expressions.
• Undo Operations: In many applications, such as text editors, stacks manage the undo functionality.
• Backtracking Algorithms: Stacks are used in depth-first search (DFS) algorithms and puzzle-solving.

Conclusion

In this tutorial, the stack data structure was introduced, along with a step-by-step guide to implementing a stack in C. The tutorial covered how to define a stack using arrays, perform basic operations such as push, pop, and peek, and use utility functions to check if the stack is full or empty. Stacks are essential tools in programming, and mastering their use can significantly enhance one’s ability to write efficient and maintainable code.