Programming Problems in Java: A Primer for The Technical Interview (2014)
Chapter 4. Queues and Stacks
The next data structures we visit are queues and stacks.
Queues and stacks are ubiquitous in both programming and technical interviews. Queues are used to maintain priority while processing requests. Stacks are fundamental in program evaluation and parsing. Both are used commonly in graphical search and enumeration algorithms.
In this section we will look at the definitions of queues and stacks. We construct implementations of each from elementary data structures. And finally we look at some interesting interview problems that can be solved with queues and stacks.
4.1 Queue
A queue is an abstract data structure that preserves first-in first-out order of its data. The queue data structure has only two basic operations, enqueue and dequeue. Enqueue pushes data to the back of the queue, and dequeue removes data from the front of the queue. In an efficient implementation, these operations complete in constant time.
A queue is easily implemented from a doubly linked-list. Enqueue appends an item to the tail of a list, and dequeue removes the current head node, replacing it with the next node in the list.
The following is a sample implementation of a queue using aLinkedList. The enqueue operation is calledpush, and the dequeue operations is calledpop, which also returns the item removed from the queue. To access data in the queue, we provide a method calledfront which returns the value of the node at the front of the queue without removing it.
Listing 4.1: Queue Class
class Queue {
private List<Integer> list;
Queue() {
list = new LinkedList<Integer>();
}
void push(int data) {
list.add(data);
}
Integer front() {
return (list.size() == 0) ? null
: list.get(0);
}
Integer pop() {
return (list.size() == 0) ? null
: list.remove(0);
}
}
Note thatJavaprovides aQueueinterface with various class implementations.
4.2 Stack
A stack is an abstract data type that provides last-in first-out access to underlying data. Compared with a queue, it provides a kind of reverse access. As with a queue, a stack exposes two operations. These are push and pop. Push stores data onto the top of a stack, and pop removes data from the top of the stack. These operations run in constant time in an efficient implementation.
A stack is easily implemented from a simple linked-list. The list need not be circular or doubly linked as a stack only accesses the head. A push operation inserts a node at the head, and a pop operation removes the head.
The following is a sample implementation of a stack using the linked-list data structure derived previously. To access the data in the stack, we provide a method calledtopwhich returns the value of the node at the top of the stack. To remove the data at the top of the stack, we provide a method calledpopwhich also returns the value of the removed node.
Listing 4.2: Stack Class
class Stack {
private List<Integer> list;
Stack() {
list = new LinkedList<Integer>();
}
void push(int data) {
list.add(0, data);
}
Integer top() {
return (list.size() == 0) ? null : list.get(0);
}
Integer pop() {
return (list.size() == 0) ? null
: list.remove(0);
}
}
Note thatJavaprovides aStackclass withpush,popand other functions.
4.3 Implement a queue using a stack
A common programming question is to implement a queue using a stack. The goal is to show equivalence the power of the two elementary data types.
The key to solving this problem is to understand that stacks and queues are opposite in terms of their access, and that there is no mechanism by which a single stack alone can implement a queue. The solution is to use two stacks to reverse the data.
In the solution below we have two stacks called in-stack and out-stack. The in-stack allows for enqueue in constant time. Each queue push operation is translated into a stack push operation.
To support first-in first-out, when the dequeue operation is taken we must be able to reach to the bottom of the in-stack. To do this, we need only empty the in-stack to the out-stack. Notice the element last in starts on top of in-stack, and after the transfer it is on the bottom of out-stack. The top of out-stack was the first in, so popping this element provides us with a queue. The private methodtransferconsolidates the logic for the data transfer between the two stacks.
Listing 4.3: Implement Queue from a Stack
class QueueFromStack {
private Stack<Integer> instack;
private Stack<Integer> outstack;
QueueFromStack() {
instack = new Stack<Integer>();
outstack = new Stack<Integer>();
}
void push(int data) {
instack.push(data);
}
Integer front() {
if (outstack.empty() && instack.empty()) {
return null;
}
transfer();
return outstack.peek();
}
Integer pop() {
if (outstack.empty() && instack.empty()) {
return null;
}
transfer();
return outstack.pop();
}
private void transfer() {
if (outstack.empty()) {
while (!instack.isEmpty()) {
outstack.push(instack.pop());
}
}
}
}
Notice that the out-stack is only updated when it is found to be empty during an access or dequeue operation. A commonly made error is to make out-stack a temporary variable. After creation and popping it once, the contents are transferred back into the in-stack. This is potentially wasteful.
4.4 Implement a stack using a queue
A follow-up is to reverse the question, and ask a candidate to implement a stack using a queue. This question has a number of answers. Similar to above, we provide a solution that uses two queues.
In this solution, we maintain the invariant that the queue that is not empty has its elements in reverse order. In that way, a pop operation need only dequeue from the non-empty queue.
For a single element, this is always the case. Now we suppose a second element is pushed. Instead of pushing it onto the non-empty queue, add it to a secondary and empty queue. This will be the first element removed from the secondary queue. We then transfer the first queue to the secondary queue. This leaves us with a single non-empty queue, whose elements are in last-in first-out order. This logic is the core of thepushmethod below.
Listing 4.4: Implement Stack from a Queue
class StackFromQueue {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
StackFromQueue() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
void push(int data) {
Queue<Integer> enqueue =
queue1.isEmpty() ? queue1 : queue2;
Queue<Integer> dequeue =
queue1.isEmpty() ? queue2 : queue1;
enqueue.add(data);
while (!dequeue.isEmpty()) {
enqueue.add(dequeue.poll());
}
}
Integer top() {
return !queue1.isEmpty()
? queue1.peek()
: queue2.peek();
}
Integer pop() {
return !queue1.isEmpty() ? queue1.poll()
: queue2.poll();
}
}
4.5 Level order traversal
A classic interview question is to perform a level order traversal of a binary tree. That is, given a binary tree, visit the nodes from left to right in order of their depth.
The key to solving this question is to use a queue to manage the frontier of exploration. We initialize the queue with the root node. This is the first level. Then each node is visited in turn and its children are enqueued. Every level is contiguous, and levels are visited in turn.
Listing 4.5: Level Order Traversal
void level_traversal(Node root) {
if (null == root) {
return;
}
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
if (null != node.left) {
queue.add(node.left);
}
if (null != node.right) {
queue.add(node.right);
}
System.out.println(node.value);
}
}
Another name for this enumeration is breadth-first traversal. And we’ve shown that breadth-first on a binary tree is exactly level order.
A common modification to the question is to separate the levels with a token, such as a newline. In order to accomplish this, we can seed the queue with a level end token such asnullor a special symbol likeLEVEL_TOKEN. When we encounter this token again we know that the current level has been fully enumerated. If the token is then enqueued again, it will be placed at the end of the level which was just enqueued. With this trick, we can complete the solution usingLEVEL_TOKENas our level separation token.
Listing 4.6: Level Order Traversal with Separation Tokens
static final Node LEVEL_TOKEN = new Node(null);
void level_traversal_with_separation_token(
Node root) {
if (null == root) {
return;
}
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
queue.add(LEVEL_TOKEN);
while (!queue.isEmpty()) {
Node node = queue.poll();
if (LEVEL_TOKEN == node) {
if (!queue.isEmpty()) {
System.out.println("END LEVEL");
queue.add(LEVEL_TOKEN);
}
continue;
}
if (null != node.left) {
queue.add(node.left);
}
if (null != node.right) {
queue.add(node.right);
}
System.out.println(node.value);
}
}
4.6 Largest rectangle under a histogram
A histogram is a graphical representation of data in which sequential entries along the x-axis are associated with a height in the y-axis. These values are plotted as rectangles of equal width with height equal to the y-value. In statistics, a histogram gives a graphical representation of a probability distribution.
An advanced interview question is to calculate the area of the largest rectangle under the histogram.
Since the histogram is composed of rectangles, we see that every maximal rectangle is bounded by the height of some entry in the histogram. The width of every maximal rectangle under the histogram is the number of other rectangles that are contiguous but at least as tall. So we are looking for rectangles bounded by three entries in the histogram: an entry that defines the height, the first contiguous entry of at least that height, and the last contiguous entry of at least that height.
We begin by defining a histogram as a class with x and y coordinates.
Listing 4.7: Definition of Histogram
class HistogramEntry {
int x;
int y;
HistogramEntry(int x, int y) {
this.x = x;
this.y = y;
}
}
A naive solution starts by enumerating all pairs of histogram entries α and β. It calculates the minimum height between α and β by iteratively checking each of those values. The area is then computed and a running max is tracked. However, this solution is cubic!
Using a stack, we can find a solution that solves the problem in a single pass. The stack maintains a collection of all ‘open’ rectangles. The solution takes it in turn to inspect each entry of the histogram from left to right. When the height of histogram entries is increasing, an open rectangle is added to the stack. It is specified by its x and y coordinates. But the y coordinate must be the earliest rectangle preceding the entry that is at least as tall. We will see that the y coordinate can be determined by closing open rectangles before pushing the new entry onto the stack.
When the height of histogram entry decreases during enumeration, all open entries with height larger than the current value must be closed. The area of an open entry is its height multiplied by width. The width is simply the current x location minus the starting location.
After the last entry has been visited, a final pass must close all open entries.
Listing 4.8: Largest Rectangle Under Histogram
int largest_area(List<HistogramEntry> histogram) {
int max_area = 0;
int current_pos = 0;
int last_closed_pos = 0;
Stack<HistogramEntry> open_entries =
new Stack<HistogramEntry>();
for (HistogramEntry entry : histogram) {
current_pos = entry.x;
last_closed_pos = entry.x;
while (!open_entries.isEmpty()
&& open_entries.peek().y >= entry.y) {
HistogramEntry top = open_entries.pop();
last_closed_pos = top.x;
int area =
top.y ⋆ ((current_pos - 1) - (top.x - 1));
max_area = Math.max(max_area, area);
}
open_entries.push(new HistogramEntry(
last_closed_pos, entry.y));
}
current_pos++;
while (!open_entries.isEmpty()) {
HistogramEntry top = open_entries.pop();
int area =
top.y ⋆ ((current_pos - 1) - (top.x - 1));
max_area = Math.max(max_area, area);
}
return max_area;
}
In this solution, it is clear that every rectangle is only considered once. This means that every entry in the histogram has been pushed once and popped once, and so we have achieved a linear time algorithm. This is a dramatic improvement over the naive cubic time solution.