Stacks, queues and expression evaluation notes — Unit 3

A Stack is a linear data structure that follows a particular order in which operations are performed. The order is LIFO (Last In First Out) or FILO (First In Last Out).

A real-world analogy is a stack of plates in a cafeteria; you can only take the top plate, and if you add a new plate, it goes on top.

⇒1.1 Core Operations

• `Push`: Adds an item to the stack. If the stack is full, it results in an Overflow condition.
• `Pop`: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, it results in an Underflow condition.
• `Peek` or `Top`: Returns top element of stack.
• `isEmpty`: Returns true if stack is empty.

Stacks can be implemented using a static array. We use an integer variable `top` to keep track of the index of the top element. Initially, `top = -1`.

```c
#define MAX 100
int stack[MAX];
int top = -1;

void push(int data) {
if(top == MAX - 1) {
printf("Stack Overflow\n");
return;
}
stack[++top] = data;
}

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

Time Complexity: Push, Pop, and Peek are all $O(1)$.
Disadvantage: The size of the stack is fixed at compile-time (static).

To overcome the fixed-size limitation of array-based stacks, we can implement a stack using a singly linked list. The stack can grow dynamically.

⇒3.1 Concept

In a linked list implementation, the `head` pointer acts as the `top` of the stack.
- Pushing is equivalent to inserting a node at the beginning of the linked list.
- Popping is equivalent to deleting the first node of the linked list.

```c
void push(int data) {
struct Node newNode = (struct Node)malloc(sizeof(struct Node));
if(newNode == NULL) {
printf("Stack Overflow (Heap Full)\n");
return;
}
newNode->data = data;
newNode->next = top;
top = newNode;
}
```

Advantages: No arbitrary size limits. Only uses memory when needed.

Stacks are heavily used in systems programming and compilers.

• Function Call Stack: Managing function calls, passing parameters, and returning addresses in modern OS architectures.
• Undo/Redo Mechanisms: In text editors and software interfaces.
• Balanced Parentheses: Checking if mathematical or code brackets `{}, (), []` are balanced.
• Expression Evaluation and Conversion: Converting Infix to Postfix/Prefix and evaluating them.
• Browser History: The 'Back' button uses a stack of visited URLs.
• Tree/Graph Traversal: Used in Depth-First Search (DFS) iteratively.

Arithmetic expressions can be written in three forms, depending on the position of the operator relative to its operands.

⇒5.1 Infix Notation

Operator is placed between operands. Standard human-readable format. E.g., `A + B`.
Requires parentheses and precedence rules (BODMAS) to evaluate properly.

⇒5.2 Prefix Notation (Polish Notation)

Operator is placed before operands. E.g., `+ A B`.

⇒5.3 Postfix Notation (Reverse Polish Notation - RPN)

Operator is placed after operands. E.g., `A B +`.

Why use Prefix/Postfix? They do not require parentheses or operator precedence rules to evaluate. Computers evaluate them strictly left-to-right (or right-to-left) using a stack, making them much faster for machines to parse.

A classic algorithm using a stack to convert an expression. We maintain a string for the Postfix output and a Stack for operators.

⇒6.1 Algorithm Steps

• Scan the infix expression from left to right.
• If the scanned character is an operand, append it to the postfix output.
• If the scanned character is an '(', push it to the stack.
• If the scanned character is an ')', pop and output from the stack until an '(' is encountered. Discard the '(' and ')'.
• If the scanned character is an operator (`+`, `-`, ``, `/`, `^`): - While stack is not empty AND top of stack has greater than or equal* precedence than the scanned operator:
  - Pop and output.
  - Push the scanned operator to the stack.
• After scanning all characters, pop and output any remaining operators in the stack.

(Note: The power operator `^` is right-associative, so the rule changes slightly for it: pop only if precedence is strictly greater).

Once converted, evaluating a postfix expression is very straightforward for a computer using a single stack.

⇒7.1 Algorithm

• Scan the postfix expression from left to right.
• If the scanned character is an operand, push its value onto the stack.
• If the scanned character is an operator, pop two operands from the stack.
  - Let the first popped value be $B$ and the second be $A$.
  - Evaluate `A operator B`.
  - Push the result back onto the stack.
• When the expression ends, the final result is the only item left in the stack.

Example: Evaluate `2 3 5 +` 1. Push 2. Stack: `[2]` 2. Push 3. Stack: `[2, 3]` 3. Read ``. Pop 3, Pop 2. Evaluate $2 \times 3 = 6$. Push 6. Stack: `[6]`
4. Push 5. Stack: `[6, 5]`
5. Read `+`. Pop 5, Pop 6. Evaluate $6 + 5 = 11$. Push 11. Stack: `[11]`
Result: 11.

A Queue is a linear data structure that follows the FIFO (First In First Out) order. The first element added is the first one to be removed.

Real-world analogy: A line of people waiting at a ticket counter.

⇒8.1 Core Operations

• `Enqueue (Insert)`: Adds an item to the rear of the queue.
• `Dequeue (Delete)`: Removes an item from the front of the queue.
• `Front`: Returns the front element without removing it.
• `Rear`: Returns the rear element without removing it.

Unlike a stack where insertion and deletion occur at the same end (`top`), a queue requires two pointers: `front` (for deletion) and `rear` (for insertion).

In an array implementation, we initialize `front = -1` and `rear = -1`.

⇒9.1 Operations

• Enqueue: Check if `rear == MAX - 1`. If yes, Queue Overflow. Else, increment `rear` and add element.
• Dequeue: Check if `front == rear` (empty). Else, increment `front` and return the element. (Or return element at `front` then increment).

⇒9.2 The Major Drawback of Linear Array Queues

As we enqueue and dequeue elements, both the `front` and `rear` pointers move towards the end of the array. Eventually, `rear` reaches `MAX - 1`, causing an overflow error, even if there is empty space at the beginning of the array (because elements were dequeued).

This false overflow issue makes standard linear array queues highly inefficient in terms of memory utilisation.

To solve the false overflow problem of linear queues, we use a Circular Queue. The last position is logically connected back to the first position to make a circle.

⇒10.1 Mechanism (Modulo Arithmetic)

We use the modulo operator `%` to wrap the pointers around the array size `MAX`.

• Next position of Rear: `rear = (rear + 1) % MAX`
• Next position of Front: `front = (front + 1) % MAX`

⇒10.2 Overflow and Empty Conditions

• Queue Full: `(rear + 1) % MAX == front`
• Queue Empty: `front == -1` (Assuming we set them both to -1 when empty).

By treating the array circularly, memory space is fully utilised until the queue actually holds `MAX` concurrent elements.

A Deque (pronounced 'deck') is a generalised version of a queue where insertion and deletion can occur at both ends (front and rear).

⇒11.1 Types of Deque

• Input Restricted Deque: Insertion is allowed at only one end, but deletion is allowed at both ends.
• Output Restricted Deque: Deletion is allowed at only one end, but insertion is allowed at both ends.

⇒11.2 Deque as Stack and Queue

A deque can behave as both a Stack and a regular Queue.

A Priority Queue is a special type of queue in which each element is associated with a priority value. Elements are dequeued based on their priority, not their insertion order.

⇒12.1 Rules

• An element with high priority is dequeued before an element with low priority.
• If two elements have the same priority, they are served according to their order in the queue (FIFO).

⇒12.2 Implementation

While they can be implemented using arrays or linked lists (by keeping them sorted, or searching for the max element on every dequeue), the most efficient and standard way to implement a Priority Queue is using a Heap data structure (Min-Heap or Max-Heap).

Queues are used extensively in operating systems and network routing.

• CPU Scheduling: Round Robin scheduling uses a circular queue to allocate time slices to processes.
• Spooling in Printers: Print jobs are queued and processed in a FIFO manner.
• Breadth-First Search (BFS): Used in graph traversal to maintain the order of nodes to visit.
• Handling Asynchronous Data: Buffers in IO operations (like keyboard buffers, file IO).
• Interrupt Handling: OS hardware interrupts are queued based on priority (using Priority Queues).

Ensure you are ready for these exam and interview questions.

⇒14.1 University Exam Checklist

• Write C functions to implement a Stack using an array and a linked list.
• Convert a given Infix expression (e.g., `A * (B + C) / D`) to Postfix showing stack states.
• Write an algorithm to evaluate a Postfix expression.
• Explain the drawback of a linear queue and how a Circular Queue resolves it.
• Define Deque and its types.

⇒14.2 Placement Interview Focus

• Implement a Queue using two Stacks. (A classic interview question).
• Implement a Stack using two Queues.
• How would you design a stack that supports `push`, `pop`, and `getMin()` in $O(1)$ time?
• Given a string of parentheses `{[()]}`, write an algorithm using a stack to check if they are balanced.