Extra 5% OFF Use Code: OL05
Free Shipping over ₹999

Stacks

by Mohd Azka
in Data Structure and Algorithm(DSA)
March 18, 2024

Stack

A stack is a fundamental data structure that follows the Last-In, First-Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. It operates on two main operations: push and pop.

Here’s an overview of stack operations:

  1. Push: Adds an element to the top of the stack.
  2. Pop: Removes the element from the top of the stack.
  3. Peek (or Top): Returns the element at the top of the stack without removing it.
  4. isEmpty: Checks if the stack is empty.
  5. isFull: Checks if the stack is full (for fixed-size stacks).

Stacks are commonly used in various computer science applications, including:

  • Function call management: Storing return addresses during function calls.
  • Expression evaluation and parsing: Evaluating expressions and parsing syntax.
  • Undo functionality in text editors and software: Storing previous states to enable undo operations.
  • Backtracking algorithms: Storing states to backtrack to previous decisions.
  • Memory management: Storing variables and function call information during program execution.

Stacks can be implemented using various underlying data structures, including arrays and linked lists. The choice of implementation depends on factors like memory constraints, performance requirements, and the specific application context.

Stack Implementation using Arrays

Reasons to implement stacks using arrays:

  • Memory Efficient: Array elements do not hold the next elements address like linked list nodes do.
  • Easier to implement and understand: Using arrays to implement stacks require less code than using linked lists, and for this reason it is typically easier to understand as well.

A reason for not using arrays to implement stacks:

  • Fixed size: An array occupies a fixed part of the memory. This means that it could take up more memory than needed, or if the array fills up, it cannot hold more elements.
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *stack;
    int top;
    int capacity;
} Stack;

Stack* createStack(int capacity) {
    Stack *newStack = (Stack*)malloc(sizeof(Stack));
    newStack->stack = (int*)malloc(capacity * sizeof(int));
    newStack->top = -1;
    newStack->capacity = capacity;
    return newStack;
}

void push(Stack *s, int element) {
    if (s->top == s->capacity - 1) {
        printf("Stack is full\n");
        return;
    }
    s->stack[++s->top] = element;
}

int pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->stack[s->top--];
}

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

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

int size(Stack *s) {
    return s->top + 1;
}

void printStack(Stack *s) {
    printf("Stack: ");
    for (int i = 0; i <= s->top; ++i) {
        printf("%c ", s->stack[i]);
    }
    printf("\n");
}

int main() {
    Stack *myStack = createStack(100);

    push(myStack, 'A');
    push(myStack, 'B');
    push(myStack, 'C');
    push(myStack, 'D');


    // Print initial stack
    printStack(myStack);

    printf("Pop: %c\n", pop(myStack));
    printf("Peek: %c\n", peek(myStack));
    printf("isEmpty: %d\n", isEmpty(myStack));
    printf("Size: %d\n", size(myStack));

    return 0;
}

Output:

Stack: A B C
Pop: D
Peek: C
isEmpty: 0
Size: 3

Code Explanation

1. Include Header Files

#include <stdio.h>
#include <stdlib.h>
  • stdio.h: Provides input/output functions like printf.
  • stdlib.h: Provides memory allocation functions like malloc.

2. Define the Stack Structure

typedef struct {
    int *stack;
    int top;
    int capacity;
} Stack;
  • A Stack structure is defined with three members:
    • stack: A pointer to an array that stores the stack elements.
    • top: An integer that tracks the index of the top element in the stack.
    • capacity: The maximum number of elements the stack can hold.

3. Function: createStack

Stack* createStack(int capacity) {
    Stack *newStack = (Stack*)malloc(sizeof(Stack));
    newStack->stack = (int*)malloc(capacity * sizeof(int));
    newStack->top = -1;
    newStack->capacity = capacity;
    return newStack;
}
  • Purpose: Creates a new stack with a specified capacity.
  • Parameters:
    • capacity: The maximum number of elements the stack can hold.
  • Steps:
    1. Allocate memory for the Stack structure.
    2. Allocate memory for the stack array.
    3. Initialize top to -1 (indicating an empty stack).
    4. Set the capacity of the stack.
    5. Return the newly created stack.

4. Function: push

