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 a linked list.
Part 1 – Stack implementation using an array
Part 2 – Stack implementation using a linked list
Table of Content
Implement a stack method – Push
Using a 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 the 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
Implement a stack method – 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 |
Implement a stack method – 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 the stack. Starting from the 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
Why a stack is an abstract data type?
An abstract data type (ADT) refers to 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 the outside. A stack is an ADT because it can be implemented using either an array or a linked list.