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. Both are O(1) at their working ends, both come in array and linked forms, and each hides one classic trap: for the stack it is operand order in postfix evaluation, for the queue the one slot a circular buffer has to sacrifice.
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
topindex; a queue keepsfrontandrearindices. 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 * Cto 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.
Queue applications: scheduling, buffering and BFS
Queues serve wherever arrival order is the fair order.
Scheduling. An operating system keeps runnable processes in a ready queue, and disk and printer requests wait their turn the same way.
Buffering. Keyboard input, network packets and a print spooler queue up while a slower consumer drains them, so nothing loses its place.
Breadth-first search. BFS enqueues each newly discovered neighbour, so it visits a graph level by level, and level-order tree traversal is the same algorithm on a tree.
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 matter as much as the base structures: one relaxes which end you may touch, the other changes which element leaves next.
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 question bank carries over 230 questions on stacks and 160+ on queues, so practice on these exact patterns is easy to find.
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.
