Stacks & Queues: ADTs, Operations, Applications & Real-World Use

TAKEAWAYS:

• Stacks follow LIFO (Last-In-First-Out) and are used for undo operations, expression evaluation, and recursion.
• Queues follow FIFO (First-In-First-Out) and model real-world waiting systems like order processing (Daraz) or traffic queues.
• Circular queues and priority queues optimize memory and scheduling for specific use cases.
• Postfix evaluation and infix-to-postfix conversion rely on stack operations and operator precedence.
• Linked-list implementations of stacks/queues avoid resizing overhead but use extra memory for pointers.
• Time complexity of stack/queue operations is O(1) for push/pop/enqueue/dequeue (amortized for dynamic arrays).

---

Core Concepts: Stacks and Queues as ADTs

What is an Abstract Data Type (ADT)?

An ADT defines a data structure’s behavior (operations) without specifying its implementation (how it’s stored). For example:

• A stack ADT specifies push() and pop() but doesn’t say whether it uses an array or linked list.
• A queue ADT specifies enqueue() and dequeue() but hides the underlying data structure.

Why ADTs matter in exams:

• Questions often ask: "Why is a stack considered an ADT?" → Answer: Because it hides implementation details and exposes only essential operations.
• Visual analogy:

---

Stacks: LIFO Operations and Applications

Definition and Operations

A stack is a linear data structure that follows Last-In-First-Out (LIFO). Key operations:

Visualization: Stack Operations

![stack data structure](/media/00d8436dd8d922bdc281.png "A labelled diagram showing push/pop/peek operations on a stack of plates. (Image: User:Boivie, Public domain, via Wikimedia Commons)")

• Push: Adds to the top.
• Pop: Removes from the top.
• Peek: Looks at the top without removing.

---

Implementations: Arrays vs. Linked Lists

1. Array Implementation

• Pros: Fast access, cache-friendly.
• Cons: Fixed size (unless dynamic resizing is used), push() may require shifting elements.
• Example (C++):

  #include <iostream>
  using namespace std;
  
  const int MAX = 100;
  int stack[MAX];
  int top = -1; // Stack is empty initially
  
  void push(int x) {
      if (top == MAX - 1) cout << "Stack Overflow!" << endl;
      else stack[++top] = x;
  }
  
  int pop() {
      if (top == -1) { cout << "Stack Underflow!" << endl; return -1; }
      return stack[top--];
  }
  

  Trace for push(5), push(3), pop():

  Step	top	Stack (array indices)
  Init	-1	[ , , , ... ]
  Push 5	0	[5, , , ... ]
  Push 3	1	[5, 3, , ... ]
  Pop	0	[5, , , ... ] (returns 3)

2. Linked List Implementation

• Pros: Dynamic size, no resizing overhead.
• Cons: Extra memory for pointers.
• Example (C++):

  struct Node {
      int data;
      Node* next;
  };
  
  Node* top = NULL;
  
  void push(int x) {
      Node* newNode = new Node();
      newNode->data = x;
      newNode->next = top;
      top = newNode;
  }
  
  int pop() {
      if (top == NULL) { cout << "Stack Underflow!" << endl; return -1; }
      Node* temp = top;
      int val = temp->data;
      top = top->next;
      delete temp;
      return val;
  }
  

  Visualization: Linked List Stack After push(5), push(3)

---

Applications of Stacks

---

In the Real World

1. eSewa’s Transaction Processing

   • When you pay a bill via eSewa, the app uses a stack to validate the transaction steps:
     • Each step (e.g., "check balance," "deduct amount," "send confirmation") is pushed onto a stack.
     • If any step fails (e.g., insufficient balance), the stack is popped to revert previous steps (undo).
   • Worked Example: If you try to pay ₹500 but only have ₹300, eSewa’s stack rolls back all actions after detecting the error.

2. Pathao’s Ride Order Queue

   • Pathao uses a priority queue (a variant of queue) to assign drivers to rides:
     • Nearest available driver is dequeued first (FIFO-like but prioritized by distance).
     • If no driver is free, new orders wait in the queue until a driver becomes available.
   • Visualization: Pathao’s Driver Assignment Queue

3. Ncell’s Call Waiting System

   • When you’re on a call and another call comes in, Ncell uses a stack to handle the second call:
     • The new call is "pushed" into a waiting stack.
     • If you end the first call, the most recent (top of stack) call is "popped" and connected immediately.
   • Trace:
     • You’re on Call A → Call B comes in → stack = [A, B].
     • You end Call A → pop() connects Call B.

---

Postfix Evaluation and Infix-to-Postfix Conversion

Why Postfix?

• Postfix notation (e.g., 3 4 +) eliminates parentheses and operator precedence issues.
• Used in calculators (e.g., HP calculators) and compilers.

Algorithm: Infix to Postfix (Shunting-Yard)

Steps:

