Tutorial: Working with Stacks in C

Avatar

By squashlabs, Last Updated: July 28, 2023

Tutorial: Working with Stacks in C

Introduction to Stacks in C

A stack is a fundamental data structure in computer science that follows the Last-In-First-Out (LIFO) principle. In C, a stack can be implemented using either an array or a linked list. It is primarily used for managing function calls, expression evaluation, and undo/redo operations.

To understand the concept of a stack, let’s consider an example of stacking plates. When you add a plate to the stack, it goes on top of the existing plates, and when you remove a plate, you take it from the top. Similarly, in C, a stack is an abstract data type that allows you to push (add) and pop (remove) elements only at one end, called the top of the stack.

Related Article: What is Test-Driven Development? (And How To Get It Right)

Stack Program in C: Implementation and Operations

To implement a stack in C, you can use an array or a linked list. Let’s start with implementing a stack using an array. Here’s a basic implementation of a stack structure in C:

#define MAX_SIZE 100

typedef struct {
    int arr[MAX_SIZE];
    int top;
} Stack;

void initialize(Stack* stack) {
    stack->top = -1;
}

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

int isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack* stack, int data) {
    if (isFull(stack)) {
        printf("Stack overflow\n");
        return;
    }
    stack->arr[++stack->top] = data;
}

int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return -1;
    }
    return stack->arr[stack->top--];
}

int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->arr[stack->top];
}

In this implementation, we define a stack structure with an array to hold the elements and a top variable to keep track of the top position. The initialize function initializes the stack, isEmpty checks if the stack is empty, isFull checks if the stack is full, push adds an element to the top of the stack, pop removes and returns the top element, and peek returns the top element without removing it.

Complexity of Using Stacks in C

The complexity of stack operations in C depends on the underlying data structure used for implementation. When implemented using an array, the time complexity of push and pop operations is O(1) since accessing elements in an array has constant time complexity. However, if the stack is implemented using a linked list, the time complexity of push and pop operations is still O(1) since inserting and deleting nodes at the head of a linked list also has constant time complexity.

The space complexity of a stack is determined by the number of elements it contains. In both array-based and linked list-based implementations, the space complexity is O(n), where n is the number of elements in the stack.

Error Handling in Stack Programs

Error handling is an important aspect of programming, including stack programs. One common error in stack programs is stack overflow, which occurs when trying to push an element onto a full stack. Another error is stack underflow, which happens when trying to pop an element from an empty stack.

To handle these errors, we added error messages to the push and pop functions in the previous stack implementation. When a stack overflow or underflow occurs, an error message is printed, and the function returns an appropriate value (-1 in this case) to indicate the error.

Related Article: 16 Amazing Python Libraries You Can Use Now

Code Snippet Ideas: Stack Operations in C

Here are a few code snippets that demonstrate various stack operations in C:

1. Pushing elements onto a stack:

Stack stack;
initialize(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);

2. Popping elements from a stack:

int item1 = pop(&stack);  // Pops and returns 30
int item2 = pop(&stack);  // Pops and returns 20

Code Snippet Ideas: Advanced Stack Techniques

Stacks can be used for more advanced techniques and algorithms. Here are a few code snippets that demonstrate advanced stack techniques in C:

1. Checking balanced parentheses using a stack:

int checkBalancedParentheses(const char* expression) {
    Stack stack;
    initialize(&stack);
    
    for (int i = 0; expression[i] != '\0'; i++) {
        if (expression[i] == '(') {
            push(&stack, '(');
        } else if (expression[i] == ')') {
            if (isEmpty(&stack)) {
                return 0;  // Unbalanced parentheses
            }
            pop(&stack);
        }
    }
    
    return isEmpty(&stack);  // Returns 1 if parentheses are balanced, 0 otherwise
}

2. Evaluating postfix expressions using a stack:

