Stack and Queue Implementation

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

Stack and Queue: the two simplest, most-used structures in all of programming

Your browser's back button and a printer's job queue are running these two structures right now.

📚 Stack (LIFO)

RuleLast In, First Out — like a stack of plates, you can only take from the top.

OperationsPush (add to top), Pop (remove from top), Peek (look at top without removing).

Real exampleYour browser's "back" button — the most recently visited page is the first one you go back to.

🎟️ Queue (FIFO)

RuleFirst In, First Out — like a real queue at a shop, whoever arrived first gets served first.

OperationsEnqueue (add to back), Dequeue (remove from front).

Circular queueWraps the back around to the front position once space frees up, avoiding wasted array space that a simple queue would leave behind.

💡 One-liner: "Why does a plain array-based queue waste space over time, and how does a circular queue fix it?" → Dequeuing from the front leaves unused space at the array's start; a circular queue wraps the "back" pointer around to reuse that freed space instead of leaving it empty forever.

Why a plain array queue is broken

Implement a queue with an array, a front index and a rear index, and a problem appears immediately.

SIZE = 5, linear implementation enqueue A, B, C front=0 rear=2 [A][B][C][ ][ ] dequeue, dequeue front=2 rear=2 [ ][ ][C][ ][ ] enqueue D, E front=2 rear=4 [ ][ ][C][D][E] enqueue F rear would be 5 → "QUEUE FULL" But the queue holds only 3 items in a 5-slot array. Slots 0 and 1 are free and unreachable.

The front index only ever moves forward, so the space it leaves behind is abandoned. A linear array queue reports itself full while sitting half empty — which is why real implementations use a circular queue.

The circular queue

One change fixes it: advance the indices modulo the array size, so they wrap around to the start instead of running off the end.

rear = (rear + 1) % SIZE front = (front + 1) % SIZE Continuing the trace above with SIZE = 5: ... front=2 rear=4 [ ][ ][C][D][E] enqueue F rear = (4 + 1) % 5 = 0 front=2 rear=0 [F][ ][C][D][E] Slot 0 is reused. Nothing is abandoned.

💡 The modulo is the entire algorithm. (4+1) % 5 = 0 is what makes the array behave as a ring — and writing rear = rear + 1 without it is the single commonest error in queue implementation questions.

The full-versus-empty ambiguity

The circular queue creates one subtlety, and questions target it directly.

When the queue is empty, front == rear. When it is completely full and rear has wrapped all the way round, front == rear again. The same test gives opposite answers, so the two states cannot be distinguished by the indices alone.

🔧 The two standard fixes

Keep a countTrack the number of items. Empty is count == 0, full is count == SIZE. Uses the whole array, at the cost of maintaining one extra variable.

Sacrifice one slotDeclare the queue full when (rear + 1) % SIZE == front, so rear never quite catches front. Simpler, but one slot is permanently wasted.

💡 If a question gives an array of size n and asks the maximum number of elements, the answer depends on which convention it states: n with a counter, n − 1 with the sacrificed slot. Say which you are assuming.

Why both structures are O(1)

Every stack and queue operation touches only the ends — push and pop at the top, enqueue at the rear and dequeue at the front. Nothing is searched and nothing is shifted, so all of them are O(1) regardless of how many items are stored.

💡 That is precisely why these structures are worth having. An ordinary array can do everything a queue does, but removing from the front costs O(n) because every remaining element shifts down. The queue's discipline — only ever touching the ends — is what buys the constant time.

Syllabus points

Stack operations (push, pop, peek)
Queue, circular queue operations

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.