void push(Stack *s, int element) {
    if (s->top == s->capacity - 1) {
        printf("Stack is full\n");
        return;
    }
    s->stack[++s->top] = element;
}
  • Purpose: Adds an element to the top of the stack.
  • Parameters:
    • s: A pointer to the stack.
    • element: The element to be added.
  • Steps:
    1. Check if the stack is full (top == capacity - 1).
      • If full, print “Stack is full” and return.
    2. Increment top and add the element to the stack.

5. Function: pop

int pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->stack[s->top--];
}
  • Purpose: Removes and returns the top element from the stack.
  • Parameters:
    • s: A pointer to the stack.
  • Steps:
    1. Check if the stack is empty (top == -1).
      • If empty, print “Stack is empty” and return -1.
    2. Return the top element and decrement top.

6. Function: peek

int peek(Stack *s) {
    if (s->top == -1) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->stack[s->top];
}
  • Purpose: Returns the top element of the stack without removing it.
  • Parameters:
    • s: A pointer to the stack.
  • Steps:
    1. Check if the stack is empty (top == -1).
      • If empty, print “Stack is empty” and return -1.
    2. Return the top element.

7. Function: isEmpty

int isEmpty(Stack *s) {
    return s->top == -1;
}
  • Purpose: Checks if the stack is empty.
  • Parameters:
    • s: A pointer to the stack.
  • Returns:
    • 1 if the stack is empty (top == -1).
    • 0 otherwise.

8. Function: size

int size(Stack *s) {
    return s->top + 1;
}
  • Purpose: Returns the number of elements in the stack.
  • Parameters:
    • s: A pointer to the stack.
  • Returns:
    • The number of elements (top + 1).

9. Function: printStack

void printStack(Stack *s) {
    printf("Stack: ");
    for (int i = 0; i <= s->top; ++i) {
        printf("%c ", s->stack[i]);
    }
    printf("\n");
}
  • Purpose: Prints all elements in the stack.
  • Parameters:
    • s: A pointer to the stack.
  • Steps:
    1. Iterate through the stack from index 0 to top.
    2. Print each element.

10. Main Function

int main() {
    Stack *myStack = createStack(100);
 
    push(myStack, 'A');
    push(myStack, 'B');
    push(myStack, 'C');
    push(myStack, 'D');
 
    // Print initial stack
    printStack(myStack);
 
    printf("Pop: %c\n", pop(myStack));
    printf("Peek: %c\n", peek(myStack));
    printf("isEmpty: %d\n", isEmpty(myStack));
    printf("Size: %d\n", size(myStack));
 
    return 0;
}
  • Steps:
    1. Create a stack with a capacity of 100.
    2. Push elements 'A', 'B', 'C', and 'D' onto the stack.
    3. Print the stack.
    4. Pop the top element and print it.
    5. Peek at the new top element and print it.
    6. Check if the stack is empty and print the result.
    7. Print the size of the stack.

Stack Implementation using Linked List

A reason for using linked lists to implement stacks:

  • Dynamic size: The stack can grow and shrink dynamically, unlike with arrays.

Reasons for not using linked lists to implement stacks:

  • Extra memory: Each stack element must contain the address to the next element (the next linked list node).
  • Readability: The code might be harder to read and write for some because it is longer and more complex.
#include <stdio.h>
#include <stdlib.h>

// Define a structure for the node
struct Node {
    int data;
    struct Node* next;
};

// Define a structure for the stack
struct Stack {
    struct Node* top;
};

// Function to initialize the stack
void initialize(struct Stack *stack) {
    stack->top = NULL; // Initialize top to NULL to indicate an empty stack
}

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

// Function to push an element onto the stack
void push(struct Stack *stack, int item) {
    // Create a new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    // Assign data to the new node
    newNode->data = item;
    // Set the next of the new node to the current top
    newNode->next = stack->top;
    // Move the top to point to the new node
    stack->top = newNode;
}

// Function to pop an element from the stack
int pop(struct Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow\n");
        return -1; // Return an error value
    }
    // Retrieve the item at the top of the stack
    int item = stack->top->data;
    // Store the current top node
    struct Node* temp = stack->top;
    // Move the top to the next node
    stack->top = stack->top->next;
    // Free the memory of the popped node
    free(temp);
    return item; // Return the popped item
}