int evaluatePostfixExpression(const char* postfix) {
    Stack stack;
    initialize(&stack);
    
    for (int i = 0; postfix[i] != '\0'; i++) {
        if (isdigit(postfix[i])) {
            int operand = postfix[i] - '0';
            push(&stack, operand);
        } else {
            int operand2 = pop(&stack);
            int operand1 = pop(&stack);
            int result;
            
            switch (postfix[i]) {
                case '+':
                    result = operand1 + operand2;
                    break;
                case '-':
                    result = operand1 - operand2;
                    break;
                case '*':
                    result = operand1 * operand2;
                    break;
                case '/':
                    result = operand1 / operand2;
                    break;
            }
            
            push(&stack, result);
        }
    }
    
    return pop(&stack);
}

Code Snippet Ideas: Real World Examples of Stack Usage in C

Stacks have numerous real-world applications in C. Here are a few code snippets that demonstrate the usage of stacks in practical scenarios:

1. Undo/redo functionality in a text editor:

Stack undoStack;
Stack redoStack;
initialize(&undoStack);
initialize(&redoStack);

void performEditAction(const char* action) {
    // Perform the edit action
    // ...
    
    // Push the action onto the undo stack
    push(&undoStack, action);
    
    // Clear the redo stack
    while (!isEmpty(&redoStack)) {
        pop(&redoStack);
    }
}

void undo() {
    if (!isEmpty(&undoStack)) {
        const char* action = pop(&undoStack);
        
        // Undo the action
        // ...
        
        // Push the action onto the redo stack
        push(&redoStack, action);
    }
}

void redo() {
    if (!isEmpty(&redoStack)) {
        const char* action = pop(&redoStack);
        
        // Redo the action
        // ...
        
        // Push the action onto the undo stack
        push(&undoStack, action);
    }
}

2. Backtracking in maze solving algorithms:

typedef struct {
    int row;
    int col;
} Position;

int solveMaze(char maze[][MAX_SIZE], int numRows, int numCols) {
    Stack stack;
    initialize(&stack);
    
    Position start = {0, 0};
    push(&stack, start);
    
    while (!isEmpty(&stack)) {
        Position current = pop(&stack);
        int row = current.row;
        int col = current.col;
        
        if (row == numRows - 1 && col == numCols - 1) {
            return 1;  // Maze solved
        }
        
        if (maze[row][col] == ' ') {
            maze[row][col] = '.';  // Mark current position as visited
            
            // Push neighboring positions onto the stack
            if (row > 0 && maze[row - 1][col] != '#') {
                Position neighbor = {row - 1, col};
                push(&stack, neighbor);
            }
            if (row < numRows - 1 && maze[row + 1][col] != '#') {
                Position neighbor = {row + 1, col};
                push(&stack, neighbor);
            }
            if (col > 0 && maze[row][col - 1] != '#') {
                Position neighbor = {row, col - 1};
                push(&stack, neighbor);
            }
            if (col < numCols - 1 && maze[row][col + 1] != '#') {
                Position neighbor = {row, col + 1};
                push(&stack, neighbor);
            }
        }
    }
    
    return 0;  // Maze unsolvable
}

Related Article: Agile Shortfalls and What They Mean for Developers

Code Snippet Ideas: Best Practices for Working with Stacks in C

When working with stacks in C, there are some best practices to consider. Here are a few code snippets that demonstrate these best practices:

1. Use a macro to define the maximum size of the stack:

#define MAX_SIZE 100

2. Encapsulate the stack implementation in a separate module:

// stack.h
typedef struct {
    int arr[MAX_SIZE];
    int top;
} Stack;

void initialize(Stack* stack);
int isEmpty(Stack* stack);
int isFull(Stack* stack);
void push(Stack* stack, int data);
int pop(Stack* stack);
int peek(Stack* stack);

// stack.c
#include "stack.h"

void initialize(Stack* stack) {
    stack->top = -1;
}

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

int isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack* stack, int data) {
    if (isFull(stack)) {
        printf("Stack overflow\n");
        return;
    }
    stack->arr[++stack->top] = data;
}

int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return -1;
    }
    return stack->arr[stack->top--];
}

int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->arr[stack->top];
}

Code Snippet Ideas: Performance Considerations for Stack Programs

When designing and implementing stack programs in C, there are certain performance considerations to keep in mind. Here are a few code snippets that demonstrate these performance considerations:

1. Use a fixed-size stack if the maximum number of elements is known in advance:

