A stack is Last-In-First-Out (LIFO) data structure in which only the top element can be accessed. The data is added by push and removed by pop on top. The operation of push, pop and peek all have O(1) complexity. Stack can be implemented with array, linked list. This is stack implemented using array.
Part 1 – Stack implementation using array
Part 2 – Stack implementation using linked list
Table of Content
Push
To push an element in stack is to add element at the next available spot in array. First we need to define an array. In Java, if you use array (not ArrayList), you have to specify the maxSize of the array. If the array reaches the maxSize, we cannot add more element. The variable top is the index of the last element added.
Java
|
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 |
public class StackArray<T> { private int maxSize; private T[] stackArray; private int top; //Constructor, Time O(1), Space O(1) @SuppressWarnings("unchecked") public StackArray(int capacity) { maxSize = capacity; stackArray = (T[]) new Object[maxSize]; top = -1; } //Push at the top, Time O(1), Space O(1) public void push(T value) { if (isFull()) { System.out.println("stack reach max size, cannot push"); return; } stackArray[++top] = value; } //Check full, Time O(1), Space O(1) private boolean isFull() { return length == maxSize-1; } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 |
class StackArray { constructor() { this.stackArray = []; //array } //Push at the top, Time O(1), Space O(1) push(value) { this.stackArray.push(value); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Stack : # Constructor, Time O(1), Space O(1) def __init__(self, size) : self.top_index = -1 self.stack = [None]*size self.max_size = size # Push at the top, Time O(1), Space O(1) def push(self, value): if self.is_full(): print ("Reach max size, cannot add.") return self.top_index += 1 self.stack[self.top_index] = value # Check full, Time O(1), Space O(1) def is_full(self): return self.top_index == self.max_size -1 |
Doodle
Pop
To pop an element is to remove the last element in the array. First we check whether the stack is empty. If it is empty, the method should return. In Java array implementation, we return the element at index of top, then decrease top by 1. Please note the element is still in array until you replace with other element or remove array from the memory.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//Remove from the top, Time O(1), Space O(1) public T pop() { if (isEmpty()) { System.out.println("stack is empty, cannot pop"); return null; } return stackArray[top--]; } //Check empty, Time O(1), Space O(1) public boolean isEmpty() { return top == -1; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//Return the top value, Time O(1), Space O(1) pop(){ if (this.isEmpty()) { console.log("stack is empty, cannot pop"); return null; } return this.stackArray.pop(); } //Check empty, Time O(1), Space O(1) isEmpty() { return this.stackArray.length == 0; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 |
# Remove from the top, Time O(1), Space O(1) def pop(self): if self.is_empty(): print("stack is empty, cannot pop") return None top_item = self.stack[self.top_index] self.top_index -= 1 return top_item # Check empty, Time O(1), Space O(1) def is_empty(self): return self.top_index == -1 |
Peek
Peek is to return the value of element at top position. The same as pop, we should check whether the stack is empty. If it is not empty, return the value.
Java
|
1 2 3 4 5 6 7 8 |
//Return the top value, Time O(1), Space O(1) public T peek() { if (isEmpty()) { System.out.println("stack is empty, no value return"); return null; } return stackArray[top]; } |
Javascript
|
1 2 3 4 5 6 7 8 |
//Return the top value, Time O(1), Space O(1) peek() { if (this.isEmpty()) { console.log("stack is empty, no value return"); return null; } return this.stackArray[this.stackArray.length - 1]; } |
Python
|
1 2 3 4 5 6 |
#Return the top value, Time O(1), Space O(1) def peek(self): if self.is_empty(): print("stack is empty, no value return") return None return self.stack[self.top_index] |
Print
Print is to print all elements in stack starting from top. A for loop is used to iterate through the array from last to first.
Java
|
1 2 3 4 5 6 7 8 |
//print all element starting from top, //Time O(n), Space O(1), n is number of items in stack public void print() { System.out.print("stack: "); for (int i = top; i >= 0; i--) System.out.print(stackArray[i] + " "); System.out.println(); } |
Javascript
|
1 2 3 4 5 6 7 |
//print all, Time O(n), Space O(1), n is number of items in stack print(){ var str = "stack: "; for (var i = this.stackArray.length-1; i >=0; i--) str += this.stackArray[i] + " "; console.log(str); } |
Python
|
1 2 3 4 5 |
#print all, Time O(n), Space O(1), n is number of items in stack def print(self) : for i in range (self.top_index, -1, -1): print(self.stack[i], end= " ") print() |
Download Java, JavaScript and Python code
Data structures and Java collections
What is the difference between a stack and a call stack?
A stack is a Last-In-First-Out data structure. The last item added to a stack will be the first one to be removed.
A call stack is a stack data structure used by computer programs to keep track of the sequence of function calls.