Stack vs Queue, step by step.

A stack and a queue both keep items in the order they arrive and differ in which one leaves first. A stack removes the newest: last in, first out (LIFO). A queue removes the oldest: first in, first out (FIFO). Both add and remove in O(1). Use a stack to undo and backtrack, a queue to serve in arrival order.

Below, both run the same six operations step by step, so you can see which values come out.

Stack vs queue: what differs

A stack and a queue on the same operations

Both players start empty on an array of six cells, as the app draws them, add 5, 0, 7 and 9, then remove two values. The stack is the app's array-based stack: a push writes the next free cell and the value drops into the stack beside the array, and a pop clears the last filled cell. Its pops take 9 and then 7, the newest values, and 0 is the top again.

Array-based stack: push 5, 0, 7, 9, pop twice

All steps as text
  1. An empty stack on an array of six cells. Push 5, 0, 7 and 9, then pop twice.
  2. Push 5: it goes into cell 0 and is the top of the stack.
  3. Push 0: it goes into cell 1, on top of 5.
  4. Push 7: it goes into cell 2, the new top.
  5. Push 9: it goes into cell 3, the new top.
  6. Pop: 9 leaves cell 3 and comes off the top, the newest value in the stack.
  7. Pop: 7 leaves cell 2, and 0 is the top again.
  8. Out came 9 and 7, newest first: last in, first out. Left are 5 and 0, with 0 on top.
Stack vs Queue — Array-based stack: push 5, 0, 7, 9, pop twice. Last step: Out came 9 and 7, newest first: last in, first out. Left are 5 and 0, with 0 on top.

The queue is drawn as the app's array-based view, with its front and rear markers and the queue below the array. Its dequeues take 5 and then 0, the oldest values, and 7 is at the front. Nothing shifts in either array: the stack works at one end, and the queue's two ends both move forward.

Array-based queue: enqueue 5, 0, 7, 9, dequeue twice

All steps as text
  1. An empty queue on an array of six cells. Enqueue 5, 0, 7 and 9, then dequeue twice.
  2. Enqueue 5 into the empty queue: it goes into cell 0, and front and rear both mark that cell.
  3. Enqueue 0 at the rear: it goes into cell 1, and rear moves there.
  4. Enqueue 7 at the rear: it goes into cell 2, and rear moves there.
  5. Enqueue 9 at the rear: it goes into cell 3, and rear moves there.
  6. Dequeue: 5 leaves from the front, the oldest value in the queue. Front moves to cell 1.
  7. Dequeue: 0 leaves from the front, the oldest value in the queue. Front moves to cell 2.
  8. Out came 5 and 0, oldest first: first in, first out. Left are 7 and 9, with 7 at the front.
Stack vs Queue — Array-based queue: enqueue 5, 0, 7, 9, dequeue twice. Last step: Out came 5 and 0, oldest first: first in, first out. Left are 7 and 9, with 7 at the front.

Stack vs queue at a glance

A stack and a queue are both linear collections that you add to and remove from one item at a time, without reaching into the middle. They differ in which item the next removal takes, and the rest of the table follows from that.

StackQueue
OrderLIFO: last in, first outFIFO: first in, first out
AddPush, at the topEnqueue, at the rear
RemovePop, from the topDequeue, from the front
Look without removingPeek at the topPeek at the front
Out of 5, 0, 7, 9 above9, then 75, then 0
On an arrayOne index, the topTwo indices, front and rear, wrapping around
On a linked listPush and pop at the headEnqueue after the tail, dequeue at the head
Time per operationThe same: O(1)
Typical usesUndo, function calls, parentheses, depth-first searchPrint jobs, requests, buffers, breadth-first search

LIFO vs FIFO: which item leaves first

A stack adds and removes at the same end, the top, so the item that leaves is always the one that arrived last. A queue adds at one end, the rear, and removes at the other, the front, so items leave in the order they came. Push 1, 2 and 3 and pop three times, and you get 3, 2, 1: the input reversed. Enqueue the same and dequeue three times, and you get 1, 2, 3, unchanged.

That one difference decides where each is used. A stack hands back the most recent unfinished thing, which is what nesting needs: the innermost call, the latest edit, the last opening parenthesis. A queue hands back the one that has waited longest, which is what fairness needs: the first print job, the earliest request, the vertex found first.

Stack and queue on an array and on a linked list

On an array, the stack needs one index, the top. A push writes at top + 1 and a pop lowers top by one, so no item ever moves. A queue that removed from the start of a plain array would shift every remaining item one cell left, which is O(n). So it keeps two indices, front and rear, and moves both forward, wrapping around to cell 0 with the modulo operator: a circular buffer. In the player, front moved from cell 0 to cell 2 while 7 and 9 stayed where they were, and cells 0 and 1 are free for the next enqueues once rear wraps around.

On a linked list, the stack pushes and pops at the head. The queue also needs a link to the tail: it enqueues after the tail and dequeues at the head. Both stay O(1), at the cost of one link per item.

