📚 Stack

📖 Stack Overview

A stack is a linear data structure in which insertion and deletion happen at only one end, called the top.

Real-life examples

• A pile of plates.
• Undo operations in an editor.
• Function-call management using the runtime call stack.
• Expression conversion and evaluation.
• Backtracking algorithms.

⚙️ Basic Stack Operations

🧱 Stack Using Array

An array can store the stack elements, while an integer variable named top records the index of the current top element.

#define MAX 5

int stack[MAX];
int top = -1;

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Array Stack Visualizer Push multiple values, pop multiple elements, and watch TOP move with the stack

Initial stack (bottom → top)

Capacity

Operation Push Values Pop Multiple Peek

Values to push

  Prepare Operation

top = 2

← TOP pointer

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

Choose an operation and press Load Operation.

OperationPush

Elements3

Step1

⬆️ Push Operation

Push inserts a new value at the top of the stack. Before insertion, an array stack must check for overflow.

Algorithm

PUSH(value)

1. If top == MAX - 1
      report Stack Overflow
      stop

2. top = top + 1

3. stack[top] = value

⬇️ Pop Operation

Pop removes the current top element. Before removal, the stack must check for underflow.

Algorithm

POP()

1. If top == -1
      report Stack Underflow
      stop

2. value = stack[top]

3. top = top - 1

4. return value

👀 Peek Operation

Peek returns the top value without changing the stack.

Algorithm

PEEK()

1. If top == -1
      report Stack Empty
      stop

2. return stack[top]

💻 Array Stack Program in C

Visible Learning Program

#include <stdio.h>

#define MAX 5

int stack[MAX];
int top = -1;

void push(int value)
{
    if(top == MAX - 1)
    {
        printf("Overflow\n");
        return;
    }

    top++;
    stack[top] = value;
}

int pop()
{
    int value;

    if(top == -1)
        return -1;

    value = stack[top];
    top--;

    return value;
}

int peek()
{
    if(top == -1)
        return -1;

    return stack[top];
}

int main()
{
    push(10);
    push(20);
    push(30);

    printf("Popped: %d\n", pop());
    printf("Top: %d\n", peek());

    return 0;
}

Popped: 30
Top: 20

20  ← TOP
10

⚡ Time and Space Complexity

🔗 Stack Using Linked List

A stack can also be implemented using a singly linked list. In this implementation, the head node acts as TOP.

Node Structure

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

struct Node *top = NULL;

⚙️ Linked Stack Operations

Push Algorithm

PUSH(value)

1. Create newNode
2. newNode->data = value
3. newNode->next = top
4. top = newNode

Pop Algorithm

POP()

1. If top == NULL
      report Underflow
      stop

2. temp = top
3. value = temp->data
4. top = top->next
5. free(temp)
6. return value

Peek Algorithm

PEEK()

1. If top == NULL
      report Empty Stack
      stop

2. return top->data

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Linked List Stack Visualizer Push multiple values, pop multiple nodes, and watch the TOP pointer change

Initial stack (bottom → top)

Operation Push Values Pop Multiple Peek

Values to push

  Prepare Operation

top = N3

← TOP / head

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

Choose an operation and press Prepare Operation.

OperationPush Values

Nodes3

Step1

💻 Linked List Stack Program in C

Visible Learning Program

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

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

struct Node *top = NULL;

