Mastering Stacks and Queues: Data Structure Fundamentals

Posted on Jun 9, 2026 in Computer Engineering

1. What is a Stack?

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. Think of it like a stack of plates in a cafeteria: the last plate you place on top is the first one you take off.

2. Representation of a Stack

There are two primary ways to implement a stack in memory:

A. Array Representation (Static Allocation)

  • How it works: A fixed-size array is allocated, and a variable named top keeps track of the index of the topmost element.
  • Initial State: top = -1 (indicates the stack is empty).
  • Pros: Fast access time; easy to implement.
  • Cons: Fixed size. If the array is full and you try to add an item, it causes a Stack Overflow.

B. Linked List Representation (Dynamic Allocation)

  • How it works: Each element is a node containing data and a pointer to the next node. The top pointer points to the head of the linked list.
  • Initial State: top = NULL.
  • Pros: Dynamic sizing; it grows and shrinks as needed, so no fixed size limits.
  • Cons: Requires extra memory for pointers.

3. Algorithms for Push and Pop (Array-Based)

These are the fundamental operations of a stack. Here is the straightforward logic for both:

PUSH Algorithm (Inserting an element)

Before adding an element, you must always check if the stack is already full.

Procedure PUSH(Stack, MaxSize, top, item)
    1. If top == MaxSize - 1 then:
            Print "Stack Overflow"
            Exit
    2. Else:
            top = top + 1      // Move top up
            Stack[top] = item  // Insert item
    3. Exit

POP Algorithm (Removing an element)

Before removing an element, you must always check if the stack is already empty.

Procedure POP(Stack, top)
    1. If top == -1 then:
            Print "Stack Underflow"
            Exit
    2. Else:
            item = Stack[top]  // Access the top item
            top = top - 1      // Move top down
            Return item
    3. Exit

4. Application of Stack: Polish Notation

In mathematics, we usually write expressions in Infix notation (where the operator sits between operands, like A + B). Compilers find this format hard to parse because of brackets and operator precedence.

Stacks are used to convert expressions into Polish Notation (Prefix or Postfix), which does not require brackets.

  • Infix: A + B (Operator is in between)
  • Prefix (Polish Notation): + A B (Operator comes before)
  • Postfix (Reverse Polish Notation / RPN): A B + (Operator comes after)

5. Postfix Evaluation Algorithm

Compilers easily evaluate postfix expressions using a stack. The rule is simple: Scan left to right. Push operands to the stack. When you hit an operator, pop two operands, evaluate them, and push the result back.

The Logic

  1. Scan the postfix expression from left to right.
  2. If the symbol is an operand (a number like 5, 3), PUSH it onto the stack.
  3. If the symbol is an operator (like +, -, *, /):
    • Pop the top element (this is Operand 2).
    • Pop the next top element (this is Operand 1).
    • Evaluate: Result = Operand 1 Operand 2.
    • PUSH the result back onto the stack.
  4. Repeat until the end of the expression. The final remaining value in the stack is your answer.
Example: Evaluate 5 3 + 2 *
  • Scan 5 → Push 5 (Stack: [5])
  • Scan 3 → Push 3 (Stack: [5, 3])
  • Scan + → Pop 3, Pop 5. Compute 5 + 3 = 8. Push 8 (Stack: [8])
  • Scan 2 → Push 2 (Stack: [8, 2])
  • Scan * → Pop 2, Pop 8. Compute 8 * 2 = 16. Push 16 (Stack: [16])
  • Final Answer: 16

6. Infix to Postfix Conversion

Compilers use a stack to hold operators during this conversion, keeping track of operator precedence (e.g., * and / have higher priority than + and -).

