An array is the simplest storage for a stack. The elements sit in the array from the bottom of the stack (index 0) upwards, and one integer, top, remembers where the top element is. Every stack operation then becomes a single array access plus a change to top.
A stack can be built on an array or on a linked list. This page shows the array version; the linked-list version has its own tutorial.
Stack implementation using Array in Java
The class below stores up to 100 int values:
topstarts at-1, meaning the stack is empty.push()checks for overflow, incrementstopand stores the value atarray[top].pop()checks for underflow, readsarray[top]and decrementstop.peek()readsarray[top]without changingtop.
The class is called IntStack so that it is not confused with java.util.Stack.
// A fixed-capacity stack of int values backed by an array
class IntStack {
private final int capacity = 100; // maximum number of items
private final int[] array; // storage for the items
private int top; // index of the top item, -1 when empty
IntStack() {
array = new int[capacity];
top = -1;
}
// true when the stack holds no items
boolean isEmpty() {
return top == -1;
}
// true when every slot of the array is used
boolean isFull() {
return top == capacity - 1;
}
// Adds an item on top of the stack
void push(int item) {
if (isFull()) {
System.out.println("Stack is full, cannot push " + item + ".");
return;
}
array[++top] = item; // move top up, then store the item
System.out.println(item + " pushed into the stack.");
}
// Removes the top item
void pop() {
if (isEmpty()) {
System.out.println("Stack is empty, cannot pop.");
return;
}
int item = array[top--]; // read the item, then move top down
System.out.println(item + " popped from the stack.");
}
// Shows the top item without removing it
void peek() {
if (isEmpty()) {
System.out.println("Stack is empty, nothing to peek.");
return;
}
System.out.println("Stack top item: " + array[top]);
}
// Prints the items from top to bottom
void printStack() {
System.out.print("Stack Items:");
for (int i = top; i >= 0; i--) {
System.out.print(" " + array[i]);
}
System.out.println();
}
}
public class StackUsingArray {
public static void main(String[] args) {
IntStack stack = new IntStack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.pop();
stack.peek();
stack.printStack();
}
}
10 pushed into the stack. 20 pushed into the stack. 30 pushed into the stack. 40 pushed into the stack. 40 popped from the stack. Stack top item: 30 Stack Items: 30 20 10
Time complexity: O(1) for push, pop, peek, isEmpty and isFull.
Space complexity: O(n), where n is the capacity of the array; the whole array is allocated up front, even when the stack holds few items.