Data structure - Stack

The underlying data structure for a stack can be either an array or a linked list. Stack data sctructures exhibit a first in last out (LIFO) characteristics. When messages 1,2,3 are pushed into the Stack, these messages can only be retrieved in the order of 3,2,1.

Stacks can be represented using an internal or linked list. Each implmentation has its uniue advantage/disadvantages. Since stacks do not allow un-ordered insertion/deletion, operations for insertion/deletion have constant time time complexity. O(1). In summary:

O(operation) O(1)
insertion Y(es)
deletion, e.g.: (pop) Y
peek Y

Stack array

Internally an array is used to store the data according to the array index. The ordered access of the array elements means that elements do not need to shifted when insertion/deletion occurs. The array keeps track of its current array position using tail.

array representation of a Stack

Psuedocode

Example of a stack array implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const Stack = () => {
let tail = -1; // reference to the "top" of store
const store = [];
size = () => store.length;
push = (value) => {
store[++tail] = value;
}
peek = () => {
if (tail > -1) {
store[tail];
}
}
pop = () => {
// Dereference the tail element.
// store[tail--] = undefined;
if (tail > -1) {
store[tail];
store.splice(tail, 1);
tail--;
}
}
print = () => console.log(store);
return { size, push, pop, peek, print }
}

(() => {
const stack = Stack();
stack.push(1); stack.push(2); stack.push(3);
stack.print(); // [1, 2, 3]

stack.pop(); stack.pop(); stack.peek();
stack.print(); // [1]
})();

Stack Linked List

Instead of using an internal array to store data, a Linked list implementation of a stack store data in nodes (objects). Each node object refernces the neighbouring node by “next” reference.

Linked list representation of a Stack

Psuedocode

Example of a Stack Linked list implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const node = (key, data) => {
return {
key: key,
data: data,
prev: null
}
}
const Stack = () => {
let key = 1; // reference to the "tail" of store
let tail;
size = () => tail ? tail.key : 0;
push = (value) => {
if (!tail) {
tail = node(key++, value);
}
else if (tail) {
const newNode = node(key++, value);
newNode.prev = tail;
tail = newNode;
}
}
peek = () => tail ? tail.data : -1;
pop = () => {
if (tail) {
tail = tail.prev;
return tail.data;
}
return -1;
}
print = () => {
let prevNode = tail;
while (prevNode) {
console.log(prevNode.data);
prevNode = prevNode.prev;
}
}
return { size, push, peek, pop, print }
}

(() => {
const stack = Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.print(); // 1, 2, 3
stack.pop();
stack.pop();
stack.peek();
stack.print(); // [1]
})();