1. Initialize an empty stack for operators and an empty list for output.
2. For each token in infix expression:
   • If operand → add to output.
   • If operator:
     • While stack top has higher or equal precedence → pop to output.
     • Push current operator to stack.
   • If ( → push to stack.
   • If ) → pop from stack to output until ( is encountered.
3. Pop all remaining operators from stack to output.

Precedence Rules:

Example: Convert (A + B) * C - D to Postfix

Code Implementation (C++):

#include <stack>
#include <string>
#include <unordered_map>

int precedence(char op) {
    static unordered_map<char, int> prec = {{'+', 2}, {'-', 2}, {'*', 3}, {'/', 3}, {'^', 4}};
    return prec[op];
}

string infixToPostfix(string infix) {
    stack<char> opStack;
    string postfix;
    for (char c : infix) {
        if (isalnum(c)) postfix += c;
        else if (c == '(') opStack.push(c);
        else if (c == ')') {
            while (!opStack.empty() && opStack.top() != '(') {
                postfix += opStack.top();
                opStack.pop();
            }
            opStack.pop(); // Remove '('
        } else { // Operator
            while (!opStack.empty() && precedence(opStack.top()) >= precedence(c)) {
                postfix += opStack.top();
                opStack.pop();
            }
            opStack.push(c);
        }
    }
    while (!opStack.empty()) {
        postfix += opStack.top();
        opStack.pop();
    }
    return postfix;
}

Trace for (A + B) * C - D:

---

Evaluating Postfix Expressions

Algorithm:

1. Initialize an empty stack.
2. For each token in postfix expression:
   • If operand → push to stack.
   • If operator → pop top 2 operands, apply operator, push result.
3. Final result is the only item left in the stack.

Example: Evaluate 3 4 + 2 *

Code Implementation (C++):

#include <stack>
#include <string>
#include <cctype>

int evaluatePostfix(string postfix) {
    stack<int> valStack;
    for (char c : postfix) {
        if (isdigit(c)) valStack.push(c - '0');
        else {
            int b = valStack.top(); valStack.pop();
            int a = valStack.top(); valStack.pop();
            switch (c) {
                case '+': valStack.push(a + b); break;
                case '-': valStack.push(a - b); break;
                case '*': valStack.push(a * b); break;
                case '/': valStack.push(a / b); break;
            }
        }
    }
    return valStack.top();
}

Trace for 4 5 + 7 3 - 2 + * (Exam Question):

---

Queues: FIFO Operations and Variants

Definition and Operations

A queue follows First-In-First-Out (FIFO). Key operations:

Visualization: Queue Operations

![queue data structure](/media/da5f4ca2a0710524f301.png "A labelled diagram showing enqueue/dequeue operations on a line of people. (Image: This Image was created by User:Vegpuff. If you are using the, CC BY-SA 3.0, via Wikimedia Commons)")

---

Implementations: Arrays vs. Linked Lists

1. Array Implementation

• Problem: Fixed size → circular queue is used to reuse space.
• Example (Circular Queue):

  #include <iostream>
  using namespace std;
  
  const int MAX = 5;
  int queue[MAX];
  int front = -1, rear = -1;
  
  void enqueue(int x) {
      if ((rear + 1) % MAX == front) cout << "Queue Overflow!" << endl;
      else {
          if (front == -1) front = 0;
          rear = (rear + 1) % MAX;
          queue[rear] = x;
      }
  }
  
  int dequeue() {
      if (front == -1) { cout << "Queue Underflow!" << endl; return -1; }
      int val = queue[front];
      if (front == rear) front = rear = -1; // Queue becomes empty
      else front = (front + 1) % MAX;
      return val;
  }
  

  Trace for enqueue(1), enqueue(2), dequeue():

  Step	front	rear	Queue (indices)
  Init	-1	-1	[ , , , , ]
  Enqueue 1	0	0	[1, , , , ]
  Enqueue 2	0	1	[1, 2, , , ]
  Dequeue	1	1	[ , 2, , , ] (returns 1)

2. Linked List Implementation

• Pros: Dynamic size, no circular logic needed.
• Example (C++):

  struct Node {
      int data;
      Node* next;
  };
  
  Node* front = NULL, *rear = NULL;
  
  void enqueue(int x) {
      Node* newNode = new Node();
      newNode->data = x;
      newNode->next = NULL;
      if (rear == NULL) front = rear = newNode;
      else { rear->next = newNode; rear = newNode; }
  }
  
  int dequeue() {
      if (front == NULL) { cout << "Queue Underflow!" << endl; return -1; }
      Node* temp = front;
      int val = temp->data;
      front = front->next;
      if (front == NULL) rear = NULL;
      delete temp;
      return val;
  }
  

  Visualization: Linked List Queue After enqueue(1), enqueue(2)

---

Queue Variants

Example: Priority Queue (Ncell Call Handling)

• Calls are dequeued based on priority (e.g., VIP customers first).
• Visualization:

---

Applications of Queues

---

In the Real World (Queues)

1. Daraz’s Order Processing

   • When you place an order on Daraz, it enters a queue in the system:
     • Orders are processed FIFO (first order placed = first shipped).
     • If a seller is busy, your order waits in the queue until they pick it up.
   • Worked Example: If you order at 10:00 AM and the seller processes 2 orders before yours, your order ships at ~10:15 AM.

2. NTC’s Bus Route Scheduling

   • NTC buses follow a circular queue schedule:
     • Buses depart from the terminal in a fixed cycle (e.g., Bus 1 → Bus 2 → Bus 3 → repeat).
     • Passengers waiting at a stop see buses arrive in a predictable FIFO order.
   • Visualization: NTC Bus Circular Queue

     flowchart TD
       A["Terminal"] --> B["Bus 1\n10:00 AM"]
       B --> C["Bus 2\n10:15 AM"]
       C --> D["Bus 3\n10:30 AM"]
       D --> A

3. Khalti’s Transaction Queue

   • When you send money via Khalti, the transaction is added to a priority queue:
     • High-priority transactions (e.g., emergency payments) are processed first.
     • Normal transactions wait in the queue until their turn.
   • Trace:
     • You send ₹500 (priority: medium) → Queue: [Emergency ₹1000, Your ₹500].
     • Emergency transaction is dequeued first → Your ₹500 is processed next.

---

Stack vs. Queue: Comparison Table

---

Exam Tip: How to Score Full Marks

1. Define ADTs Clearly

   • For stack/queue questions, always start with:

     "A stack is an ADT that follows LIFO principle and supports push(), pop(), peek(), and isEmpty() operations. It hides the implementation details (e.g., array vs. linked list)."

2. Trace Algorithms Step-by-Step

   • For infix-to-postfix or postfix evaluation, show the stack/queue state after each operation in a table (like above). Examiners love this!
   • Example answer snippet:

     "After processing token B, the stack contains [+] and output is A B. The next token is ), so we pop + to output, resulting in A B +."

3. Link to Real-World Examples

   • Questions often ask for applications. Always give 2 examples (one local, one global) with clear explanations.
   • Example:

     "Stacks are used in eSewa for transaction validation (undo on failure) and in Pathao for ride assignment (priority queue)."

4. Code + Trace = High Marks

   • If asked to write an algorithm (e.g., push() or enqueue()), provide:
     • Pseudocode (or C++/Java code).
     • Trace table (show variables like top, front, rear).
   • Example trace header: | Step | Operation | Stack/Queue State | Output/Result |

5. Avoid Common Mistakes

   • ❌ "Stack uses FIFO." → ✅ "Stack uses LIFO."
   • ❌ Forgetting to handle ( and ) in infix-to-postfix.
   • ❌ Not updating front/rear correctly in circular queues.

6. For Postfix Evaluation

   • Always show the stack contents after each operation and highlight the final result.
   • Example answer:

     *"The postfix expression 3 4 + 2 * evaluates to 14. The stack operations are:

     1. Push 3 → [3]
     2. Push 4 → [3, 4]
     3. Pop 4, 3 → 3 + 4 = 7 → [7]
     4. Push 2 → [7, 2]
     5. Pop 2, 7 → 7 * 2 = 14 → [14] Final result: 14."*

---

Practice Questions (Exam-Style)

1. Define stack as an ADT and list four applications of stacks in real-world systems.

   Answer: A stack is an ADT with LIFO order supporting push(), pop(), peek(), and isEmpty(). Applications:

   • Undo operations (MS Word).
   • Expression evaluation (eSewa transaction validation).
   • Function call stack (recursion in programs).
   • Browser history (back/forward buttons).

2. Convert the infix expression A + B * (C - D) / E to postfix and show the stack status after each step.

   Answer: Postfix = A B C D - * E / + Stack Trace:

   Token	Stack	Output
   A	[]	A
   +	[+]	A
   B	[+]	A B
   *	[+, *]	A B
   (	[+, *, (]	A B
   C	[+, *, (]	A B C
   -	[+, *, (, -]	A B C
   D	[+, *, (, -]	A B C D
   )	[+, *]	A B C D -
   /	[+, *, /]	A B C D - *
   E	[+, *, /]	A B C D - * E
   End	[+, *]	A B C D - * E /
   	[]	A B C D - * E / +

3. Evaluate the postfix expression 5 1 2 + 4 * + 3 - using a stack.

   Answer: 14 Trace:

   Token	Stack	Operation
   5	[5]	Push 5
   1	[5, 1]	Push 1
   2	[5, 1, 2]	Push 2
   +	[5, 3]	1 + 2 = 3
   4	[5, 3, 4]	Push 4
   *	[5, 12]	3 * 4 = 12
   +	[17]	5 + 12 = 17
   3	[17, 3]	Push 3
   -	[14]	17 - 3 = 14

4. Differentiate between stack and queue with examples from Nepalese systems.

   Answer:

   Feature	Stack (LIFO)	Queue (FIFO)
   Example	eSewa transactions (undo on failure)	Daraz orders (first-order-first-ship)
   Analogy	Last bill paid is the first to undo.	First order placed is the first to ship.
   Use Case	Reversible actions.	Sequential processing.