(Updated September 3, 2024)
Table of contents
Overview
This section expands linked lists. Remember that each data structure shown here is still a linked list. What is changing are the rules that govern how the object may be manipulated.
Stacks
Overview
Stacks are a wondrous structure. This is mainly because they are nothing more than a linked list. Well, if they are nothing more than a linked list, why do we call them stacks? The underlying structure is a linked list, but how we enforce its use makes it a stack.
For example, let us say we need to call a series of methods, which will call more methods, and those methods call even more, and so on. When a method calls a method that calls another method, we need a way to return to the previous method and then to the previous method before that. Of course, we think of the return statement, and all is well. The ability to call a method and later use a return statement only frees us of the knowledge and responsibility of stack management for so long.
Imagine ourselves on the cafeteria line or at our favorite buffet. As we enter the line at the end, we form a queue (see Queues discussion). And the queue rules define how we enter at the back of the line and exit at the front. (There are no such rules for governing a generic linked list.) We come upon a pile of plates, or rather a stack of plates. Each person in the line (queue) takes a plate from the top.
Now imagine that in the kitchen, someone is washing the plates. This person starts with no plates, and the rapid-cleaning dishwasher has many cleaned plates. The person at this station then removes plates from the dishwasher and places them one atop another.
It is these actions that define the purpose and use of a stack, which we will now describe.
Stack Operations
Recall that a stack is nothing more than a linked list. The actions we allow on this linked list are what make it special. To place an object on the stack is to push onto the stack. To remove an object from the stack is to pop the stack. All push and pop actions may only occur at the top of the stack. We may inspect the value at the top of the stack without actually popping it off. Any actions within the stack are prohibited.
Using our linked list code as a foundation, we will now define a stack in Java. Example 1a has some basic stack code.
import java.util.EmptyStackException;
public class IntStack {
// the top of the stack
private Node top;
private int size;
private class Node {
private int data;
private Node next;
private Node(int item) {
data = item;
next = null;
}
}
public IntStack () {
top = null;
size = 0;
}
// returns the top value or exception when empty.
public int peek() {
if (isEmpty())
throw new EmptyStackException();
else
return top.data;
}
// push new item on the top
public void push(int item) {
Node n = new Node(item);
n.next = top;
top = n;
size++;
}
// remove item from the top and return the removed value.
public int pop() {
int v;
if ( isEmpty() )
throw new EmptyStackException();
v = top.data;
top = top.next;
size--;
return v;
}
// debug method to dump the contents of the stack to the screen
public String toString() {
Node p = top;
String s = "";
while ( p != null ) {
s = s + p.data + "\n";
p = p.next;
}
return s;
}
// method to determine if the stack is empty.
public boolean isEmpty() {
return top == null;
}
// method to return the number of frames
public int size() {
return size;
}
}
Example 1a: The class IntStack which uses a Node to perform typical stack operations.
Notice how we build the stack. Everything is pushed onto the top (or head from our linked list discussions) of the chain. Subsequently we only pop from the top. This is all we need to perform the necessary operations on a stack.
But do not lose sight that this is just a linked list governed by different rules.
The pop() method must be sensitive to the possibility that the stack may be empty. This is called a stack underflow, but Java has an exception already set aside for this purpose. The pop() method will throw an EmptyStackException in the event we attempt to pop an empty stack. This would allow an application using this class to catch the exception and have an opportunity to decide what to do next.
When pushing a value onto the stack, there is the possibility of running out of memory and not being able to add another value. Ordinarily, we would call this a stack overflow, but since the actual issue is that we have exhausted memory, we have chosen not to deal with this at all. Instead, it is left to the programmer to decide what to do if the application exceeds available memory.
We also introduce a couple of other tools for use with stacks. For example, we may want to look at the value on top of the stack but not pop it. This is useful in determining if some action should be taken based on the top stack value. A tool like this is more advantageous than popping the value, inspecting it to determine the action taken and then pushing it back onto the stack if we decide we do not want it. The peek() method allows us to inspect the value on top, being mindful of the possibility that the stack is empty and throwing an exception when appropriate.
Another useful tool for stack operations is a debug method to dump the stack to the screen for viewing. Sometimes this, along with a debugger, helps ascertain why a program performs a certain way. The dumpstack() method from our linked list has been renamed toString() and returns the contents of our integer stack as a String. The first item displayed is the top; all subsequent values are shown below.
One more useful tool is the boolean method isEmpty(). The isEmpty() method is useful when trying to set up a while loop to deal with all of the items on the stack.
Finally we can get the number of stack elements (also called frames) by calling the size() method.
Stacks are used in many everyday pieces of software, including compilers, operating systems, and applications. Anytime we need the ability to keep historical information as last-in-first-out (LIFO or FILO – first-in-last-out), a stack is likely a good candidate.
The code in Example 1b is used to exercise the IntStack class. Essentially, all the test code will perform the same job – add a few values and try all code paths along the way.
import java.util.EmptyStackException;
public class ExerciseIntStack
public static void main(String[] args) {
IntStack s = new IntStack();
s.push(7);
s.push(5);
s.push(3);
System.out.println("Stack length is " + s.size());
System.out.println("Stack contains:\n" + s);
while (! s.isEmpty()) {
System.out.println("Popped " + s.pop());
}
// intentionally try to pop an empty stack
try {
System.out.println("Popped " + s.pop());
} catch (EmptyStackException e) {
System.out.println("That could have been bad!");
}
}
}
Example 1b: Code to exercise the IntStack.
The output is shown below:
Stack length is 3 Stack contains: 3 5 7 Popped 3 Popped 5 Popped 7 That could have been bad!
Queues
Queues are a data structure with all the basic properties of a linked list, but now we keep track of both ends instead of just the front (top, head, first, etc.).
Stacks are first-in-last-out (FILO or LIFO) structures, whereas queues are first-in-first-out (FIFO). It is exactly like going to the grocery store, where we enter at the end of the line and work our way toward the front until it is our turn.
Similar to Stacks that have push() and pop() methods, the operations are now called enqueue and dequeue. The corresponding methods are enq() and deq() respectively.
The rules are that we always enqueue on the end and (last) and dequeue from the front (first)
import java.util.NoSuchElementException;
public class IntQueue {
// the front and back of the queue
private Node first, last;
private int size;
private class Node {
private int data;
private Node next;
private Node(int item) {
data = item;
next = null;
}
}
public IntQueue () {
first = null;
last = null;
size = 0;
}
// returns the first value or exception when empty.
public int peek() {
if (isEmpty())
throw new NoSuchElementException();
else
return first.data;
}
// enqueue (add) new item on the last
public void enq(int item) {
Node oldlast = last;
last = new Node(item);
if (isEmpty())
first = last;
else
oldlast.next = last;
size++;
}
// dequeue (remove) item from the first of the queue and return the removed value.
public int deq() {
int v;
if ( isEmpty() )
throw new NoSuchElementException();
v = first.data;
first = first.next;
if ( first == null )
last = null;
size--;
return v;
}
// debug method to dump the contents of the queue to the screen
public String toString() {
Node p = first;
String s;
s = "FIRST ->";
while ( p != null ) {
s = s + " " + p.data + " ";
p = p.next;
}
s = s +"<- LAST\n";
return s;
}
// method to determine if the queue is empty.
public boolean isEmpty() {
return first == null;
}
// method to return the number of queue entries
public int size() {
return size;
}
}
Example 2a: The class IntQueue which uses a Node to perform typical queue operations.
Example 2b provides a test of the IntQueue data structure.
import java.util.NoSuchElementException;
public class ExerciseIntQueue {
public static void main(String[] args) {
IntQueue q = new IntQueue();
q.enq(7);
q.enq(5);
q.enq(3);
System.out.print("Queue contains:\n" + q);
System.out.println("Queue length is " + q.size());
while (! q.isEmpty()) {
System.out.println("Dequeued " + q.deq());
}
// intentionally try to deq an empty queue
try {
System.out.println("Dequeued " + q.deq());
} catch (NoSuchElementException e) {
System.out.println("That could have been bad!");
}
}
}
Example 2b: Code to test IntQueue.
The basic components are similar to the Stack example where we have a peek() method to non-destructively view the front of the line (first) as well as a nice toString() to dump the contents for debugging.
There is also a size() and isEmpty() method.
The output of the test is shown below:
Queue contains: FIRST -> 7 5 3 <- LAST Queue length is 3 Dequeued 7 Dequeued 5 Dequeued 3 That could have been bad!
Deques (Double-Ended Queues)
The double-ended queue or deque (pronounced deck) is what you get when you cross a queue with a schizophrenic stack. It is a simple modification of the queue in the previous section. The rules change enough to allow us to enqueue or dequeue from both ends, making it a first-or-last-in-first-or-last-out (FLIFLO) design.
There seems to be little agreement on what to call the functions (push and pop for stacks, enqueue and dequeue for queues). We will call them addFirst(), addLast(), removeFirst() and removeLast().
Everything else will remain the same regarding the support methods (toString(), isEmpty(), size()).
Essentially the old enq() becomes addLast() and deq() becomes removeFirst(). The other two will be new. What will also be new here is the concept of the doubly-linked list. The base Node will be modified to be able to point to the next node, but also point to the previous node. This is necessary since we can perform movement and relinking operations in both directions.
import java.util.NoSuchElementException;
public class IntDeque {
// the top of the queue
private Node first, last;
private int size;
private class Node {
private int data;
private Node next, prev;
private Node(int item) {
data = item;
next = null;
prev = null;
}
}
public IntDeque () {
first = null;
last = null;
size = 0;
}
// returns the first value or exception when empty.
public int peekFirst() {
if (isEmpty())
throw new NoSuchElementException();
else
return first.data;
}
// returns the last value or exception when empty.
public int peekLast() {
if (isEmpty())
throw new NoSuchElementException();
else
return last.data;
}
// enqueue (add) new item on the last
public void addLast(int item) {
Node oldlast = last;
last = new Node(item);
if (isEmpty())
first = last;
else {
// link up both directions
oldlast.next = last;
last.prev = oldlast;
}
size++;
}
// enqueue (add) new item on the first
public void addFirst(int item) {
Node oldfirst = first;
first = new Node(item);
if (isEmpty())
last = first;
else {
// link up both directions
oldfirst.prev = first;
first.next = oldfirst;
}
size++;
}
// dequeue (remove) item from the first of the queue and return the removed value.
public int removeFirst() {
int v;
if ( isEmpty() )
throw new NoSuchElementException();
v = first.data;
// advance and null the prev link.
first = first.next;
if (first != null )
first.prev = null;
else
last = null;
size--;
return v;
}
// dequeue (remove) item from the first of the queue and return the removed value.
public int removeLast() {
int v;
if ( isEmpty() )
throw new NoSuchElementException();
v = last.data;
// advance and null the prev link.
last = last.prev;
if ( last != null )
last.next = null;
else
first = null;
size--;
return v;
}
// debug method to dump the contents of the queue to the screen
public String toString() {
Node p = first;
String s;
s = "FIRST ->";
while ( p != null ) {
s = s + " " + p.data + " ";
p = p.next;
}
s = s +"<- LAST\n";
s = s + "LAST ->";
p = last;
while ( p != null ) {
s = s + " " + p.data + " ";
p = p.prev;
}
s = s +"<- FIRST\n";
return s;
}
// method to determine if the queue is empty.
public boolean isEmpty() {
return first == null;
}
// method to return the number of queue entries
public int size() {
return size;
}
}
Example 3a: The class IntDeque which uses a Node to perform typical deque operations.
Example 3b tests the IntDeque class.
import java.util.NoSuchElementException;
public class ExerciseIntDeque {
public static void main(String[] args) {
IntDeque d = new IntDeque();
int x;
d.addLast(7);
d.addLast(5);
d.addLast(3);
d.addFirst(13);
d.addFirst(15);
d.addFirst(17);
System.out.print("Deque contains:\n" + d);
System.out.println("Deque length is " + d.size());
x = 0;
while ( x < 3 ) {
System.out.println("Dequeued from front " + d.removeFirst());
x++;
}
System.out.print("Deque contains:\n" + d);
x = 0;
while ( x < 3 ) {
System.out.println("Dequeued from end " + d.removeLast());
x++;
}
/*
x = 0;
while ( x < 3 ) {
System.out.println("Dequeued from front " + d.removeFirst());
x++;
}
*/
System.out.print("Deque contains:\n" + d);
// intentionally try to deq an empty deqque
try {
System.out.println("Dequeued from front " + d.removeFirst());
} catch (NoSuchElementException e) {
System.out.println("That could have been bad!");
}
// intentionally try to deq an empty deque
try {
System.out.println("Dequeued fron end " + d.removeLast());
} catch (NoSuchElementException e) {
System.out.println("That could have been bad!");
}
}
}
Example 3b: Code to test IntQueue.
The output is shown below:
Deque contains: FIRST -> 17 15 13 7 5 3 <- LAST LAST -> 3 5 7 13 15 17 <- FIRST Deque length is 6 Dequeued from front 17 Dequeued from front 15 Dequeued from front 13 Deque contains: FIRST -> 7 5 3 <- LAST LAST -> 3 5 7 <- FIRST Dequeued from end 3 Dequeued from end 5 Dequeued from end 7 Deque contains: FIRST -><- LAST LAST -><- FIRST That could have been bad! That could have been bad!