The stack data structure is another linear dynamic set of entities in a specific sequence. It has an important restriction though, insertions (push as we use it here) and deletions (pop as we use it here) must be performed in only one position, namely the top of the stack.
Those names are allusions to physical stacks (as a stack of plates in a kitchen). This analogy can help us to understand why the insertion and deletion are done in only one position, the top: the top plate is the only accessible, and as it was the last to be pushed it’s also the only one that can be popped out.
Thus, stacks implement the LIFO policy (i.e., last-in, first-out).
The Stack fundamental operations are insertion (i.e., push), deletion (i.e., pop), and peek.
As queues, stacks cannot be accessed via index (not even to search if the stack has a value). You would have to delete and get the element as many times as you need. However, this can be synthetically done with an auxiliary buffer to avoid modifications to the stack.
Stack Nodes
The following is the implementation of the Stack Node.
1class StackNode {
2 constructor(value, next = null) {
3 this.value = value
4 this.next = next
5 }
6}
This implementation by itself won’t let us simulate the stack. To actually have a stack, we need the Stack Wrapper.
The Stack (Wrapper)
Let’s use a basic implementation of the Stack wrapper to see how using it in conjunction with the StackNode will set the stack. You might have noticed that the stack wrapper has only a reference to the stack head, but there is no tail reference as there is no operation in the stack that requires a tail.
Note: I’ll be changing the Stack implementation to explain better, in a concise manner each operation. The full implementation of the StackNode, the Stack, the StackNode and the Stack tests can be checked for further analysis.
1class BasicStack {
2 constructor() {
3 this.head = null;
4 this.size = 0;
5 }
6
7 push(value) {
8 const node = new StackNode(value, this.head);
9 this.head = node;
10 this.size++;
11 return this;
12 }
13
14 toString() {
15 const nodes = [];
16
17 let currentNode = this.head;
18 while(currentNode) {
19 nodes.push(currentNode.value);
20 currentNode = currentNode.next;
21 }
22 nodes.push("null")
23 return nodes.join('\n||\n\\\/\n')
24 }
25}
Let’s test the previous basic stack wrapper.
1stack = new BasicStack();
2stack
3 .push(1)
4 .push(2)
5 .push(3)
6 .push(4)
7 .push(5);
8
9console.log("Stack:\n", stack.toString(), "\n");
Stack:
5
||
\/
4
||
\/
3
||
\/
2
||
\/
1
||
\/
null
Operations
stack.push
Push is the insertion operation for stacks. The insertion occurs at the top of the stack. When the stack is empty the insertion adds a stack node and the wrapper tracks it in the head of the wrapper.
As more stack nodes are pushed into the stack, the wrapper makes its current head the new stack node’s next and then it moves the reference to the new node. By doing this we always keep the head at the top of the stack, and the stack size increases by one.
Pushing has $O(1)$ time complexity because the node is always added at the top of the stack.
stack.pop
Pop is the deletion operation for stacks. The deletion occurs at the top of the stack as well. When the stack is empty we return a null reference and there is no deletion at all. On the other hand, when the stack has elements, the head reference goes to its current next, and the head is returned to the caller. This reduces the stack size by one.
Popping has $O(1)$ time complexity too because the head reference is moved to the next node and the reference to the old head is returned.
1class StackWithPushAndPop {
2 constructor() {
3 this.head = null;
4 this.size = 0;
5 }
6
7 push(value) {
8 const node = new StackNode(value, this.head);
9 this.head = node;
10 this.size++;
11 return this;
12 }
13
14 pop() {
15 if (!this.head) return null;
16
17 const poppedNode = this.head;
18 this.head = this.head.next;
19 poppedNode.next = null;
20 this.size--;
21
22 return poppedNode.value;
23 }
24
25 toString() {
26 const nodes = [];
27
28 let currentNode = this.head;
29 while(currentNode) {
30 nodes.push(currentNode.value);
31 currentNode = currentNode.next;
32 }
33 nodes.push("null")
34 return nodes.join('\n||\n\\\/\n')
35 }
36}
1stack = new StackWithPushAndPop();
2stack
3 .push(1)
4 .push(2)
5 .push(3)
6 .push(4)
7 .push(5);
8
9console.log("Stack:\n", stack.toString(),"\n");
10
11console.log("Popped value: ", stack.pop(), "\n");
12
13console.log("Stack:\n", stack.toString(),"\n");
Stack:
5
||
\/
4
||
\/
3
||
\/
2
||
\/
1
||
\/
null
Popped value: 5
Stack:
4
||
\/
3
||
\/
2
||
\/
1
||
\/
null
stack.peek
The peek function looks at the head of the stack without popping it out from the stack. With this operation, we always have a way to look at the head value. No matter how many elements are stacked, this operation will always look to the head.
1class StackWithPeek {
2 constructor() {
3 this.head = null;
4 this.size = 0;
5 }
6
7 push(value) {
8 const node = new StackNode(value, this.head);
9 this.head = node;
10 this.size++;
11 return this;
12 }
13
14 peek() {
15 if (!this.head) return null;
16 return this.head.value;
17 }
18
19 toString() {
20 const nodes = [];
21
22 let currentNode = this.head;
23 while(currentNode) {
24 nodes.push(currentNode.value);
25 currentNode = currentNode.next;
26 }
27 nodes.push("null")
28 return nodes.join('\n||\n\\\/\n')
29 }
30}
1stack = new StackWithPeek();
2stack
3 .push(1)
4 .push(2)
5 .push(3)
6 .push(4)
7 .push(5);
8
9console.log("Peeking:", stack.peek());
Peeking: 5
Runtime Complexity Overview
| Operation | Runtime Complexity |
|---|---|
| Push | $O(1)$ |
| Pop | $O(1)$ |
| Peek | $O(1)$ |
Space Complexity
Stacks have $O(n)$ space complexity.