In this blog, we would be learning How to implement Stack and reverse it in the javascript programming language.
Note: I have chosen Javascript language (my favourite) to implement it, language is just a medium here, we can implement it in any programming language. The key Idea is the underlying algorithm will always remain the same.
Before we dive into the coding part, let’s start with the definition of Stack.
Table of Contents
What is Stack?
Stack is a linear data structure that works on a principle of Last in First Out (popularly known as LIFO).
If you know about the Recursion where program control has to go deep (in downwards) and build the solution upward, as a result, the stack is the obvious choice for it.
Other problems where Stack suited the most –
- Checking if parenthesis is balanced or not
- Reversing array using stack
- expression computation
How to create Stack in Javascript?
Following primitive operation is supported by Stack data structure –
- push(value)
- pop()
- peek()
- is_empty()
Let’s define the Object prototype for the Stack and then implement each primitive operation.
Note: Stack can be implemented using Array, Queue, or Linked List. There is a catch though, in each implementation, we will have to implement its primitive operation in constant time. For simplicity, we would be using the array to create the Stack.
function Stack() {
this.arr = []; // to store the stack data
this.top = 0; // to point the top of the stack
}
Push(value) —
push function takes the argument value and inserts it to the top of the Stack.
Stack.prototype.push = function (value) {
this.arr[this.top] = value; // store the value at the top
this.top = this.top + 1; // increment top pointer
}
Time Complexity: O(1)
Space Complexity: O(1)
Pop() —
pop returns the top element of the stack after removing it.
Stack.prototype.pop = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var topEl = this.arr[this.top - 1];
this.top = this.top - 1;
this.arr.pop();
return topEl;
}
Time Complexity: O(1)
Space Complexity: O(1)
Peek() —
peek function doesn’t delete the data from the stack instead it just returns the top of the stack
Stack.prototype.peek = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
return this.arr[this.top - 1];
}
Time Complexity: O(1)
Space Complexity: O(1)
is_empty() —
is_empty function returns true if the stack is empty else false
Stack.prototype.is_empty = function () {
return this.top === 0;
}
Time Complexity: O(1)
Space Complexity: O(1)
Note: We can see all the primitive operations are taking constant time. So if we create the stack from other linear data structures then we have to make sure the primitive operations are constant time there too.
Let’s put all the code together –
function Stack() {
this.arr = []; // to store the stack data
this.top = 0; // to point the top of the stack
}
Stack.prototype.push = function (value) {
this.arr[this.top] = value; // store the value at the top
this.top = this.top + 1; // increment top pointer
}
Stack.prototype.pop = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var topEl = this.arr[this.top - 1];
this.top = this.top - 1;
this.arr.pop();
return topEl;
}
Stack.prototype.peek = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
return this.arr[this.top - 1];
}
Stack.prototype.is_empty = function () {
return this.top === 0;
}
How to reverse stack?
Approach 1 — Modify the original Stack
Pop element from stack one by one and store in the new string, this new string will be the reverse of the original string.
Let’s create a reverse function that reverses the stack and return the reversed string.
Stack.prototype.reverse = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var revStr = '';
while(!this.is_empty()) {
revStr += this.pop();
}
return revStr;
}
Time Complexity: O(n) → to process the complete stack
Space Complexity: O(n) → to store the n items in the string
Approach 2 — Keep the original Stack as it is
Since, with the Stack implementation, we have the reference of the stack arr which have the stack data. Now with the top pointer, we can loop over arr and store the reverse string and return.
Stack.prototype.reverseAlternate = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var revStr = '';
for (var i = this.top - 1; i >= 0; i--) {
revStr += this.arr[i];
}
return revStr;
}
Time Complexity: O(n) → to process the stack data residing in arr
Space Complexity: O(n) → to store the n items in the string
Combining all code together with an example –
function Stack() {
this.arr = [];
this.top = 0;
}
Stack.prototype.push = function (val) {
this.arr[this.top] = val;
this.top = this.top + 1;
}
Stack.prototype.pop = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var topEl = this.arr[this.top - 1];
this.top = this.top - 1;
this.arr.pop();
return topEl;
}
Stack.prototype.is_empty = function () {
return this.top === 0;
}
Stack.prototype.reverse = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var revStr = '';
for (var i = this.top - 1; i >= 0; i--) {
revStr += this.arr[i];
}
return revStr;
}
Stack.prototype.reverseV1 = function () {
if (this.is_empty()) {
throw new Error("Underflow, stack is empty");
}
var revStr = '';
while(!this.is_empty()) {
revStr += this.pop();
}
return revStr;
}
var stack = new Stack();
stack.push('a');
stack.push('b');
stack.push('c');
console.log(stack.reverse()); // cba
console.log(stack.reverseV1()); // cba
Approach 3 — Reverse the original Stack (using only stacks)
It should be clear that reversing the stack can’t be done in O(1) space complexity.
Let’s dig more to cover the following interesting scenarios –
If it is asked to reverse the original stack without using other linear data structures except for stack.
With array reversing stack is straightforward, but we are not allowed to use it, however, we can use n number of stacks to solve it but can’t use other linear data structures.
e.g
lets reverse stack1 = [1, 2, 3, 4, 5]
pop each element to other stack, let’s say stack2
stack2 = [5, 4, 3, 2, 1]
It should be clear that popping each element from stack2 and pushing to stack1 will result in the original stack1.
Let's use one more stack, say stack3
pop each element from stack2 to stack3
stack3 = [1, 2, 3, 4, 5]
Now popping each element from the stack3 to stack1 will reverse the stack1.
So, to reverse a stack using other stacks, we need atleast 2 stacks.
This question is generally asked in many interviews in the data structure round.
Time Complexity: O(n) → to process the stack
Space Complexity: O(n) → to store the items in the other stacks
Want to build a quote generator using javascript?
Recommended books for further reading –
Please share the articles on –
The latest tips and news from the industry straight to your inbox!
Join 30,000+ subscribers for exclusive access to our monthly news and tutorials!
This is really insightful, thanks for the article!