Introduction
What comes to your mind when you hear a word stack?
Stack of books? yes, Pringles? yes.
What makes it special is the order in which we eat pringle. We always start with a pringle on the top, and one by one we start consuming more till we reach the last one at the bottom of the box.
This order is called LIFO. Last In First Out.
The question is, where in programming do we follow this order, LIFO. Answer is every damn time.
Every time you code, you are following LIFO to maintain the order of Parentheses. Take this code for example.
class parentheses
{
constructor(elements = [])
}
Listing 1: Sample code
Following is the same code only with parentheses.
{
(
[]
)
}
Listing 2: Parentheses
Look closely, In listing 2, there is a pattern. First opening curly brace "{" is the last to be closed "}". Second round parenthesis "(" only second last to be closed ")" and same goes for square bracket "[ ]".
Another real world application of stack would be Undo and Redo features.
Stack has a list of operations that we need to build.
- Push: Adds an element at the top of the stack.
- Pop: Removes the element from the top of the stack and returns it.
- Peek: Shows the top element from the stack.
- Size: Returns the size of the stack.
- IsEmpty: Returns true if stack is empty else returns false.
- Print stack: Bonus operation.
The Implementation
Stacks can be implemented using Array and LinkedList both,
- The elements in an array are stored in a linear fashion next to each other which offers cache locality, due to which it makes them faster while accessing its items. But there is a drawback too, Arrays are going to double their size as soon as it exhausts their assigned limit.
- With Linkedlist we can add elements dynamically, and size will increase dynamically while the drawback of using linkedlist is it has items linearly stored yes but nodes are scattered across the memory and they are linked with pointers so it has extra overhead of pointers to carry.
Common Data Structure Operations
Stacks only have one entry point and one exit point. So all that matters is insertion and deletion complexity.
In Array, we need to insert or delete an element at the top of the array which means at the last position, In linkedlist we only have to deal with the head node.
Array Vs LinkedList
| Data Structures |
Insert element at last index / Head Node |
Delete element from the last index / Head Node |
|
Space Complexity |
| Stack operations |
Push/Enqueue |
Pop / Dequeue |
Peek |
|
| Array |
O(1) |
O(1) |
O(1) |
O(n) |
| LinkedList |
O(1) |
O(1) |
O(1) |
O(n) |
Approach 1: Implement a Stack using LinkList.
First we obviously need a Node class.
class Node{
constructor(value){
this.value = value,
this.next = null
}
}
Listing 3: class Node
Next, we need a stack class and stack has 3 properties.
- Top: the top node of a stack
- Botton: the bottom or last node of a stack
- Length: length of a stack
class Stack{
constructor(){
this.top = null,
this.bottom = null,
this.length = 0
}
}
Listing 4: class stack
Push operation
Let's start with the Push method, what we need to do is, we need to add a new head to the linkedlist. If you want to learn how to add a new head in detail then visit this article.
Following are the series of steps we are going to perform in each iteration.
Iteration 1:
Length = 1
Top = Bottom = 1
Iteration 2:
CurrentTop: 1
NewTop : 2
NewTop.next : 1
Length = 2
List : 2 -> 1
Iteration 3:
CurrentTop : 2
NewTop : 3
NewTop.next : 2
Length = 3
List : 3 -> 2 -> 1
Code snippet to insert a new head node,
push(value) {
var newTopNode = new Node(value);
if (this.length === 0) {
this.top = newTopNode;
this.bottom = newTopNode;
} else {
const tempNode = this.top;
this.top = newTopNode;
this.top.next = tempNode;
}
this.length++;
return this;
}
Listing 5: Push method
Pop operation
We need to pop the top element from the stack and in this scenario, we need to remove the head element.
Let's remove 3 and 2 from the stack.
Iteration 1: Current List: 3 -> 2 -> 1
CurrentTop : CurrentTop.next
NewTop: 2
Length = 2
Iteration 2: Current List: 2 -> 1
CurrentTop : CurrentTop.next
NewTop: 1
Length = 1
Code snippet to remove a head node.
pop(){
if(!this.top){
return null;
}
if(this.top === this.bottom){
this.bottom = null;
}
this.top = this.top.next;
this.length--;
return this;
}
Listing 6: Pop method
Peek, IsEmpty, Size operations
peek() {
return this.top;
}
isEmpty() {
return this.length === 0;
}
size() {
return this.length;
}
Listing 7: Peek, IsEmpty, Size methods
Bonus method for you guys, Let's print this linkedlist in pretty print.
printList() {
//Creates an empty array.
let printArrayList = [];
//Pointer which points to the head node
let currentNode = this.top;
//Start iterating from the first node till you reach the last node
while (currentNode !== null) {
//Add every node's value to the array
printArrayList.push(currentNode.value);
//Point pointer to the next node
currentNode = currentNode.next;
}
//Return the array
return printArrayList.join(' -> ');
}
Listing 8: PrintList method
Listing 9 is the entire code snippet for stack.
class Node {
constructor(value) {
this.value = value,
this.next = null
}
}
class Stack {
constructor() {
this.top = null,
this.bottom = null,
this.length = 0
}
push(value) {
var newTopNode = new Node(value);
if (this.length === 0) {
this.top = newTopNode;
this.bottom = newTopNode;
} else {
const tempNode = this.top;
this.top = newTopNode;
this.top.next = tempNode;
}
this.length++;
return this;
}
pop() {
if (!this.top) {
return null;
}
if (this.top === this.bottom) {
this.bottom = null;
}
this.top = this.top.next;
this.length--;
return this;
}
peek() {
return this.top;
}
isEmpty() {
return this.length === 0;
}
size() {
return this.length;
}
printList() {
//Creates an empty array.
let printArrayList = [];
//Pointer which points to the head node
let currentNode = this.top;
//Start iterating from the first node till you reach the last node
while (currentNode !== null) {
//Add every node's value to the array
printArrayList.push(currentNode.value);
//Point pointer to the next node
currentNode = currentNode.next;
}
//Return the array
return printArrayList.join(' -> ');
}
}
var books = new Stack();
books.push(10);
console.log(books.printList());
books.push(20);
console.log(books.printList());
books.push(30);
console.log(books.printList());
books.pop();
console.log(books.printList());
books.pop();
console.log(books.printList());
Listing 9: stack
Run the code and see if all functions are working properly.
![]()
Figure 1: Output of listing 9
Approach 2: Implement a Stack using Array.
This code is easy on the eyes because there is hardly anything to code. We are going to leverage most of the functions of array and that's it.
class Stack {
constructor() {
this.elements = []
}
push(value) {
this.elements.push(value);
}
pop() {
this.elements.pop();
return this;
}
peek() {
return this.elements[this.elements.length - 1];
}
}
Listing 10: Stack with array
Summary
In this article, we learned what stack is, where it's been used, How to implement its various operations with linkedlist and array. In the next article, we will understand how to code to validate parentheses in a program.