Queues: A Tale of Two Stacks
Queues
A queue is an abstract data type that uses a principle called First-In-First-Out (FIFO), meaning that the first object added to the queue must be the first object removed from it. You can analogize this to a checkout line at a store where the line only moves forward when the person at the head of it has been helped, and each person in the line is directly behind the person whose arrival immediately preceded theirs.
At minimum, any queue should be able to perform the following two operations:
- Enqueue: Add an object to the back of the line.
- Dequeue: Remove the object at the head of the line and return it; the element that was previously second in line is now at the head of the line.
The diagram below demonstrates these simple operations on an empty queue:
In addition, it's often helpful to implement a method to check whether or not a queue is empty to ensure you are not attempting to perform dequeue operations on an empty queue.
Sample Java Implementation
EXAMPLE
The code below demonstrates a simple Java Queue implementation.
x
1
import java.util.*;2
3
class Queue<E> {4
5
private class Element<E> {6
// The data value of the element7
private E data;8
// The next element in the queue9
private Element<E> next;10
11
Element(E data) {12
this.data = data;13
this.next = null;14
}15
}16
17
// The first element in the queue18
private Element<E> front;19
// The last element in the queue20
private Element<E> back;21
22
/** Create an empty queue **/23
public Queue() {24
this.front = null;25
this.back = null;26
}27
28
/** @return true if the queue is empty, false if it is not.29
**/30
public boolean isEmpty() {31
return front == null || back == null;32
}33
34
/**35
Enqueues a value into the queue. 36
@param value The data to be enqueued.37
**/38
public void enqueue(E value) {39
// Create new element40
Element<E> newElement = new Element<E>(value);41
42
// If the queue is empty43
if(isEmpty()) {44
this.front = newElement;45
}46
else { // Queue is not empty47
// Link the old last element to the new last element48
this.back.next = newElement;49
}50
51
// Set new back element regardless of whether or not queue is empty52
this.back = newElement;53
}54
55
/**56
Dequeues the queue's first element.57
@return the data associated with the queue's dequeued element.58
@throws NoSuchElementException if the queue contains no elements.59
**/60
public E dequeue() {61
if(isEmpty()) {62
throw new NoSuchElementException();63
}64
65
Element<E> head = front;66
this.front = front.next;67
68
return head.data;69
}70
71
/** 72
'View' the element at the front of the queue.73
@return the data associated with the queue's first element.74
@throws NoSuchElementException if the queue contains no elements.75
**/76
public E peekFirst() {77
if(isEmpty()) {78
throw new NoSuchElementException();79
}80
81
return front.data;82
}83
84
/** 85
'View' the element at the tail of the queue.86
@return the data associated with the queue's first element.87
@throws NoSuchElementException if the queue contains no elements.88
**/89
public E peekLast() {90
if(isEmpty()) {91
throw new NoSuchElementException();92
}93
94
return back.data;95
}96
}97
98
class QueueDemo {99
public static void main(String[] args) {100
Queue<Integer> intQueue = new Queue<Integer>();101
102
try {103
intQueue.dequeue();104
}105
catch(NoSuchElementException e) {106
System.out.println("We cannot dequeue from an empty queue.");107
}108
109
for(int i = 0; i < 4; i++) {110
intQueue.enqueue(i);111
System.out.println(112
"First: " + intQueue.peekFirst() + 113
"; Last: " + intQueue.peekLast()114
);115
}116
for(int i = 0; i < 4; i++) {117
System.out.println("Dequeued: " + intQueue.dequeue());118
}119
120
try {121
intQueue.peekFirst();122
}123
catch(NoSuchElementException e) {124
System.out.println("We cannot peek at an empty queue.");125
}126
}127
}
Output
Table Of Contents
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.
105
1
import java.util.*;2
3
class Stack<E> {4
5
private class Element<E> {6
// The data value of the element7
private E data;8
// The next element in the stack9
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 stack18
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 element37
Element<E> newTop = new Element<E>(value);38
39
// If the stack is not empty40
if(!isEmpty()) {41
// Set old top's next variable to point to new top42
newTop.next = top;43
}44
45
// Set new top regardless of whether or not stack is empty46
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
