Stack Data Structure
3 min readNov 16, 2022
Part 1: How To Implement A Stack Using Arrays
Stack is a data structure that follows the Last-In/First-Out principle(popularly known as LIFO), meaning the most recently added element is the first to remove.
List of Stack Operations
//Add an item in the stack
.push()
//Remove an item from the end of the stack
// if the stack is empty, this method will return undefined
.pop()
//Return the top element of the stack
.peek() or .top()
//Check to see if stack is empty.
//Returns true if the stack is empty
.isEmpty()
//Check to see if the stack is full.
// Used when you have placed a limit on the data
.isFull()
//Removes all the data from the stack
.clear()
Implement Stack Using Array
class Stack {
constructor(){
this.items =[];
}
// add an element
push(element){
this.items.push(element)
}
// remove an element
pop(){
return this.items.pop()
}
// return the number of elements
size(){
return this.items.length
}
// view the last element
peek(){
return this.items[this.items.length - 1];
}
// deletes all elements
clear(){
this.items.length = 0;
console.log("Stack is cleared")
}
// check to see if stack is empty
isEmpty(){
return this.items.length === 0;
}
}
//create new instance of stack class
let stack1 = new Stack()
stack1.push(10)
stack1.push(20)
stack1.push(30)
Time Complexity:
Space Complexity: O(N)
Applications of Stack Data Structure
Example 1: Reverse A String
const reverse = (string) =>{
let stack = [];
// push each element to stack as you iterate through string
for(let i =0; i < string.length; i++){
stack.push(string[i]);
}
//pop each element from the stack and store it into a variable
let reversedString = '';
while(stack.length > 0){
reverseString += stack.pop();
}
return reversedString
}
//TIME COMPLEXITY: 0(N)
//SPACE COMPLEXITY: 0(N)
Example 2: Check Valid Parenthesis
//check to see if every open bracket in a string
//has a corresponding closing bracket
//Process
//create a hashMap that contains the different types of bracket
// along with their corresponding closing bracket
// define a stack and set it equal to an empty array
// loop through each character of the given string
// if the character matches any key in the hashMap
// push its value to the empty stack
// Else if the character matches the last element of the stack
// check to make sure stack is not empty
// remove the last element from the stack
// Else, return false
// meaning the character doesn't match the element at the top of stack
// Once you have looped through all the characters in the given string
//return true if the length of the stack if equal to 0
const isValid = (s) => {
const hashMap = {"(":")",
"{": "}",
"[": "]"
}
let stack =[];
for( let char of s){
if (hashMap[char]){
//character is an open bracket
stack.push(hashMap[char])
} else if(stack.length > 0 && stack[stack.length - 1] === char){
//character is a closing bracket and the top of the stack matches
stack.pop()
} else {
//character is a closing brack and the top of the stack doesnt match
return false
}
}
//will return true if the length of the stack is equal to 0
return stack.length === 0
}
//TIME COMPLEXITY: 0(N)
//SPACE COMPLEXITY: 0(N)
Check out Part 2: How To Implement A Stack Using Linked List
Citation