Module 3: Stack & Queue
1. Stack: Core Concepts & Operations
1.1 Definition and Properties
A Stack is a linear data structure that follows the LIFO (Last In First Out) principle. This means
that the element inserted last is the first one to be removed. Think of a stack of plates; you can
only add or remove plates from the top.
A stack utilizes a single pointer called TOP, which tracks the index/address of the topmost
element in the stack. Initially, when the stack is empty, TOP is set to -1 (in array representation) or
NULL (in linked list representation).
1.2 Fundamental Operations
• Push: Adds an element to the top of the stack. Before executing, a check for Stack Overflow
(stack is full) must be made.
• Pop: Removes and returns the top element of the stack. Before executing, a check for Stack
Underflow (stack is empty) must be made.
• Peek / Top: Returns the value of the top element without removing it.
• isEmpty: Checks whether the stack is empty (TOP == -1).
• isFull: Checks whether the array-based stack has reached maximum capacity (TOP == MAX -
1).
2. Stack Implementations
2.1 Array Implementation (Static allocation)
Fixed size allocation. Quick access but rigid boundary thresholds.
// Push Operation Logic
void push(int stack[], int item) {
if (top == MAX - 1) {
printf("Stack Overflow! Cannot insert %d\n", item);
} else {
top++;
stack[top] = item;
}
}
// Pop Operation Logic
int pop(int stack[]) {
if (top == -1) {
printf("Stack Underflow! Empty stack\n");
return -1;
} else {
int item = stack[top];
top--;
return item;
}
}
2.2 Linked List Implementation (Dynamic allocation)
The stack grows dynamically without overflow limits (unless heap memory runs out). Elements
are inserted and deleted exclusively at the HEAD of the linked list to ensure O(1) operational time
complexity. The HEAD pointer serves directly as the TOP pointer.
• Push: Insert a new node at the beginning of the list.
• Pop: Delete the node at the beginning of the list.
3. Applications of Stack
3.1 Arithmetic Expression Notations
Compilers evaluate arithmetic expressions written in distinct linear forms:
• Infix Notation: Operators are written in-between operands (e.g., A + B). Requires operator
precedence and parentheses to eliminate ambiguity.
• Postfix Notation (Reverse Polish): Operators are written after their operands (e.g., A B +).
No parentheses or precedence parsing needed at execution time.
• Prefix Notation (Polish): Operators are written before their operands (e.g., + A B).
3.2 Algorithm: Conversion of Infix to Postfix Using Stack
Precedence Rules: ^ (Highest) → *, / → +, - (Lowest).
Associativity: Left-to-right for basic operators, right-to-left for exponents (^).
1. Scan the Infix expression from left to right.
2. If the scanned character is an Operand, append it directly to the Postfix output
string.
3. If the scanned character is a '(', push it onto the stack.
4. If the scanned character is a ')', pop from stack and append to output until a '('
is encountered. Pop and discard the '('.
5. If the scanned character is an Operator:
- While stack is not empty and priority(stack[top]) >= priority(scanned_operator),
pop operators from stack to output.
- Push the scanned operator onto the stack.
6. Once the end of the infix expression is reached, pop remaining operators from
stack and append to output.
3.3 Algorithm: Postfix Expression Evaluation Using Stack
To evaluate a postfix expression (e.g., 5 3 + 2 *):
1. Scan the Postfix expression from left to right.
2. If the scanned element is an Operand, push its numeric value onto the stack.
3. If the scanned element is an Operator:
- Pop the top element (Operand 2).
- Pop the next top element (Operand 1).
- Evaluate: Result = Operand 1 [Operator] Operand 2.
- Push the Result back onto the stack.
4. After scanning the complete expression, the single value remaining in the stack is
the final evaluated answer.
4. Queues: Core Concepts & Representations
4.1 Definition and Properties
A Queue is a linear data structure working on the FIFO (First In First Out) principle. The first
item added to the structure is always the first item removed. Examples include printing lines or a
customer queue at a counter.
Queues maintain two independent pointers:
• FRONT: Tracks the index of the element to be deleted/dequeued.
• REAR: Tracks the index of the last inserted element/enqueue point.
4.2 Linear Queue Memory Representations
Initially, FRONT = -1 and REAR = -1.
• Enqueue (Insertion): Increments REAR and adds the element at `REAR`. (If queue is empty,
both FRONT and REAR are set to 0). Worse-case check: REAR == MAX - 1 (Queue Full).
• Dequeue (Deletion): Extracts the element at FRONT and increments FRONT. If FRONT ==
REAR after deletion, the queue becomes empty, and both pointers reset to -1.
The Limitation of Linear Queues:
Even if elements are deleted from the front, REAR continues moving forward until REAR ==
MAX - 1. At this point, the queue reports "Queue Full" during an insertion attempt, even
though empty memory spaces exist at the front of the array. This is known as memory
wastage/false overflow.
5. Advanced Queue Variations
5.1 Circular Queue
To overcome the limitations of a linear queue, a Circular Queue connects the last memory index
back to the first index, conceptually forming a ring. Arithmetic updates rely on modulo
computations (% MAX).
• Circular Position Increment: Index = (Index + 1) % MAX
• Queue Full Condition: (REAR + 1) % MAX == FRONT
• Queue Empty Condition: FRONT == -1
// Circular Enqueue Logic
void enqueue(int cq[], int item) {
if ((rear + 1) % MAX == front) {
printf("Circular Queue Full!\n");
} else {
if (front == -1) front = 0; // First element setup
rear = (rear + 1) % MAX;
cq[rear] = item;
}
}
5.2 Double-Ended Queue (Deque)
A linear queue variation where insertions and deletions can happen at both ends (FRONT and
REAR). There are two specialized constraints on Deques:
• Input-Restricted Deque: Insertions are allowed only at one end (REAR), but deletions are
allowed at both ends (FRONT and REAR).
• Output-Restricted Deque: Deletions are allowed only at one end (FRONT), but insertions are
allowed at both ends (FRONT and REAR).
5.3 Priority Queue
A collection of elements where each element has an assigned priority metadata flag. Deletions do
not strictly follow arrival order; instead, processing occurs based on priority:
• Higher priority elements are processed and dequeued before lower priority elements.
• If two elements share identical priority scales, they are handled based on their sequential
FIFO arrival arrangement.