Stack vs queue time complexity

Every basic operation takes O(1) on both: push, pop and peek, enqueue, dequeue and peek. On a dynamic array that doubles when full, push and enqueue are O(1) amortized: the rare copy into a bigger array, spread over all the operations, adds only a constant to each. Finding a given value means looking at the items one by one, O(n), but neither structure is meant for that. Both take O(n) space for n items on a linked list or a dynamic array; a static array reserves its whole capacity up front.

The usual trap is a queue on a list that removes its first item: Python's list.pop(0) or Java's ArrayList.remove(0) shifts everything behind it, O(n) per dequeue.

Note

Python's collections.deque and Java's ArrayDeque work at both ends in O(1) and serve as a stack and as a queue. In C++, std::stack and std::queue sit on a std::deque by default.

A queue from two stacks

Two stacks make a queue. Enqueue pushes onto the first. Dequeue pops from the second, and only when the second is empty does it move every item across from the first, which reverses them a second time and so puts the oldest on top. Each item crosses once, so both operations are O(1) amortized. The other way around, a stack from queues, costs O(n) for either push or pop, since a queue can never bring its newest item to the front without passing all the others.

When to use a stack and when to use a queue

Use a stack when the most recent item is the one to deal with next:

  • Undo: each edit is pushed, and undo pops the latest; the browser's Back button works the same way.
  • Function calls: the call stack holds each unfinished call, the innermost on top.
  • Matching brackets: push each opening one and pop it at its closing partner.
  • Backtracking: depth-first search keeps the current path on a stack.

Use a queue when items must be served in the order they arrive:

  • Print jobs and requests: a printer or a web server takes the oldest waiting job first.
  • Buffers: keystrokes, network packets and streamed data are read in the order they came.
  • Scheduling: round-robin gives each task a turn, then puts it back at the rear.
  • Level by level: breadth-first search and level order traversal visit what they found first.

Breadth-first search takes its next vertex from a queue and depth-first search from a stack: BFS vs DFS shows both at work on one tree.

Common mix-ups

  • Dequeue and deque are the same thing. Dequeue is the queue's remove operation. A deque, a double-ended queue, is a structure that adds and removes at both ends, so it can act as a stack or as a queue.
  • Pop always takes the newest item. Only on a stack. C++'s std::queue::pop removes the front, the oldest item.
  • An array-based queue has to shift its items. Only a naive one. A circular buffer moves its two indices instead, as in the player.
  • A priority queue is a queue. It is not FIFO: it removes the item with the highest priority, whatever its arrival, and is usually built on a heap.
  • A stack must be built on an array. Stack and queue name behaviors, not layouts: an array or a linked list serves either one in O(1).

Stack vs queue interview questions

What is the main difference between a stack and a queue?

Which item a removal takes. A stack takes the newest one, last in, first out, as it adds and removes at the same end. A queue takes the oldest one, first in, first out, as it adds at the rear and removes at the front.

Which one does BFS use, and which one DFS?

Breadth-first search uses a queue, so it visits vertices in the order it finds them, level by level. Depth-first search uses a stack, or recursion, so it goes on from the vertex it found last.

How do you implement a queue with two stacks?

Push every new item onto stack 1. To dequeue, pop from stack 2; if stack 2 is empty, first pop everything from stack 1 onto it, which brings the oldest item to the top. Each item is moved once, so the cost is O(1) amortized per operation.

Why does an array-based queue need a circular array when a stack does not?

A stack adds and removes at the same end, so its items never move and the free cells are always above the top. A queue removes at the front and adds at the rear, so both ends move forward; wrapping them around to the start reuses the cells that dequeues free.

Are push, pop, enqueue and dequeue all O(1)?

Yes, on a linked list and on a circular array, and amortized on a dynamic array that doubles when full. Dequeuing from the start of a plain list that shifts its items is the exception: O(n).

Six operations here.
Both topics in the app.

In VisiGrab, the stack and the queue each have a slide show you step through, with demos to tap, code in three languages and a quiz.

A 50-slide stack

From push and pop to the linked-list-based stack, by way of a browser's Back button and two parentheses checks, one balanced and one not.

An 18-slide queue

From an enqueue and dequeue demo to the linked-list-based queue, by way of a printer and a web server that takes requests in order.

Demos to tap

Pop and push on a full stack of six while a top marker follows the top. Enq and Deq on a six-slot queue, and on a circular array whose front and rear wrap around.

Theory and complexity

Each topic has an Info tab and an Efficiency tab, with a complexity table for a linked list, a static array and a dynamic array.

Python, Java and C++

Three stacks and four queues in each language, among them a circular array and a list whose dequeue is O(n), with links to the full source on GitHub.

Two quizzes

Ten questions on each, to check what you have learned before moving on.

Newest first or oldest first,
step by step.

Download VisiGrab to push, pop, enqueue and dequeue in the app's demos, and step through both topics from the first slide to the code.

The stack and the queue each have a topic among 30+. See them all