Stack
A stack is an abstract data type representing a collection of values, with elements added and removed according to the last in, first out (LIFO) principle.
Elements may be pushed (inserted) or popped (removed) from the same end of the stack (the top). The stack may also be peeked (retrieving the element at the top without removing it).
Common operations
| Name | Description |
|---|---|
size() |
gets the number of elements stored in the stack |
peek() |
gets the element at the top of the stack |
dequeue() |
removes and returns the element at the top of the stack |
enqueue(e) |
inserts element e at the top of the stack |
Singly-linked list implementation
A stack may be implemented by adapting a singly-linked list , which allows for $\mathcal{O}(1)$-time access, insertion, and deletion at the head of the list.
1public class LinkedStack<E> implements StackADT<E> {
2 private final SinglyLinkedList<E> list = new SinglyLinkedList<>();
3
4 public int size() { return list.size(); }
5
6 public boolean isEmpty() { return list.isEmpty(); }
7
8 public E peek() { return list.first(); }
9
10 public void push(E e) { list.addFirst(e); }
11
12 public E pop() { return list.removeFirst(); }
13}
Array-based implementation
A stack may also be implemented using either a static or dynamic array .
In the following dynamic array implementation, the top of the stack is tracked as the index of the last element of the array. Using the end of the array as the top of the stack allows for both insertion and deletion to occur in $\mathcal{O}(1)$-time.
1public class ArrayStack<E> implements StackADT<E> {
2 public static final int DEFAULT_CAPACITY = 16;
3
4 private E[] data;
5 private int top = -1;
6
7 public ArrayStack() { data = (E[]) new Object[DEFAULT_CAPACITY]; }
8
9 public int size() { return isEmpty() ? 0 : top + 1; }
10
11 public boolean isEmpty() { return top < 0; }
12
13 public E peek() {
14 if (isEmpty()) return null;
15 return data[top];
16 }
17
18 public void push(E e) {
19 if (size() == data.length) resize(data.length * 2);
20 data[++top] = e;
21 }
22
23 public E pop() {
24 if (isEmpty()) return null;
25 var result = data[top];
26 data[top--] = null;
27 return result;
28 }
29
30 private void resize(int capacity) {
31 var resizedData = (E[]) new Object[capacity];
32 for (int i = 0; i <= top; i++) { resizedData[i] = data[i]; }
33 data = resizedData;
34 }
35}