#define MAX_SIZE 100
int arr[MAX_SIZE];
int top = -1;

2. Avoid unnecessary stack operations by checking for stack overflow and underflow conditions:

void push(int data) {
    if (top == MAX_SIZE - 1) {
        printf("Stack overflow\n");
        return;
    }
    arr[++top] = data;
}

int pop() {
    if (top == -1) {
        printf("Stack underflow\n");
        return -1;
    }
    return arr[top--];
}

Stack Program Using an Array in C

Here’s an example of a stack program using an array in C:

#include <stdio.h>

#define MAX_SIZE 100

typedef struct {
    int arr[MAX_SIZE];
    int top;
} Stack;

void initialize(Stack* stack) {
    stack->top = -1;
}

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

int isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack* stack, int data) {
    if (isFull(stack)) {
        printf("Stack overflow\n");
        return;
    }
    stack->arr[++stack->top] = data;
}

int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return -1;
    }
    return stack->arr[stack->top--];
}

int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->arr[stack->top];
}

int main() {
    Stack stack;
    initialize(&stack);
    
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    
    printf("Top element: %d\n", peek(&stack));
    
    printf("Popped element: %d\n", pop(&stack));
    printf("Popped element: %d\n", pop(&stack));
    
    printf("Top element: %d\n", peek(&stack));
    
    return 0;
}

This program initializes a stack, pushes three elements onto the stack, prints the top element, pops two elements from the stack, and prints the top element again.

Related Article: 24 influential books programmers should read

Linked Lists in C: An Alternative to Array-based Stacks

In addition to array-based stacks, linked lists can also be used to implement stacks in C. Linked lists provide dynamic memory allocation, allowing the stack size to be flexible. Here’s an example of a stack implementation using linked lists:

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* top;
} Stack;

void initialize(Stack* stack) {
    stack->top = NULL;
}

int isEmpty(Stack* stack) {
    return stack->top == NULL;
}

void push(Stack* stack, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = stack->top;
    stack->top = newNode;
}

int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return -1;
    }
    Node* temp = stack->top;
    int data = temp->data;
    stack->top = temp->next;
    free(temp);
    return data;
}

int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->top->data;
}

int main() {
    Stack stack;
    initialize(&stack);
    
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    
    printf("Top element: %d\n", peek(&stack));
    
    printf("Popped element: %d\n", pop(&stack));
    printf("Popped element: %d\n", pop(&stack));
    
    printf("Top element: %d\n", peek(&stack));
    
    return 0;
}

This program demonstrates a stack implementation using linked lists. It initializes a stack, pushes three elements onto the stack, prints the top element, pops two elements from the stack, and prints the top element again.

Use Cases with Code Examples: Stack Implementation in C

Stacks have a wide range of use cases in C. Here are a few examples:

1. Evaluating infix expressions:

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX_SIZE 100

typedef struct {
    char arr[MAX_SIZE];
    int top;
} Stack;

void initialize(Stack* stack) {
    stack->top = -1;
}

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

int isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack* stack, char data) {
    if (isFull(stack)) {
        printf("Stack overflow\n");
        return;
    }
    stack->arr[++stack->top] = data;
}

char pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return '\0';
    }
    return stack->arr[stack->top--];
}

char peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return '\0';
    }
    return stack->arr[stack->top];
}

int isOperator(char ch) {
    return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

int getPrecedence(char ch) {
    switch (ch) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
    }
    return -1;
}

void infixToPostfix(const char* infix, char* postfix) {
    Stack stack;
    initialize(&stack);
    int j = 0;
    
    for (int i = 0; infix[i] != '\0'; i++) {
        char ch = infix[i];
        
        if (isdigit(ch)) {
            postfix[j++] = ch;
        } else if (isOperator(ch)) {
            while (!isEmpty(&stack) && getPrecedence(ch) <= getPrecedence(peek(&stack))) {
                postfix[j++] = pop(&stack);
            }
            push(&stack, ch);
        } else if (ch == '(') {
            push(&stack, ch);
        } else if (ch == ')') {
            while (!isEmpty(&stack) && peek(&stack) != '(') {
                postfix[j++] = pop(&stack);
            }
            if (!isEmpty(&stack) && peek(&stack) == '(') {
                pop(&stack);
            }
        }
    }
    
    while (!isEmpty(&stack)) {
        postfix[j++] = pop(&stack);
    }
    
    postfix[j] = '\0';
}