// Function to peek at the top element of the stack
int peek(struct Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1; // Return an error value
    }
    return stack->top->data; // Return the item at the top of the stack
}

int main() {
    struct Stack stack;
    initialize(&stack);

    // Push elements onto the stack
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    // Print the top element of the stack
    printf("Top element of stack: %d\n", peek(&stack));

    // Pop elements from the stack and print them
    printf("Elements popped from stack:\n");
    while (!isEmpty(&stack)) {
        printf("%d\n", pop(&stack));
    }

    return 0;
}

Output:

Top element of stack: 30
Elements popped from stack:
30
20
10

Code explanation

1. Define the Node Structure

struct Node {
    int data;
    struct Node* next;
};
  • A Node structure is defined with two members:
    • data: Stores the integer value of the node.
    • next: A pointer to the next node in the linked list.

2. Define the Stack Structure

struct Stack {
    struct Node* top;
};
  • A Stack structure is defined with one member:
    • top: A pointer to the top node of the stack.

3. Function: initialize

void initialize(struct Stack *stack) {
    stack->top = NULL; // Initialize top to NULL to indicate an empty stack
}
  • Purpose: Initializes the stack by setting top to NULL.
  • Parameters:
    • stack: A pointer to the stack.

4. Function: isEmpty

int isEmpty(struct Stack *stack) {
    return (stack->top == NULL); // If top is NULL, stack is empty
}
  • Purpose: Checks if the stack is empty.
  • Parameters:
    • stack: A pointer to the stack.
  • Returns:
    • 1 if the stack is empty (top == NULL).
    • 0 otherwise.

5. Function: push

void push(struct Stack *stack, int item) {
    // Create a new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    // Assign data to the new node
    newNode->data = item;
    // Set the next of the new node to the current top
    newNode->next = stack->top;
    // Move the top to point to the new node
    stack->top = newNode;
}
  • Purpose: Adds an element to the top of the stack.
  • Parameters:
    • stack: A pointer to the stack.
    • item: The element to be added.
  • Steps:
    1. Allocate memory for a new node.
    2. Assign item to the data field of the new node.
    3. Set the next of the new node to the current top.
    4. Update top to point to the new node.

6. Function: pop

int pop(struct Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow\n");
        return -1; // Return an error value
    }
    // Retrieve the item at the top of the stack
    int item = stack->top->data;
    // Store the current top node
    struct Node* temp = stack->top;
    // Move the top to the next node
    stack->top = stack->top->next;
    // Free the memory of the popped node
    free(temp);
    return item; // Return the popped item
}
  • Purpose: Removes and returns the top element from the stack.
  • Parameters:
    • stack: A pointer to the stack.
  • Steps:
    1. Check if the stack is empty (top == NULL).
      • If empty, print “Stack Underflow” and return -1.
    2. Retrieve the data of the top node.
    3. Store the top node in a temporary pointer.
    4. Move top to the next node.
    5. Free the memory of the popped node.
    6. Return the retrieved data.

7. Function: peek

int peek(struct Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1; // Return an error value
    }
    return stack->top->data; // Return the item at the top of the stack
}
  • Purpose: Returns the top element of the stack without removing it.
  • Parameters:
    • stack: A pointer to the stack.
  • Steps:
    1. Check if the stack is empty (top == NULL).
      • If empty, print “Stack is empty” and return -1.
    2. Return the data of the top node.

8. Main Function

int main() {
    struct Stack stack;
    initialize(&stack);
 
    // Push elements onto the stack
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
 
    // Print the top element of the stack
    printf("Top element of stack: %d\n", peek(&stack));
 
    // Pop elements from the stack and print them
    printf("Elements popped from stack:\n");
    while (!isEmpty(&stack)) {
        printf("%d\n", pop(&stack));
    }
 
    return 0;
}
  • Steps:
    1. Initialize the stack.
    2. Push elements 10, 20, and 30 onto the stack.
    3. Print the top element of the stack (30).
    4. Pop all elements from the stack and print them (30, 20, 10).

    Leave a Reply

    Your email address will not be published.

    Need Help?
    OceanLabz © 2025 All rights reserved.
    Successfully added to your cart.