Stacks and queues are the two simplest useful data structures, and almost everything harder is built on them. A stack serves data in last-in-first-out order; a queue serves it first-in-first-out. That one difference in discipline decides which one a problem needs, and examiners test that judgement constantly. Let us define both cleanly, implement them two ways, work a postfix evaluation by hand, and settle the circular-queue condition that trips people up.
Stack: LIFO and its two operations
A stack is a linear structure where insertion and deletion happen at the same end, called the top. The last element pushed is the first popped, which is why it is called LIFO, last in, first out. It has exactly two core operations, both O(1):
push(x) places x on top.
pop() removes and returns the top element.
A peek or top reads the top without removing it, and an isEmpty check guards against popping an empty stack (a stack underflow). Pushing onto a full fixed-size stack is a stack overflow, the origin of the term you know from crashes.
Queue: FIFO and its two ends
A queue inserts at one end, the rear, and removes from the other, the front. The first element enqueued is the first dequeued, so it is FIFO, first in, first out, exactly like a line at a counter. Its two operations are:
enqueue(x) adds x at the rear.
dequeue() removes and returns the front element.
Both are O(1) when the structure keeps front and rear pointers. Where a stack has one moving end, a queue has two, and that is the whole structural difference.
Array vs linked implementations
Both structures can be built on an array or a linked list, and the choice is a classic trade-off.
Array-based. Simple and cache-friendly, with O(1) operations, but the capacity is fixed. A stack keeps a single `top` index; a queue keeps `front` and `rear` indices. The catch for a plain array queue is that after many dequeues the front drifts rightward and the left of the array is wasted, which is exactly what the circular queue below fixes.
Linked-list-based. Grows and shrinks on demand, so there is no overflow until memory runs out, but every node costs a pointer and the allocations are not cache-friendly. A stack pushes and pops at the head in O(1); a queue keeps head (front) and tail (rear) pointers so both ends stay O(1).
The rule of thumb: use an array when you know a tight upper bound on size, and a linked list when you do not.
Stack applications: expression evaluation and function calls
The stack earns its keep in three places worth knowing cold.
Expression evaluation and conversion. Compilers convert infix expressions like `A + B * C` to postfix (`A B C * +`) using a stack to hold operators by precedence, then evaluate the postfix with a second stack. Postfix needs no brackets and no precedence rules at evaluation time, which is why machines prefer it.
Function calls. Every function call pushes an activation record (return address, parameters, locals) onto the program's call stack and pops it on return. Recursion is just this stack used to depth. A runaway recursion overflowing that stack is the literal stack overflow.
Backtracking and undo. Depth-first search, balanced-bracket checking, and undo features all use LIFO order to remember the most recent state first.
A worked postfix evaluation
Evaluate the postfix expression 5 6 2 + * 12 4 / -. Scan left to right: push operands, and on an operator pop the top two, apply it, and push the result.
Token | Action | Stack (bottom to top) |
|---|---|---|
5 | push 5 | 5 |
6 | push 6 | 5, 6 |
2 | push 2 | 5, 6, 2 |
+ | pop 2 and 6, push 6+2=8 | 5, 8 |
* | pop 8 and 5, push 5*8=40 | 40 |
12 | push 12 | 40, 12 |
4 | push 4 | 40, 12, 4 |
/ | pop 4 and 12, push 12/4=3 | 40, 3 |
- | pop 3 and 40, push 40-3=37 | 37 |
The single value left, 37, is the answer, matching the infix `5 * (6 + 2) - 12 / 4`. Note the operand order on subtraction and division: the second-popped value is the left operand. That ordering detail is a favourite trap.
Circular queue: the full and empty conditions
A circular queue treats the array as a ring, so when `rear` reaches the last index it wraps to index 0 and reuses the freed slots. Advancing a pointer becomes `rear = (rear + 1) % N` for capacity N. This solves the wasted-space problem of a plain array queue.
The subtlety is telling full from empty, because in both cases `front` and `rear` can point at the same neighbourhood. The standard fix sacrifices one slot so the two states are distinguishable:
Empty when `front == rear`.
Full when `(rear + 1) % N == front`.
Because one slot is always left unused as a sentinel, a size-N array holds at most N − 1 elements. The alternative is to keep an explicit count of elements, then full is `count == N` and empty is `count == 0`, which uses all N slots at the cost of one extra variable. Know both; GATE has asked for each.
Deques and priority queues
Two variants round out the topic.
Deque (double-ended queue) allows insertion and deletion at both ends, so it generalises both a stack and a queue. It is the backbone of sliding-window algorithms.
Priority queue dequeues not the oldest element but the one with the highest priority. It is usually built on a binary heap, giving O(log n) insert and extract, and it drives Dijkstra's shortest paths, Prim's minimum spanning tree, and Huffman coding. Do not confuse it with an ordinary FIFO queue; the ordering rule is different.
How stacks and queues are tested
GATE CS mixes conceptual and worked questions: evaluate a postfix expression or convert infix to postfix, state the full or empty condition of a circular queue, work out the maximum elements a circular queue of size N holds, or identify which structure a scenario needs (a stack for recursion and DFS, a queue for BFS and scheduling). Implementing a queue with two stacks, or a stack with two queues, is a recurring puzzle. KnowledgeGate's published bank carries over 230 questions on stacks and 160+ on queues, so the practice on these exact patterns is deep.
Placement interviews love these because they reveal whether you understand LIFO versus FIFO in practice: balanced parentheses, the next-greater-element problem, a min-stack in O(1), and level-order tree traversal with a queue are standard first-round questions.
The short version
A stack is LIFO with push and pop at one end; a queue is FIFO with enqueue at the rear and dequeue at the front. Build them on an array for a known size or a linked list for an unknown one. Master the three stack applications, hand-evaluate one postfix expression, and be able to write both the pointer-based and count-based circular-queue conditions from memory.
Use the Data Structures learn module as your solved-problem hub for the whole paper.
The natural next structure is the tree, where stacks and queues reappear as traversal engines. Our binary trees and binary search trees deep dive builds on exactly this.
For a GATE-depth sequence, GATE Guidance by Sanchit Sir is built for it, and placement aspirants can start from the CS Fundamentals category.
Hand-trace one postfix evaluation and one circular-queue wrap-around, and these two structures stop being trivia and become reliable marks.