void push(int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

int pop()
{
    struct Node *temp;
    int value;

    if(top == NULL)
        return -1;

    temp = top;
    value = temp->data;

    top = top->next;
    free(temp);

    return value;
}

int peek()
{
    if(top == NULL)
        return -1;

    return top->data;
}

int main()
{
    push(10);
    push(20);
    push(30);

    printf("Popped: %d\n", pop());
    printf("Top: %d\n", peek());

    return 0;
}

Popped: 30
Top: 20

TOP → 20 → 10 → NULL

⚡ Linked List Stack Complexity

🧩 Parentheses Balancing Using Stack

A stack is commonly used to verify whether brackets in an expression are properly balanced. The important bracket pairs are (), {}, and [].

Algorithm

IS_BALANCED(expression)

1. Create an empty stack

2. For each character ch in expression:

      If ch is an opening bracket
            Push ch

      Else if ch is a closing bracket

            If stack is empty
                  return Not Balanced

            Pop top bracket

            If popped bracket does not match ch
                  return Not Balanced

3. If stack is empty
      return Balanced
   Else
      return Not Balanced

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Parentheses Balancing Visualizer Follow every character, stack Push/Pop, match, and final result

Expression

  Load Expression

Bracket Stack

Current Character: —

Action: Ready

TOP: —

Result: Pending

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

Load an expression and press Next.

💻 Parentheses Balancing Program in C

Visible Learning Program

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

int isMatching(char open, char close)
{
    return (open == '(' && close == ')') ||
           (open == '{' && close == '}') ||
           (open == '[' && close == ']');
}

int main()
{
    char expr[100];
    char stack[100];

    int top = -1;
    int balanced = 1;

    scanf("%99s", expr);

    for(int i = 0; expr[i] != '\0'; i++)
    {
        char ch = expr[i];

        if(ch == '(' || ch == '{' || ch == '[')
        {
            top++;
            stack[top] = ch;
        }
        else if(ch == ')' || ch == '}' || ch == ']')
        {
            if(top == -1)
            {
                balanced = 0;
                break;
            }

            if(!isMatching(stack[top], ch))
            {
                balanced = 0;
                break;
            }

            top--;
        }
    }

    if(top != -1)
        balanced = 0;

    if(balanced)
        printf("Balanced\n");
    else
        printf("Not Balanced\n");

    return 0;
}

{[()]}

Balanced

⚡ Parentheses Balancing Complexity

🔁 Infix to Postfix Conversion

In an infix expression, operators appear between operands, such as A+B*C. In a postfix expression, operators appear after their operands, such as ABC*+.

Operator Precedence

Algorithm

INFIX_TO_POSTFIX(expression)

1. Create an empty operator stack

2. Scan expression from left to right

3. If token is an operand
      append token to postfix

4. Else if token is '('
      push it

5. Else if token is ')'
      pop and append until '(' is found
      pop '(' and discard it

6. Else token is an operator
      while stack TOP contains an operator with
      higher precedence, or equal precedence
      for a left-associative operator:
            pop TOP and append it

      push current operator

7. After scanning the expression,
      pop all remaining operators to postfix

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Infix to Postfix Visualizer Watch operands move to output and operators move through the stack

Infix Expression

  Load Expression

Operator Stack

Postfix Output

—

Current Token: —

Action: Ready

TOP: —

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

Load an infix expression and press Next.

💻 Infix to Postfix Program in C

Visible Learning Program

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

int precedence(char op)
{
    if(op == '^')
        return 3;

    if(op == '*' || op == '/' || op == '%')
        return 2;

    if(op == '+' || op == '-')
        return 1;

    return 0;
}

int isRightAssociative(char op)
{
    return op == '^';
}

int main()
{
    char infix[100];
    char stack[100];
    char postfix[100];

    int top = -1;
    int k = 0;

    scanf("%99s", infix);

    for(int i = 0; infix[i] != '\0'; i++)
    {
        char ch = infix[i];

        if(isalnum((unsigned char)ch))
        {
            postfix[k++] = ch;
        }
        else if(ch == '(')
        {
            stack[++top] = ch;
        }
        else if(ch == ')')
        {
            while(top != -1 && stack[top] != '(')
                postfix[k++] = stack[top--];

            if(top != -1)
                top--;
        }
        else
        {
            while(top != -1 &&
                  stack[top] != '(' &&
                  (precedence(stack[top]) > precedence(ch) ||
                  (precedence(stack[top]) == precedence(ch) &&
                   !isRightAssociative(ch))))
            {
                postfix[k++] = stack[top--];
            }

            stack[++top] = ch;
        }
    }

    while(top != -1)
        postfix[k++] = stack[top--];

    postfix[k] = '\0';

    printf("%s\n", postfix);

    return 0;
}

A+B*(C-D)

ABCD-*+

⚡ Infix to Postfix Complexity

🧮 Postfix Expression Evaluation

A postfix expression places each operator after its operands. For example, 23* means 2 * 3. A stack evaluates postfix expressions naturally in one left-to-right scan.

Algorithm

EVALUATE_POSTFIX(expression)

1. Create an empty value stack

2. Scan postfix expression from left to right

3. If token is an operand
      push its numeric value

4. Else token is an operator
      b = pop()
      a = pop()

      result = a operator b

      push(result)

5. After scanning all tokens
      answer = pop()

6. The stack should now be empty

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Postfix Evaluation Visualizer Watch operands enter the stack and operators combine the top two values

Postfix Expression (single-digit operands)

  Load Expression

Value Stack

Current Token: —

First Operand (a): —

Second Operand (b): —

Operation: Ready

Current / Final Result

—

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

Load a postfix expression and press Next.

💻 Postfix Evaluation Program in C

Visible Learning Program

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

int main()
{
    char postfix[100];
    int stack[100];

    int top = -1;

    scanf("%99s", postfix);

    for(int i = 0; postfix[i] != '\0'; i++)
    {
        char ch = postfix[i];

        if(isdigit((unsigned char)ch))
        {
            stack[++top] = ch - '0';
        }
        else
        {
            int b = stack[top--];
            int a = stack[top--];
            int result = 0;

            switch(ch)
            {
                case '+':
                    result = a + b;
                    break;

                case '-':
                    result = a - b;
                    break;

                case '*':
                    result = a * b;
                    break;

                case '/':
                    result = a / b;
                    break;
            }

            stack[++top] = result;
        }
    }

    printf("%d\n", stack[top]);

    return 0;
}

23*54*+9-

17

⚡ Postfix Evaluation Complexity

❓ Common Stack Interview Questions

Review the most important Stack ADT, implementation, balancing, conversion, and evaluation questions.

🎯 20 Stack Practice Problems

Try every problem yourself first. Use 💻 Solve It Yourself to write and test your C program. Open Hint only when necessary, and use Show Program when you want to study the complete solution.