Stacks: Balanced Brackets
Stacks
A stack is a data structure that uses a principle called Last-In-First-Out (LIFO), meaning that the last object added to the stack must be the first object removed from it.
At minimum, any stack should be able to perform the following three operations:
- Peek: Return the object at the top of the stack (without removing it).
- Push: Add an object passed as an argument to the top of the stack.
- Pop: Remove the object at the top of the stack and return it.
The diagram below demonstrates these simple operations on a stack:
In addition, it's often helpful to implement a method to check whether or not a stack is empty to ensure you are not attempting to perform peek or pop operations on an empty stack.
Sample Java Implementation
EXAMPLE
The code below demonstrates a simple Java Stack implementation.
x
1
import java.util.*;
2
3
class Stack<E> {
4
5
private class Element<E> {
6
// The data value of the element
7
private E data;
8
// The next element in the stack
9
private Element<E> next;
10
11
Element(E data) {
12
this.data = data;
13
this.next = null;
14
}
15
}
16
17
// The element at the top of the stack
18
private Element<E> top;
19
20
/** Create an empty stack **/
21
public Stack() {
22
this.top = null;
23
}
24
25
/** @return true if the stack is empty, false if it is not.
26
**/
27
public boolean isEmpty() {
28
return top == null;
29
}
30
31
/**
32
Pushes a value onto the top of the stack.
33
@param value The data for the stack's new top element.
34
**/
35
public void push(E value) {
36
// Create new top element
37
Element<E> newTop = new Element<E>(value);
38
39
// If the stack is not empty
40
if(!isEmpty()) {
41
// Set old top's next variable to point to new top
42
newTop.next = top;
43
}
44
45
// Set new top regardless of whether or not stack is empty
46
this.top = newTop;
47
}
48
49
/**
50
Remove the element at the top of the stack.
51
@return the data associated with the stack's topmost element being removed.
52
@throws EmptyStackException if the stack contains no elements.
53
**/
54
public E pop() {
55
if(isEmpty()) {
56
throw new EmptyStackException();
57
}
58
59
Element<E> oldTop = top;
60
this.top = top.next;
61
62
return oldTop.data;
63
}
64
65
/**
66
'View' the element at the top of the stack.
67
@return the data associated with the stack's topmost element.
68
@throws EmptyStackException if the stack contains no elements.
69
**/
70
public E peek() {
71
if(isEmpty()) {
72
throw new EmptyStackException();
73
}
74
75
return top.data;
76
}
77
}
78
79
class StackDemo {
80
public static void main(String[] args) {
81
Stack<Integer> intStack = new Stack<Integer>();
82
83
try {
84
intStack.pop();
85
}
86
catch(EmptyStackException e) {
87
System.out.println("We cannot pop off an empty stack.");
88
}
89
90
for(int i = 0; i < 4; i++) {
91
intStack.push(i);
92
System.out.println("New Top: " + intStack.peek());
93
}
94
for(int i = 0; i < 4; i++) {
95
System.out.println("Popped: " + intStack.pop());
96
}
97
98
try {
99
intStack.peek();
100
}
101
catch(EmptyStackException e) {
102
System.out.println("We cannot peek at an empty stack.");
103
}
104
}
105
}
Output
Table Of Contents
Related challenge for Stacks