int evaluatePostfix(const char* postfix) {
    Stack stack;
    initialize(&stack);
    
    for (int i = 0; postfix[i] != '\0'; i++) {
        char ch = postfix[i];
        
        if (isdigit(ch)) {
            push(&stack, ch - '0');
        } else if (isOperator(ch)) {
            int operand2 = pop(&stack);
            int operand1 = pop(&stack);
            int result;
            
            switch (ch) {
                case '+':
                    result = operand1 + operand2;
                    break;
                case '-':
                    result = operand1 - operand2;
                    break;
                case '*':
                    result = operand1 * operand2;
                    break;
                case '/':
                    result = operand1 / operand2;
                    break;
            }
            
            push(&stack, result);
        }
    }
    
    return pop(&stack);
}

int main() {
    char infix[100];
    char postfix[100];
    
    printf("Enter an infix expression: ");
    scanf("%s", infix);
    
    infixToPostfix(infix, postfix);
    
    printf("Postfix expression: %s\n", postfix);
    
    int result = evaluatePostfix(postfix);
    
    printf("Result: %d\n", result);
    
    return 0;
}

This program converts an infix expression to postfix notation and evaluates the postfix expression. It uses a stack to perform the conversion and evaluation.

2. Checking for balanced parentheses in an expression:

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 100

typedef struct {
    char arr[MAX_SIZE];
    int top;
} Stack;

void initialize(Stack* stack) {
    stack->top = -1;
}

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

int isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

void push(Stack* stack, char data) {
    if (isFull(stack)) {
        printf("Stack overflow\n");
        return;
    }
    stack->arr[++stack->top] = data;
}

char pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return '\0';
    }
    return stack->arr[stack->top--];
}

char peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return '\0';
    }
    return stack->arr[stack->top];
}

int isBalanced(const char* expression) {
    Stack stack;
    initialize(&stack);
    
    for (int i = 0; expression[i] != '\0'; i++) {
        char ch = expression[i];
        
        if (ch == '(' || ch == '[' || ch == '{') {
            push(&stack, ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (isEmpty(&stack)) {
                return 0;  // Unbalanced parentheses
            }
            char top = pop(&stack);
            
            if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) {
                return 0;  // Unbalanced parentheses
            }
        }
    }
    
    return isEmpty(&stack);  // Returns 1 if parentheses are balanced, 0 otherwise
}

int main() {
    char expression[100];
    
    printf("Enter an expression: ");
    scanf("%s", expression);
    
    if (isBalanced(expression)) {
        printf("Parentheses are balanced\n");
    } else {
        printf("Parentheses are unbalanced\n");
    }
    
    return 0;
}

This program checks whether the parentheses in an expression are balanced or not using a stack.

These code examples demonstrate various use cases of stack implementation in C. Stacks are versatile data structures that can be applied to solve a wide range of problems efficiently and effectively.

You May Also Like

What is Test-Driven Development? (And How To Get It Right)

Test-Driven Development, or TDD, is a software development approach that focuses on writing tests before writing the actual code. By following a set of steps, developers... read more

Agile Shortfalls and What They Mean for Developers

What is the best software development methodology to use? This question is the topic of hot debate during the project implementation stage. However, what you choose... read more

24 influential books programmers should read

The fast-paced world of programming demands that people remain up-to-date. In fact, getting ahead of the curve makes a programmer stand out in his professional field.... read more

The most common wastes of software development (and how to reduce them)

Software development is a complex endeavor that requires much time to be spent by a highly-skilled, knowledgeable, and educated team of people. Often, there are time... read more

Intro to Security as Code

Organizations need to adapt their thinking to protect their assets and those of their clients. This article explores how organizations can change their approach to... read more

The Path to Speed: How to Release Software to Production All Day, Every Day (Intro)

To shorten the time between idea creation and the software release date, many companies are turning to continuous delivery using automation. This article explores the... read more