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
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.
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.
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.
| Stack | Queue | |
|---|---|---|
| Order | LIFO: last in, first out | FIFO: first in, first out |
| Add | Push, at the top | Enqueue, at the rear |
| Remove | Pop, from the top | Dequeue, from the front |
| Look without removing | Peek at the top | Peek at the front |
| Out of 5, 0, 7, 9 above | 9, then 7 | 5, then 0 |
| On an array | One index, the top | Two indices, front and rear, wrapping around |
| On a linked list | Push and pop at the head | Enqueue after the tail, dequeue at the head |
| Time per operation | The same: O(1) | |
| Typical uses | Undo, function calls, parentheses, depth-first search | Print jobs, requests, buffers, breadth-first search |
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.
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.
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.
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.
Use a stack when the most recent item is the one to deal with next:
Use a queue when items must be served in the order they arrive:
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.
std::queue::pop removes the front, the oldest item.O(1).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.
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.
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.
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.
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).
// 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.
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.
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.
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.
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.
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.
Ten questions on each, to check what you have learned before moving on.
// build your own
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