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 post is stack implemented using linked list.
Part 1 – Stack implementation using array
Part 2 – Stack implementation using linked list
Table of Content
Push
Using linked list, first we need to define a stack node. This class has variables of data and next. Next we define the stack class. It has two class variables: top and length. top is a pointer to the top node. length is to track the length of the list. To push an element in stack is to add a node with the data at the front of the list.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class StackNode<T> { protected T data; protected StackNode<T> next = null; //Constructor, Time O(1), Space O(1) public StackNode(T value) { this.data = value; } } public class StackList<T> { private int length = 0; private StackNode<T> top = null; //Push at the top, Time O(1), Space O(1) public void push(T value) { StackNode<T> newNode = new StackNode<T> (value); newNode.next = top; top = newNode; length++; } } |
Javascript
|
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 |
class StackNode { //Constructor, Time O(1), Space O(1) constructor (value, next) { this.data = value this.next = null } } // Create Stack Using Linked list class StackList { //Constructor, Time O(1), Space O(1) constructor () { this.length = 0; this.top = null } //Push at the top, Time O(1), Space O(1) push(value) { var newNode = new StackNode(value) newNode.next = this.top this.top = newNode this.length++; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class StackNode: #Constructor, Time O(1), Space O(1) def __init__(self, data): self.data = data self.next = None class StackList: #Constructor, Time O(1), Space O(1) def __init__(self): self.top = None self.length = 0 #Push at the top, Time O(1), Space O(1) def push(self, value): newNode = StackNode(value) newNode.next = self.top self.top = newNode self.length += 1 |
Doodle
Pop
First we check whether the stack is empty. If it is empty, the method should return. In this implementation, to pop an element is to move the top pointer to the next node. The popped node is still in the list until the linked list is removed from the memory.
Java
|
1 2 3 4 5 6 7 8 9 10 11 |
//Remove from the top, Time O(1), Space O(1) public T pop() { if (top == null) { System.out.println("stack is empty, cannot pop"); return null; } StackNode<T> node = top; top = top.next; length--; return node.data; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 |
//Remove from the top, Time O(1), Space O(1) pop() { if (this.top == null) { console.log("stack is empty, cannot pop"); return null; } var node = this.top this.top = this.top.next node = null this.length--; } |
Python
|
1 2 3 4 5 6 7 8 9 |
#Remove from the top, Time O(1), Space O(1) def pop(self): if self.top == None: print("stack is empty, cannot pop") return node = self.top self.top = self.top.next self.length -= 1 return node.data |
Peek
Peek is to return the value of the top node. 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 (top == null) { System.out.println("stack is empty, no value return"); return null; } return top.data; } |
Javascript
|
1 2 3 4 5 6 7 8 |
//Return the top value, Time O(1), Space O(1) peek() { if (this.top == null) { console.log("stack is empty, no value return"); return null; } return this.top.data; } |
Python
|
1 2 3 4 5 6 |
#Return the top value, Time O(1), Space O(1) def peek(self): if self.top == None: print("stack is empty, cannot pop") return return self.top.data |
Print
Print is to print all elements in stack. Starting from top, a while loop is used to iterate through each node in the list.
Java
|
1 2 3 4 5 6 7 8 9 10 |
//print all, Time O(n), Space O(1), n is number of items in stack public void print() { System.out.print("stack: "); StackNode<T> node = top; while (node != null) { System.out.print(node.data + " "); node = node.next; } System.out.println(); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 |
//print all, Time O(n), Space O(1), n is number of items in stack print() { var str = "stack: "; var node = this.top while(node != null) { str += node.data + " "; node = node.next } console.log(str); } |
Python
|
1 2 3 4 5 6 7 8 |
#print all, Time O(n), Space O(1), n is number of items in stack def print(self) : line = "stack: " node = self.top while node != None: line += str(node.data) + " " node = node.next print(line) |
Download Java, JavaScript and Python code
Data structures and Java collections
What it means that a stack is an abstract data type?
An abstract data type (ADT) refers a class that defines the behavior of a data structure without specifying its implementation. The underlying mechanism used to implement them is not visible to outside.
A stack is an ADT because it can be implemented using either an array or a linked list.