15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A queue data structure releases values in first-in, first-out order. Enqueue writes a value at the rear, dequeue removes the oldest value from the front, and front reads it without removing. In the simple array version here, enqueue is O(1) but dequeue is O(n), because every remaining value shifts one place left.
| Order | FIFO, first in first out |
|---|---|
| enqueue | O(1), write at values[size] |
| dequeue, simple array | O(n), n - 1 shifts left |
| front, isEmpty, size | O(1) each |
| Empty test | size == 0, not front == rear |
| Storage | O(C) for capacity C |
A stack removes the most recently inserted value. A queue removes the least recently inserted value.
A queue follows first in, first out (FIFO):
For a queue shown as:
| Index | 0 | 1 | 2 |
|---|---|---|---|
| Value | 4 | 7 | 2 |
front = 4rear = 2dequeue() removes 4enqueue(x) places x after 2If 7 arrives after 4, 4 leaves first.
Use this operation sequence throughout the lesson:
1enqueue(4), enqueue(7), dequeue(), enqueue(2), front()Start with an empty queue.
1queue = []
2front has no element
3rear has no elementUse a simple fixed-capacity array representation. Active queue elements occupy the array from index 0 through index size - 1.
In an array queue, dequeue() returns the front value, copies each remaining value one slot left, and shrinks size. The front always stays at index 0, and the rear sits at size - 1.
enqueue(4)The queue is empty, so write 4 into index 0.
| Index | 0 |
|---|---|
| Value | 4 |
1queue = [4]
2front = 4
3rear = 4
4size = 1With one element, that element is both the front and the rear.
enqueue(7)The rear is the insertion end. Keep 4 where it is and write 7 after it.
| Index | 0 | 1 |
|---|---|---|
| Value | 4 | 7 |
1queue = [4, 7]
2front = 4
3rear = 7
4size = 2The oldest value, 4, remains at the front.
dequeue()A dequeue removes the front value.
First, save the front value:
1returned value = 4The remaining value, 7, becomes the value at logical front position 0. In the simple array representation, shift it left one position.
| Step | Index 0 | Index 1 | Logical queue |
|---|---|---|---|
| Before dequeue | 4 | 7 | [4, 7] |
Copy array[1] into array[0] | 7 | 7 | [7] after reducing size |
After reducing the size, only index 0 belongs to the queue.
| Index | 0 |
|---|---|
| Value | 7 |
1return 4
2queue = [7]
3front = 7
4rear = 7
5size = 1enqueue(2)Write the new value after the existing element.
| Index | 0 | 1 |
|---|---|---|
| Value | 7 | 2 |
1queue = [7, 2]
2front = 7
3rear = 2
4size = 2front()front() examines the next value to dequeue and does not remove it.
1return 7
2queue remains [7, 2]
3front = 7
4rear = 2
5size = 2After each valid operation, three facts remain true:
dequeue() removes only the front.These facts form the queue’s invariant.
For the array representation used here:
size = 0, the queue has no front or rear element.size > 0, array[0] is the front.size > 0, array[size - 1] is the rear.0 through size - 1 in FIFO order.For example, after enqueue(4), enqueue(7), and dequeue(), the active array is:
| Index | 0 |
|---|---|
| Value | 7 |
The only remaining value is 7, so it is both the oldest remaining value and the newest remaining value.
Start from the invariant.
To add x without disturbing existing order:
x at index size, immediately after the current rear.size.No existing queue element moves. The old front remains the front, and x becomes the new rear.
To remove the oldest value:
array[0], because it is the front.size.The shift matters in the simple-array design. After removing index 0, the old value at index 1 becomes the new front at index 0.
To inspect the next value to leave:
array[0].size.Both front() and dequeue() use array[0] as the next value. front() leaves that value in the queue.
isEmpty() checks whether size is 0.size() returns the stored count.Tracking size distinguishes an empty queue from a one-element queue. A queue containing [4] has one front/rear element.
The queue has a fixed-capacity array.
1SimpleArrayQueue
2 values: array with capacity C
3 size: number of active queue elements
4
5Valid state:
6 0 <= size <= C
7 active elements occupy values[0 .. size - 1]
8 if size > 0:
9 values[0] is the front
10 values[size - 1] is the rear1isEmpty(queue)
2Input: a valid SimpleArrayQueue queue
3Returns: true if queue contains no active elements; otherwise false
4Mutation: does not change queue
5
6size(queue)
7Input: a valid SimpleArrayQueue queue
8Returns: the number of active elements
9Mutation: does not change queue1enqueue(queue, x)
2Input: a valid SimpleArrayQueue queue and value x
3Requires: queue.size < queue capacity
4Returns: no value
5Mutation: appends x at the rear
6
71. queue.values[queue.size] = x
82. queue.size = queue.size + 11dequeue(queue)
2Input: a valid SimpleArrayQueue queue
3Returns: the oldest enqueued value not yet dequeued
4Mutation: removes that front value and shifts remaining active values left
5Failure boundary: report empty-queue underflow if queue.size = 0
6
71. if queue.size = 0:
82. report empty-queue underflow
93. removed = queue.values[0]
104. i = 1
115. while i < queue.size:
126. queue.values[i - 1] = queue.values[i]
137. i = i + 1
148. queue.size = queue.size - 1
159. return removed1front(queue)
2Input: a valid SimpleArrayQueue queue
3Returns: the value a following dequeue would return
4Mutation: does not change queue
5Failure boundary: report empty-queue underflow if queue.size = 0
6
71. if queue.size = 0:
82. report empty-queue underflow
93. return queue.values[0]1isEmpty(queue)
2Input: a valid SimpleArrayQueue queue
3Returns: true exactly when queue has no active elements
4Mutation: does not change queue
5
61. return queue.size = 01size(queue)
2Input: a valid SimpleArrayQueue queue
3Returns: number of active elements
4Mutation: does not change queue
5
61. return queue.sizeUse the original sequence:
1enqueue(4), enqueue(7), dequeue(), enqueue(2), front()Assume the array has enough capacity.
Initial state:
| Index | 0 | 1 |
|---|---|---|
| Value | — | — |
1size = 0enqueue(queue, 4)4 at values[size] = values[0].size from 0 to 1.| Index | 0 |
|---|---|
| Value | 4 |
1queue = [4]
2front = 4
3rear = 4
4size = 1enqueue(queue, 7)7 at values[size] = values[1].size from 1 to 2.| Index | 0 | 1 |
|---|---|---|
| Value | 4 | 7 |
1queue = [4, 7]
2front = 4
3rear = 7
4size = 2dequeue(queue)size = 0. It is false because size = 2.removed = values[0] = 4.i = 1.1 < 2, so the loop runs.values[1] into values[0]. Line 6 writes 7 into index 0.i from 1 to 2.2 < 2. It is false, so shifting stops.size from 2 to 1.removed, which is 4.| Index | 0 |
|---|---|
| Value | 7 |
1return 4
2queue = [7]
3front = 7
4rear = 7
5size = 1enqueue(queue, 2)2 at values[size] = values[1].size from 1 to 2.| Index | 0 | 1 |
|---|---|---|
| Value | 7 | 2 |
1queue = [7, 2]
2front = 7
3rear = 2
4size = 2front(queue)size = 0. It is false.values[0], which is 7.1return 7
2queue remains [7, 2]
3size remains 2Each operation preserves the queue invariant and produces its required result.
A new queue has size = 0.
There are no active array elements, so there is no front or rear. The invariant holds because there is no enqueued value waiting to be dequeued.
Assume the queue is valid before enqueue(queue, x).
The active values are in values[0 .. size - 1], ordered from oldest to newest. The algorithm writes x at values[size], after all existing values, then increases size.
Enqueue preserves the order of existing elements and places the new value at the rear.
Assume the queue is nonempty and valid before dequeue(queue).
By the invariant, values[0] is the oldest enqueued value not yet dequeued. The algorithm saves that value in removed.
During the shift loop, before an iteration with index i, the values from old indices 1 through i - 1 have already been copied one position left without changing their relative order. Line 6 copies the next old value, values[i], into values[i - 1]. The loop preserves the relative order of every remaining value.
When the loop terminates, every old active value from indices 1 through size - 1 has moved left by one position. After decreasing size, the active array contains exactly the old queue except for its front value.
Dequeue returns the oldest active value and removes only that value.
Assume the queue is nonempty and valid before front(queue).
The invariant says values[0] is the oldest active value. front() returns values[0] and does not write an array cell or change size.
front() returns exactly the value that a following dequeue would return and leaves the queue unchanged.
Both dequeue() and front() test size = 0 before reading values[0].
Neither operation accesses a front element when no active front exists.
Let n be the current number of queue elements.
enqueue() performs:
size.That is a constant number of operations when capacity remains.
1Time: O(1)dequeue() first reads the front value. Its loop starts at i = 1 and continues while i < n.
The loop runs once for each remaining element:
1i = 1, 2, 3, ..., n - 1That is n - 1 shifts. Each iteration performs one array assignment and one index increment.
1Time: O(n)For a one-element queue, there are 0 shifts. For a queue with more elements, the work grows with the number of remaining elements.
front() checks size and reads one array cell.isEmpty() compares size with 0.size() returns one stored value.Each performs a constant number of operations.
1Time: O(1) eachAn array with capacity C stores up to C queue values and a constant amount of metadata such as size.
1Container storage: O(C)
2Extra temporary space per operation: O(1)dequeue() uses only a saved removed value and an index i in addition to the queue itself.
Incorrect assumption:
1dequeue removes values[size - 1]Smallest exposing input:
1enqueue(4), enqueue(7), dequeue()Wrong result:
1return 74 entered first, so FIFO requires:
1return 4Correction: dequeue must use the front value at values[0].
Incorrect line:
1values[i] = values[i - 1]Exposing queue before dequeue:
1[4, 7, 2]If the loop runs left to right:
i = 1, write values[1] = values[0], producing [4, 4, 2].i = 2, write values[2] = values[1], producing [4, 4, 4].After reducing the size, the queue incorrectly becomes [4, 4].
Correction:
1values[i - 1] = values[i]Start at old index 1 and copy each remaining value toward the front.
Incorrect empty condition:
1if front position equals rear position:
2 queue is emptyExposing input:
1enqueue(4)The queue contains one value:
1queue = [4]
2front = 4
3rear = 4The incorrect condition rejects dequeue() even though 4 should be returned.
Correction: track size, and consider the queue empty only when:
1size = 0Incorrect behavior:
1remove 4, but do not shift remaining values or advance the logical frontExposing input:
1enqueue(4), enqueue(7), dequeue(), front()Wrong result:
1front() returns 4After removing 4, the queue should contain only [7].
Correction: in the simple-array representation, shift 7 into index 0 during dequeue so that front() returns 7.
| Operations | Required result |
|---|---|
dequeue() on [] | Report empty-queue underflow or the documented failure behavior |
front() on [] | Report empty-queue underflow or the documented failure behavior |
enqueue(5), dequeue() | Return 5; queue becomes empty |
enqueue(1), enqueue(2), dequeue(), dequeue() | Return 1, then 2 |
enqueue(1), dequeue(), enqueue(2) | Queue contains only 2 |
Practice objective: Implement a simple array queue whose enqueue, dequeue, front, isEmpty, and size operations pass FIFO-order tests and empty-queue tests.
Your implementation contract should test that:
enqueue(x) preserves existing order and appends x at the rear.dequeue() returns the oldest value and removes it from the front.front() returns the same value that a following dequeue() would return without changing the queue.dequeue() and front() detect an empty queue before accessing an element.0 while preserving relative order.1class ShiftQueue:
2 def __init__(self, capacity):
3 self.values = [0] * capacity
4 self.size = 0
5 self.shifts = 0 # counts array copies made by dequeue
6
7 def enqueue(self, x):
8 if self.size == len(self.values):
9 raise OverflowError("full")
10 self.values[self.size] = x # write after the current rear
11 self.size += 1
12
13 def dequeue(self):
14 if self.size == 0:
15 raise IndexError("underflow")
16 removed = self.values[0]
17 i = 1
18 while i < self.size: # shift every remaining value left
19 self.values[i - 1] = self.values[i]
20 self.shifts += 1
21 i += 1
22 self.size -= 1
23 return removed
24
25 def front(self):
26 if self.size == 0:
27 raise IndexError("underflow")
28 return self.values[0]
29
30q = ShiftQueue(4)
31q.enqueue(4)
32q.enqueue(7)
33print("dequeue:", q.dequeue())
34q.enqueue(2)
35print("front:", q.front())
36print("queue:", q.values[:q.size])
37print("size:", q.size)
38print("shifts:", q.shifts)
39
40big = ShiftQueue(5)
41for x in (1, 2, 3, 4, 5):
42 big.enqueue(x)
43big.dequeue()
44print("shifts to dequeue from 5 elements:", big.shifts)1import java.util.Arrays;
2
3public class Main {
4 static class ShiftQueue {
5 int[] values;
6 int size = 0;
7 int shifts = 0; // counts array copies made by dequeue
8
9 ShiftQueue(int capacity) {
10 values = new int[capacity];
11 }
12
13 void enqueue(int x) {
14 if (size == values.length) throw new IllegalStateException("full");
15 values[size] = x; // write after the current rear
16 size++;
17 }
18
19 int dequeue() {
20 if (size == 0) throw new IllegalStateException("underflow");
21 int removed = values[0];
22 int i = 1;
23 while (i < size) { // shift every remaining value left
24 values[i - 1] = values[i];
25 shifts++;
26 i++;
27 }
28 size--;
29 return removed;
30 }
31
32 int front() {
33 if (size == 0) throw new IllegalStateException("underflow");
34 return values[0];
35 }
36 }
37
38 public static void main(String[] args) {
39 ShiftQueue q = new ShiftQueue(4);
40 q.enqueue(4);
41 q.enqueue(7);
42 System.out.println("dequeue: " + q.dequeue());
43 q.enqueue(2);
44 System.out.println("front: " + q.front());
45 System.out.println("queue: " + Arrays.toString(Arrays.copyOf(q.values, q.size)));
46 System.out.println("size: " + q.size);
47 System.out.println("shifts: " + q.shifts);
48
49 ShiftQueue big = new ShiftQueue(5);
50 for (int x = 1; x <= 5; x++) big.enqueue(x);
51 big.dequeue();
52 System.out.println("shifts to dequeue from 5 elements: " + big.shifts);
53 }
54}1#include <iostream>
2#include <stdexcept>
3#include <vector>
4using namespace std;
5
6struct ShiftQueue {
7 vector<int> values;
8 int size = 0;
9 int shifts = 0; // counts array copies made by dequeue
10
11 ShiftQueue(int capacity) : values(capacity) {}
12
13 void enqueue(int x) {
14 if (size == (int)values.size()) throw runtime_error("full");
15 values[size] = x; // write after the current rear
16 size++;
17 }
18
19 int dequeue() {
20 if (size == 0) throw runtime_error("underflow");
21 int removed = values[0];
22 int i = 1;
23 while (i < size) { // shift every remaining value left
24 values[i - 1] = values[i];
25 shifts++;
26 i++;
27 }
28 size--;
29 return removed;
30 }
31
32 int front() {
33 if (size == 0) throw runtime_error("underflow");
34 return values[0];
35 }
36};
37
38int main() {
39 ShiftQueue q(4);
40 q.enqueue(4);
41 q.enqueue(7);
42 cout << "dequeue: " << q.dequeue() << endl;
43 q.enqueue(2);
44 cout << "front: " << q.front() << endl;
45 cout << "queue: [";
46 for (int i = 0; i < q.size; i++) cout << (i ? ", " : "") << q.values[i];
47 cout << "]" << endl;
48 cout << "size: " << q.size << endl;
49 cout << "shifts: " << q.shifts << endl;
50
51 ShiftQueue big(5);
52 for (int x = 1; x <= 5; x++) big.enqueue(x);
53 big.dequeue();
54 cout << "shifts to dequeue from 5 elements: " << big.shifts << endl;
55}1class ShiftQueue {
2 constructor(capacity) {
3 this.values = new Array(capacity).fill(0);
4 this.size = 0;
5 this.shifts = 0; // counts array copies made by dequeue
6 }
7
8 enqueue(x) {
9 if (this.size === this.values.length) throw new Error('full');
10 this.values[this.size] = x; // write after the current rear
11 this.size++;
12 }
13
14 dequeue() {
15 if (this.size === 0) throw new Error('underflow');
16 const removed = this.values[0];
17 let i = 1;
18 while (i < this.size) { // shift every remaining value left
19 this.values[i - 1] = this.values[i];
20 this.shifts++;
21 i++;
22 }
23 this.size--;
24 return removed;
25 }
26
27 front() {
28 if (this.size === 0) throw new Error('underflow');
29 return this.values[0];
30 }
31}
32
33const q = new ShiftQueue(4);
34q.enqueue(4);
35q.enqueue(7);
36console.log('dequeue:', q.dequeue());
37q.enqueue(2);
38console.log('front:', q.front());
39console.log(`queue: [${q.values.slice(0, q.size).join(', ')}]`);
40console.log('size:', q.size);
41console.log('shifts:', q.shifts);
42
43const big = new ShiftQueue(5);
44for (const x of [1, 2, 3, 4, 5]) big.enqueue(x);
45big.dequeue();
46console.log('shifts to dequeue from 5 elements:', big.shifts);A queue is FIFO. The value that entered first leaves first, and dequeue removes only the front. A stack is the LIFO structure: its pop removes the newest value.
It is an abstract data type: a contract that says enqueue goes to the rear and dequeue comes from the front. A shifting array, a circular array and a linked list can all implement that contract.
The usual four are the simple queue, the circular queue, the priority queue and the double-ended queue (deque). This page covers the simple queue; the circular queue has its own lesson.
After the front leaves, values[1] must become values[0], and so on to the rear. With n values that is n - 1 copies. Five values cost 4 shifts, as the code above counts.
Stop shifting. A circular array moves a front index forward with (index + 1) mod capacity. A linked queue keeps front and rear pointers and advances front. Both avoid copying.