Stack is also a type of LinkedList, but without the ability to retrieve i-th element. We can only retrieve (pop) the last added element and add (push) a new element to the top of the stack (LIFO approach).
General points of the algorithm:
- Implement the push() method to add an element to the top of the stack. Store the last previous element (tail) in the “prev” property of the new tail.
- Implement the pop() method: retrieve the tail node and reassign the tail to the previous element.
- Time complexity: O(1) for the push() and pop() methods.
- Space complexity: O(1) for the push() and pop() methods.
public class ImplementStack {
private static class Stack<T> {
private Node<T> tail;
private static class Node<T> {
private final T value;
private Node<T> prev;
public Node(T value, Node<T> prev) {
this.value = value;
this.prev = prev;
}
}
public void push(T value) {
var node = new Node<>(value, null);
if (tail != null) {
node.prev = this.tail;
}
this.tail = node;
}
public T pop() {
if (this.tail == null) {
throw new IllegalArgumentException("The stack is empty");
}
var node = this.tail;
this.tail = this.tail.prev;
return node.value;
}
}
public static void main(String[] args) {
var stack = new Stack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}