A stack is a 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. A stack can be implemented with an array or a linked list. This post is to implement a stack using an array.
Part 1 – Stack implementation using an array
Part 2 – Stack implementation using linked list
Table of Content
Implement a stack using an array method – Push
To push an element in the stack is to add an element at the next available spot in the array. First, we need to define an array. In Java, if you use an array (not ArrayList), you have to specify the maxSize of the array. If the array reaches the maxSize, we cannot add more elements. 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
Implement a stack using an array method – 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 the index of the top, then decrease the top by 1. Please note the element is still in the array until you replace it with another element or remove the 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 |
Implement a stack using an array method – Peek
Peek is to return the value of the element at the 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 the stack starting from the 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.