15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A stack implementation using an array needs an array and a count named top. Push writes at items[top], then increments top. Pop decrements top, then reads items[top]. Both are O(1) while the array has room, and a resize costs O(n) for the one push that triggers it.
| Array stack push and pop | O(1) while capacity remains |
|---|---|
| Array push that resizes | O(n) for that one push, copying n elements |
| Linked stack push and pop | O(1), both at the head node |
| Linked queue enqueue and dequeue | O(1), with stored front and rear pointers |
| Storage | Array O(C) reserved, linked O(n), one node per element |
You should already know the public behavior:
The representation determines how the container stores those values.
Two common choices are:
| Representation | Stored form | Directly stored fields |
|---|---|---|
| Array-backed container | Contiguous array cells | Array and index or indices |
| Linked container | Separate nodes connected by references | One or more node pointers |
For an array-backed stack, top can name the index of the current top value. Push writes at the next available position; pop reads the current top position and changes top.
For a linked stack, the head node is the top. Push and pop both happen at the head.
For a linked queue, store:
front: the node whose value will be dequeued nextrear: the final nodeA node has this form:
1Node:
2 value
3 nextThe next reference of the final node is null.
Use one linked queue and perform these operations:
1enqueue(4), enqueue(7), dequeue(), enqueue(2)The queue begins empty.
1front = null
2rear = null
3queue = []We will name nodes by their values when there is no ambiguity:
1node 4: [4 | next]
2node 7: [7 | next]
3node 2: [2 | next]The empty-queue boundary occurs at the start. The first enqueue must establish both ends of an empty queue.
1front = null
2rear = null
3queue = []There is no first node and no last node.
enqueue(4)First create a detached node:
1newNode = [4 | null]The queue is empty, so this one node is both the first and final node.
1front = newNode
2rear = newNodeState:
Follow front and rear through enqueue(4), enqueue(7), dequeue() and enqueue(2). Enqueue links the old rear to the new node first, then moves rear. Dequeue moves front forward. The queue ends as [7, 2].
enqueue(7)Create the new final node:
1newNode = [7 | null]The queue is nonempty. The old rear is node 4.
Link the old rear to the new node before moving rear:
1rear.next = newNodeThe reachable chain is now complete:
1front rear
2 | |
3 v v
4[4 | next] --------> [7 | null]Then move rear:
1rear = newNodeState:
1front rear
2 | |
3 v v
4[4 | next] --------> [7 | null]
5
6queue = [4, 7]dequeue()The front node contains the value to return.
First save that value:
1removedValue = front.value // 4Then advance front to the next node:
1front = front.nextNode 7 is now the first node. It was already the final node, so rear remains there.
The removed node is no longer reachable from front or rear.
enqueue(2)Create a new detached final node:
1newNode = [2 | null]The queue is nonempty. Link node 7 to node 2:
1rear.next = newNodeThen move rear:
1rear = newNodeFinal state:
1front rear
2 | |
3 v v
4[7 | next] --------> [2 | null]
5
6queue = [7, 2]After each valid queue operation, the queue has a precise shape:
front points to the node containing the next value to dequeue.rear points to the final node.rear.next is null.front and rear are null.The queue's invariant is a condition that remains true after every operation.
Example states:
enqueue(4), node 4 is both first and final.enqueue(7), node 4 remains first and node 7 becomes final.dequeue(), node 7 becomes both first and final.enqueue(2), node 7 remains first and node 2 becomes final.The stored rear pointer gives direct access to the place where a new node must be linked. Without it, a singly linked queue must start at front and follow next references until it finds the final node. That traversal is not constant work.
A linked stack stores its directly accessible end at the head:
1top
2 |
3 v
4[7 | next] -> [4 | null]Push links a new node at top. Pop advances top to the old top's next node.
Use the invariant to determine the required updates for each operation.
For a stack, use top as the head pointer.
Push:
next points to the old top.top to the new node.Set the link first. Changing top first would lose direct access to the old stack.
Pop:
top is null.top to top.next.The old top node is no longer reachable from the stack after step 3.
For a queue, use front and rear.
Enqueue on an empty queue:
newNode with newNode.next = null.front = newNode.rear = newNode.Enqueue on a nonempty queue:
newNode with newNode.next = null.rear.next = newNode.rear = newNode.Steps 2 and 3 must remain in that order. The old rear is the node that must receive the new link.
Dequeue:
front is null.front.value.front to front.next.front is now null, also set rear = null.Step 4 handles the one-element-to-empty transition.
An array-backed stack stores values in contiguous cells and a top index. If top is the number of current elements, then:
items[top], then increments top.top, then reads items[top].If the array has no available cell, a dynamically resized representation must allocate a larger array and copy the current elements before the write. If capacity starts at 0, the first allocation must use a positive capacity.
An array queue that shifts every remaining value left during dequeue does not meet a constant-time dequeue requirement. Use circular indexing or linked nodes when that requirement is stated.
The following queue operations mutate a LinkedQueue.
1record Node:
2 value
3 next
4
5record LinkedQueue:
6 front
7 rear1makeNode(value)
2Input: any value
3Returns: a new Node whose value is value and whose next is null
4Mutation: does not mutate any existing queue or node1enqueue(queue, value)
2Input: queue is a valid LinkedQueue; value is any value
3Returns: nothing
4Mutation: adds one new node containing value to the rear of queue
5
61. newNode = makeNode(value)
72. if queue.rear == null:
83. queue.front = newNode
94. queue.rear = newNode
105. return
116. queue.rear.next = newNode
127. queue.rear = newNode1dequeue(queue)
2Input: queue is a valid LinkedQueue
3Returns: the front value
4Mutation: removes the front node from queue
5Boundary: reports underflow if queue.front is null
6
71. if queue.front == null:
82. report underflow
93. oldFront = queue.front
104. removedValue = oldFront.value
115. queue.front = oldFront.next
126. if queue.front == null:
137. queue.rear = null
148. return removedValue1frontValue(queue)
2Input: queue is a valid LinkedQueue
3Returns: the next value that dequeue would return
4Mutation: none
5Boundary: reports underflow if queue.front is null
6
71. if queue.front == null:
82. report underflow
93. return queue.front.value1isEmpty(queue)
2Input: queue is a valid LinkedQueue
3Returns: true when queue contains no nodes; otherwise false
4Mutation: none
5
61. return queue.front == nullFor a valid empty linked queue, front == null and rear == null. Checking front is sufficient for isEmpty because enqueue and dequeue maintain the other condition.
1push(stack, value)
2Input: stack has a top pointer; value is any value
3Returns: nothing
4Mutation: adds value to the top of stack
5
61. newNode = makeNode(value)
72. newNode.next = stack.top
83. stack.top = newNode1pop(stack)
2Input: stack has a top pointer
3Returns: the top value
4Mutation: removes the top node
5Boundary: reports underflow if stack.top is null
6
71. if stack.top == null:
82. report underflow
93. oldTop = stack.top
104. removedValue = oldTop.value
115. stack.top = oldTop.next
126. return removedValueUse the same queue operations:
1enqueue(4), enqueue(7), dequeue(), enqueue(2)Initial queue:
1queue.front = null
2queue.rear = nullenqueue(queue, 4)| Line | Action | Queue state |
|---|---|---|
| 1 | newNode = makeNode(4) | newNode = [4 | null]; queue remains empty |
| 2 | queue.rear == null is true | Enter empty-queue branch |
| 3 | queue.front = newNode | front -> [4 | null] |
| 4 | queue.rear = newNode | front and rear both point to node 4 |
| 5 | Return | Queue is [4] |
1front
2 |
3 v
4[4 | null]
5 ^
6 |
7rearenqueue(queue, 7)| Line | Action | Queue state |
|---|---|---|
| 1 | newNode = makeNode(7) | New detached node: [7 | null] |
| 2 | queue.rear == null is false | Skip lines 3–5 |
| 6 | queue.rear.next = newNode | Node 4 now points to node 7 |
| 7 | queue.rear = newNode | rear moves to node 7 |
1front rear
2 | |
3 v v
4[4 | next] --------> [7 | null]dequeue(queue)| Line | Action | Queue state |
|---|---|---|
| 1 | queue.front == null is false | Continue |
| 3 | oldFront = queue.front | oldFront points to node 4 |
| 4 | removedValue = oldFront.value | removedValue = 4 |
| 5 | queue.front = oldFront.next | front moves to node 7 |
| 6 | queue.front == null is false | Skip line 7 |
| 8 | Return removedValue | Return 4 |
1front
2 |
3 v
4[7 | null]
5 ^
6 |
7rear
8
9returned 4enqueue(queue, 2)| Line | Action | Queue state |
|---|---|---|
| 1 | newNode = makeNode(2) | New detached node: [2 | null] |
| 2 | queue.rear == null is false | Skip lines 3–5 |
| 6 | queue.rear.next = newNode | Node 7 now points to node 2 |
| 7 | queue.rear = newNode | rear moves to node 2 |
1front rear
2 | |
3 v v
4[7 | next] --------> [2 | null]The returned sequence contains 4, and the queue now contains [7, 2] in FIFO order.
We prove that the linked queue operations preserve the queue invariant and provide FIFO behavior.
A new queue has:
1front = null
2rear = nullThe queue is empty, satisfying the invariant's empty-queue condition.
Consider enqueue(queue, value).
If the queue is empty, line 1 creates a node whose next is null. Lines 3 and 4 set both front and rear to that node. Therefore:
front points to the next dequeue value,rear points to the final node,rear.next is null.If the queue is nonempty, the invariant says rear points to the final node. Line 6 changes that final node's next to the new node. Line 7 then makes the new node the rear. Because a new node has next = null, the new rear has next = null. The old front does not change, so the next dequeue value also does not change.
Enqueue preserves the invariant and appends the value after all older queue values.
For a nonempty queue, the invariant says front points to the node containing the next dequeue value. Lines 3 and 4 save exactly that value. Line 5 advances front to the next node.
There are two cases:
front is not null, another node remains. rear still points to the final node, and FIFO order is preserved.front is null, the removed node was the only node. Line 7 sets rear to null, restoring the required empty state.After line 5, the removed node cannot be reached through front or rear. The node is no longer part of the container representation.
Neither operation contains a loop. Enqueue performs a fixed sequence of node and pointer updates. Dequeue performs a fixed sequence of checks and pointer updates.
Enqueue appends each new value at rear, and dequeue removes the node at front. Values leave in the order they entered. A queue has FIFO behavior when linked nodes, circular array indexing, or another representation preserves the same public queue contract.
The linked stack uses corresponding head updates. Push makes the new node point to the old top before replacing top; pop moves top to the old top's next node. The most recently pushed reachable node is always the next one popped.
For enqueue:
rear is null.There is no traversal from front to find the final node because rear is stored directly. The number of operations does not grow with the number of queue elements, so enqueue is O(1) time.
For dequeue:
front.front.rear to null.The work remains fixed, so dequeue is O(1) time.
Each operation uses a constant number of temporary references and values. Its auxiliary space is O(1).
A linked queue with n elements stores one node per element plus the front and rear pointers. Its storage is O(n).
A linked stack push changes one new-node link and the top pointer. A pop reads the old top and advances top once. Each operation is O(1) time and uses O(1) temporary auxiliary space.
The stack stores one node per current element, so its container storage is O(n).
For an array-backed stack, ordinary push and pop use:
top update.That is O(1) time for an operation when the current array has sufficient capacity.
If a dynamic array must grow or shrink, it copies the current n elements into a resized array. That individual resize operation costs O(n) time. Every dynamic-array push is therefore not O(1) in the worst case. Ordinary pushes are O(1), while a push that triggers a resize includes an O(n) copy.
An array-backed container with capacity C reserves O(C) storage, even if it currently holds fewer than C elements. Each stack operation still uses O(1) temporary auxiliary space.
rear before linking the old rearIncorrect nonempty enqueue order:
1queue.rear = newNode
2queue.rear.next = newNodeSmallest exposing input:
1enqueue(4), enqueue(7)After enqueue(4), both pointers name node 4. During the second enqueue, the first incorrect line changes rear to node 7. The old rear, node 4, is no longer available through queue.rear.
The second line sets node 7's next to itself or otherwise fails to connect node 4 to node 7. From front, node 7 is unreachable.
Correct order:
1queue.rear.next = newNode
2queue.rear = newNoderear after the final dequeueIncorrect dequeue fragment:
1queue.front = oldFront.next
2return removedValueSmallest exposing input:
1enqueue(4), dequeue(), enqueue(7)After dequeue(), front becomes null, but rear still points to the removed node 4. The queue claims to be empty at the front while retaining a stale final pointer. A later enqueue can link from that removed node instead of establishing node 7 as both front and rear.
Correct fragment:
1queue.front = oldFront.next
2if queue.front == null:
3 queue.rear = nullIncorrect design assumption:
1To push, walk from head to the final node and append there.Exposing input:
1push n valuesEach push must traverse all existing nodes to find the tail. As the stack grows, pushes require increasingly many link traversals.
Correct design:
1newNode.next = stack.top
2stack.top = newNodeThe head is directly stored, so both push and pop update it in O(1) time.
Incorrect claim:
1A dynamic-array stack push is always O(1).Exposing input:
1push when size equals capacityBefore writing the new element, the representation must allocate a resized array and copy the current n elements. That operation includes O(n) copying work.
Correct statement:
1An ordinary array-stack push is O(1).
2A push that triggers resizing costs O(n) for that operation.Incorrect pop or dequeue assumption:
1removedValue = top.valueor
1removedValue = front.valueExposing input:
1pop on an empty linked stackor
1dequeue on an empty linked queueHere top or front is null, so there is no node whose value can be read.
Correction: test for emptiness first and report underflow without dereferencing null.
Incorrect first-push behavior:
1items[top] = valuewhen:
1capacity = 0
2top = 0There is no valid array cell at index 0.
Correction: when a resize is needed from capacity 0, allocate a positive capacity before writing the first value.
Incorrect dequeue approach:
1remove items[0]
2shift every remaining element one position leftExposing input:
1a queue with n elements followed by dequeue()The shift writes up to n - 1 remaining elements. The dequeue is not constant time.
Correction: use circular indexing in an array representation, or use a linked queue with stored front and rear pointers.
Objective: Implement a linked queue with enqueue, dequeue, front, and isEmpty.
The tests will check:
Your implementation contract is:
1enqueue(value)
2- Adds value at the rear.
3- On an empty queue, sets both front and rear to the new node.
4
5dequeue()
6- Removes and returns the front value.
7- Reports underflow on an empty queue.
8- When removing the final node, sets both front and rear to null.
9
10front()
11- Returns the next dequeue value without removing it.
12- Reports underflow on an empty queue.
13
14isEmpty()
15- Returns true exactly when the queue has no nodes.For representation background and comparison scope, consult the Algorithms, 4th edition companion site and the Mastering Data Structures and Algorithms course outline.
1class ArrayStack:
2 def __init__(self):
3 self.items = [] # capacity starts at 0
4 self.top = 0 # element count, and the next free cell
5
6 def push(self, value):
7 if self.top == len(self.items): # full: grow before writing
8 bigger = [0] * max(1, 2 * len(self.items))
9 for i in range(self.top):
10 bigger[i] = self.items[i] # the O(n) copy
11 self.items = bigger
12 self.items[self.top] = value
13 self.top += 1
14
15 def pop(self):
16 if self.top == 0:
17 raise IndexError("underflow")
18 self.top -= 1
19 return self.items[self.top]
20
21class Node:
22 def __init__(self, value, nxt=None):
23 self.value = value
24 self.next = nxt
25
26class LinkedStack:
27 def __init__(self):
28 self.top = None
29
30 def push(self, value):
31 self.top = Node(value, self.top) # link to the old top, then move top
32
33 def pop(self):
34 if self.top is None:
35 raise IndexError("underflow")
36 node = self.top
37 self.top = node.next
38 return node.value
39
40class LinkedQueue:
41 def __init__(self):
42 self.front = None
43 self.rear = None
44
45 def enqueue(self, value):
46 node = Node(value)
47 if self.rear is None: # empty: set both ends
48 self.front = self.rear = node
49 return
50 self.rear.next = node # link the old rear first
51 self.rear = node
52
53 def dequeue(self):
54 if self.front is None:
55 raise IndexError("underflow")
56 node = self.front
57 self.front = node.next
58 if self.front is None: # last node left: clear rear too
59 self.rear = None
60 return node.value
61
62def chain(node):
63 out = []
64 while node is not None:
65 out.append(node.value)
66 node = node.next
67 return out
68
69a, s = ArrayStack(), LinkedStack()
70for v in (4, 7):
71 a.push(v)
72 s.push(v)
73print("pop:", a.pop(), s.pop())
74a.push(2)
75s.push(2)
76print(f"array stack, bottom to top: {a.items[:a.top]}, capacity {len(a.items)}")
77print("linked stack, top first:", chain(s.top))
78
79q = LinkedQueue()
80q.enqueue(4)
81q.enqueue(7)
82print("dequeue:", q.dequeue())
83q.enqueue(2)
84print("linked queue, front to rear:", chain(q.front))
85q.dequeue()
86q.dequeue()
87q.enqueue(9)
88print("after emptying, enqueue(9):", chain(q.front))1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class Main {
6 static class ArrayStack {
7 int[] items = new int[0]; // capacity starts at 0
8 int top = 0; // element count, and the next free cell
9
10 void push(int value) {
11 if (top == items.length) { // full: grow before writing
12 int[] bigger = new int[Math.max(1, 2 * items.length)];
13 for (int i = 0; i < top; i++) bigger[i] = items[i]; // the O(n) copy
14 items = bigger;
15 }
16 items[top] = value;
17 top++;
18 }
19
20 int pop() {
21 if (top == 0) throw new IllegalStateException("underflow");
22 top--;
23 return items[top];
24 }
25 }
26
27 static class Node {
28 int value;
29 Node next;
30
31 Node(int value, Node next) {
32 this.value = value;
33 this.next = next;
34 }
35 }
36
37 static class LinkedStack {
38 Node top = null;
39
40 void push(int value) {
41 top = new Node(value, top); // link to the old top, then move top
42 }
43
44 int pop() {
45 if (top == null) throw new IllegalStateException("underflow");
46 Node node = top;
47 top = node.next;
48 return node.value;
49 }
50 }
51
52 static class LinkedQueue {
53 Node front = null;
54 Node rear = null;
55
56 void enqueue(int value) {
57 Node node = new Node(value, null);
58 if (rear == null) { // empty: set both ends
59 front = node;
60 rear = node;
61 return;
62 }
63 rear.next = node; // link the old rear first
64 rear = node;
65 }
66
67 int dequeue() {
68 if (front == null) throw new IllegalStateException("underflow");
69 Node node = front;
70 front = node.next;
71 if (front == null) rear = null; // last node left: clear rear too
72 return node.value;
73 }
74 }
75
76 static List<Integer> chain(Node node) {
77 List<Integer> out = new ArrayList<>();
78 for (; node != null; node = node.next) out.add(node.value);
79 return out;
80 }
81
82 public static void main(String[] args) {
83 ArrayStack a = new ArrayStack();
84 LinkedStack s = new LinkedStack();
85 for (int v : new int[]{4, 7}) {
86 a.push(v);
87 s.push(v);
88 }
89 System.out.println("pop: " + a.pop() + " " + s.pop());
90 a.push(2);
91 s.push(2);
92 System.out.println("array stack, bottom to top: " + Arrays.toString(Arrays.copyOf(a.items, a.top))
93 + ", capacity " + a.items.length);
94 System.out.println("linked stack, top first: " + chain(s.top));
95
96 LinkedQueue q = new LinkedQueue();
97 q.enqueue(4);
98 q.enqueue(7);
99 System.out.println("dequeue: " + q.dequeue());
100 q.enqueue(2);
101 System.out.println("linked queue, front to rear: " + chain(q.front));
102 q.dequeue();
103 q.dequeue();
104 q.enqueue(9);
105 System.out.println("after emptying, enqueue(9): " + chain(q.front));
106 }
107}1#include <iostream>
2#include <stdexcept>
3#include <vector>
4using namespace std;
5
6struct ArrayStack {
7 vector<int> items; // size() is the capacity, starts at 0
8 int top = 0; // element count, and the next free cell
9
10 void push(int value) {
11 if (top == (int)items.size()) { // full: grow before writing
12 vector<int> bigger(max<size_t>(1, 2 * items.size()));
13 for (int i = 0; i < top; i++) bigger[i] = items[i]; // the O(n) copy
14 items = bigger;
15 }
16 items[top++] = value;
17 }
18
19 int pop() {
20 if (top == 0) throw runtime_error("underflow");
21 return items[--top];
22 }
23};
24
25struct Node {
26 int value;
27 Node* next;
28 Node(int v, Node* n) : value(v), next(n) {}
29};
30
31struct LinkedStack {
32 Node* top = nullptr;
33
34 void push(int value) { top = new Node(value, top); } // link to the old top, then move top
35
36 int pop() {
37 if (!top) throw runtime_error("underflow");
38 Node* node = top;
39 top = node->next;
40 int value = node->value;
41 delete node;
42 return value;
43 }
44};
45
46struct LinkedQueue {
47 Node* front = nullptr;
48 Node* rear = nullptr;
49
50 void enqueue(int value) {
51 Node* node = new Node(value, nullptr);
52 if (!rear) { // empty: set both ends
53 front = rear = node;
54 return;
55 }
56 rear->next = node; // link the old rear first
57 rear = node;
58 }
59
60 int dequeue() {
61 if (!front) throw runtime_error("underflow");
62 Node* node = front;
63 front = node->next;
64 if (!front) rear = nullptr; // last node left: clear rear too
65 int value = node->value;
66 delete node;
67 return value;
68 }
69};
70
71string chain(Node* node) {
72 string out = "[";
73 for (bool first = true; node; node = node->next, first = false)
74 out += (first ? "" : ", ") + to_string(node->value);
75 return out + "]";
76}
77
78int main() {
79 ArrayStack a;
80 LinkedStack s;
81 for (int v : {4, 7}) {
82 a.push(v);
83 s.push(v);
84 }
85 int pa = a.pop();
86 int ps = s.pop();
87 cout << "pop: " << pa << " " << ps << endl;
88 a.push(2);
89 s.push(2);
90 cout << "array stack, bottom to top: [";
91 for (int i = 0; i < a.top; i++) cout << (i ? ", " : "") << a.items[i];
92 cout << "], capacity " << a.items.size() << endl;
93 cout << "linked stack, top first: " << chain(s.top) << endl;
94
95 LinkedQueue q;
96 q.enqueue(4);
97 q.enqueue(7);
98 cout << "dequeue: " << q.dequeue() << endl;
99 q.enqueue(2);
100 cout << "linked queue, front to rear: " << chain(q.front) << endl;
101 q.dequeue();
102 q.dequeue();
103 q.enqueue(9);
104 cout << "after emptying, enqueue(9): " << chain(q.front) << endl;
105}1class ArrayStack {
2 constructor() {
3 this.items = []; // capacity starts at 0
4 this.top = 0; // element count, and the next free cell
5 }
6
7 push(value) {
8 if (this.top === this.items.length) { // full: grow before writing
9 const bigger = new Array(Math.max(1, 2 * this.items.length)).fill(0);
10 for (let i = 0; i < this.top; i++) bigger[i] = this.items[i]; // the O(n) copy
11 this.items = bigger;
12 }
13 this.items[this.top] = value;
14 this.top++;
15 }
16
17 pop() {
18 if (this.top === 0) throw new Error('underflow');
19 this.top--;
20 return this.items[this.top];
21 }
22}
23
24class Node {
25 constructor(value, next) {
26 this.value = value;
27 this.next = next;
28 }
29}
30
31class LinkedStack {
32 constructor() {
33 this.top = null;
34 }
35
36 push(value) {
37 this.top = new Node(value, this.top); // link to the old top, then move top
38 }
39
40 pop() {
41 if (this.top === null) throw new Error('underflow');
42 const node = this.top;
43 this.top = node.next;
44 return node.value;
45 }
46}
47
48class LinkedQueue {
49 constructor() {
50 this.front = null;
51 this.rear = null;
52 }
53
54 enqueue(value) {
55 const node = new Node(value, null);
56 if (this.rear === null) { // empty: set both ends
57 this.front = node;
58 this.rear = node;
59 return;
60 }
61 this.rear.next = node; // link the old rear first
62 this.rear = node;
63 }
64
65 dequeue() {
66 if (this.front === null) throw new Error('underflow');
67 const node = this.front;
68 this.front = node.next;
69 if (this.front === null) this.rear = null; // last node left: clear rear too
70 return node.value;
71 }
72}
73
74function chain(node) {
75 const out = [];
76 for (; node !== null; node = node.next) out.push(node.value);
77 return `[${out.join(', ')}]`;
78}
79
80const a = new ArrayStack();
81const s = new LinkedStack();
82for (const v of [4, 7]) {
83 a.push(v);
84 s.push(v);
85}
86const pa = a.pop();
87const ps = s.pop();
88console.log(`pop: ${pa} ${ps}`);
89a.push(2);
90s.push(2);
91console.log(`array stack, bottom to top: [${a.items.slice(0, a.top).join(', ')}], capacity ${a.items.length}`);
92console.log(`linked stack, top first: ${chain(s.top)}`);
93
94const q = new LinkedQueue();
95q.enqueue(4);
96q.enqueue(7);
97console.log(`dequeue: ${q.dequeue()}`);
98q.enqueue(2);
99console.log(`linked queue, front to rear: ${chain(q.front)}`);
100q.dequeue();
101q.dequeue();
102q.enqueue(9);
103console.log(`after emptying, enqueue(9): ${chain(q.front)}`);Use the head node as the top. Push creates a node whose next is the old top, then moves top to it. Pop saves the top value and moves top to top.next. Both are O(1) and need no traversal.
Enqueue must link the new node after the last one. Without rear you walk from front to find it, which is O(n). With rear, enqueue is rear.next = newNode, then rear = newNode.
No. When size equals capacity, the array must grow and copy its n elements first, so that one push costs O(n). Every other push is O(1).
Use circular indexing: keep front and size, and advance indices with (index + 1) mod capacity. Shifting every value left on dequeue also works, but it makes dequeue O(n).
Both give O(1) push and pop. The array reserves capacity C even when it holds fewer values and pays an O(n) copy on resize. The linked version allocates one node per element.
If dequeue moves front to null but leaves rear on the removed node, the next enqueue links from a node nobody can reach. Set rear to null whenever front becomes null.