Standard Algorithm Steps

  1. Scan the infix expression from left to right.
  2. If it’s an operand, add it directly to the output string.
  3. If it’s a left parenthesis (, push it onto the stack.
  4. If it’s a right parenthesis ), pop from the stack and add to the output until a ( is encountered. Pop and discard the (.
  5. If it’s an operator:
    • Pop operators from the stack to the output if they have higher or equal precedence than the current operator.
    • Then, push the current operator onto the stack.
  6. When the expression ends, pop all remaining operators from the stack to the output string.

7. Infix to Prefix Conversion

This is highly similar to postfix conversion, but with a clever shortcut twist.

The Shortcut Method

  1. Reverse the infix expression. (Treat ( as ) and vice-versa during reversal).
  2. Convert this reversed expression into Postfix using the standard stack algorithm above.
  3. Reverse the final postfix result. The outcome is your correct Prefix expression!

8. Recursion

Recursion happens when a function calls itself to solve a smaller instance of the same problem.

9. Introduction to Queues (The FIFO Principle)

Just like stacks, Queues are a fundamental linear data structure, but they work on a completely different principle. While a stack is Last-In-First-Out, a queue mimics a real-world line — like waiting in line for movie tickets.

A queue follows the FIFO (First In, First Out) principle. The element that enters first is the first one to leave. To manage this, a queue uses two pointers:

  • Front: Tracks the index where elements are removed (Deletion / Dequeue).
  • Rear: Tracks the index where elements are added (Insertion / Enqueue).

10. Types of Queues

A. Simple Queue (Linear Queue)

Insertion happens only at the Rear end, and deletion happens only at the Front end.

  • The major drawback: Once the Rear reaches the end of an array, you cannot insert new elements even if there is empty space at the front (caused by previous deletions).

B. Circular Queue

To fix the memory waste of a simple queue, the last position is connected back to the first position, forming a circle. If Rear reaches the end of the array, it wraps around to index 0 if space is available.

C. Double-Ended Queue (Deque)

A flexible queue where insertions and deletions can happen at both the Front and Rear ends. It can behave like both a stack and a queue.

D. Priority Queue

Elements are assigned a priority. Deletion doesn’t depend on who arrived first; instead, the element with the highest priority is processed first. If elements have the same priority, they are served in standard FIFO order.

11. Representation of Queues

Array Representation (Static)

A fixed-size array is allocated.

  • Initial State: Usually initialized with Front = -1 and Rear = -1.
  • Pros: Simple to implement; fast index access.
  • Cons: Fixed size; can cause Queue Overflow if the array fills up.

Linked List Representation (Dynamic)

Each element is a node containing data and a pointer to the next node. Front points to the first node of the list, and Rear points to the last node.

  • Initial State: Front = NULL and Rear = NULL.
  • Pros: Dynamic memory allocation — grows and shrinks as needed. No size limits.
  • Cons: Requires extra memory for storing pointers.

12. Algorithms for Simple Queue (Array-Based)

Insertion (Enqueue)

Procedure ENQUEUE_SIMPLE(Queue, MaxSize, Front, Rear, Item)
    1. If Rear == MaxSize - 1 then:
            Print "Queue Overflow"
            Exit
    2. If Front == -1 and Rear == -1 then:  // Inserting the very first element
            Front = 0
            Rear = 0
       Else:
            Rear = Rear + 1                 // Move Rear forward
    3. Queue[Rear] = Item                   // Insert the item
    4. Exit

Deletion (Dequeue)

Procedure DEQUEUE_SIMPLE(Queue, Front, Rear)
    1. If Front == -1 then:
            Print "Queue Underflow"
            Exit
    2. Item = Queue[Front]                  // Retrieve the front element
    3. If Front == Rear then:               // Queue had only one element, now empty
            Front = -1
            Rear = -1
       Else:
            Front = Front + 1               // Move Front forward
    4. Return Item
    5. Exit

13. Algorithms for Circular Queue (Array-Based)

In a circular queue, we use the modulo operator (%) to make pointers wrap around to 0 when they hit the end of the array. Let MaxSize be the size of the array.

Insertion (Enqueue)

Procedure ENQUEUE_CIRCULAR(Queue, MaxSize, Front, Rear, Item)
    1. If (Rear + 1) % MaxSize == Front then:
            Print "Queue Overflow"
            Exit
    2. If Front == -1 then:                 // Inserting the very first element
            Front = 0
            Rear = 0
       Else:
            Rear = (Rear + 1) % MaxSize      // Circular increment
    3. Queue[Rear] = Item
    4. Exit

Deletion (Dequeue)

Procedure DEQUEUE_CIRCULAR(Queue, MaxSize, Front, Rear)
    1. If Front == -1 then:
            Print "Queue Underflow"
            Exit
    2. Item = Queue[Front]
    3. If Front == Rear then:               // Queue is now empty
            Front = -1
            Rear = -1
       Else:
            Front = (Front + 1) % MaxSize    // Circular increment
    4. Return Item
    5. Exit