4.4 STACKS AND QUEUES

This section under major construction.

Collections.

In this section, we design two data structures (stacks and queues) that manipulate arbitrarily large collections of objects. These data structures are comprised of two basic operations: insert a new item into the collection and remove an item from the collection. When we insert an object, our intent is clear. But when we remove an object, which one do we choose? A stack is a collection where we always choose to remove the most recently inserted item. This is referred to as last-in first-out (LIFO). An everyday example of using a stack is surfing the web. When you click a hyperlink, your browser displays the new page (insert). You can keep clicking on hyperlinks to visit new pages. You can always revisit the previous page by clicking the Back button (remove). A queue is just the opposite - we always choose to remove the least recently inserted item. This is referred to as first-in first-out (FIFO). A classic example of a queue is waiting in line at the Department of Motor Vehicles. When you arrive, you start at the end of the line (insert). The customer that arrived first is the first one serviced (delete). We will consider many important commercial and scientific applications of stacks and queues.

Stack.

A stack supports the insert and remove operations using a LIFO discipline. We name insert operation as push and the remove operation pop.

We also include a method isEmpty to test whether or not the stack is empty. Each element in the collection can be any Java Object. Below we consider two different implementation of the following interface.

public boolean isEmpty();
public void push(Object value);
public Object pop();

Before we describe how to implement a stack, we give a simple client program that reads in an arbitrary sequence of values and prints them in reverse order.

public static void main(String[] args) {
   Stack stack = new Stack();
   while (StdIn.hasNextString()) {
      String s = StdIn.nextString();
      stack.push(s);
   }
   while (stack.isEmpty()) {
      System.out.println(stack.pop());
   }
}

Now that we have described how to use a stack, we will describe two different ways for implementing one. Our first solution uses a linked list; our second uses an array.

Linked list implementation. To implement a stack with a linked list, we maintain a reference to the first node of the linked list. This corresponds to the top of the stack. We implement push by inserting a new node at the beginning of the linked list. We implement pop by deleting the first node of the linked list. Program Stack.java implements the stack interface using this approach. This program uses a nested class Node to represent each linked list node.

private static class Node {
   Object value;
   Node next;
}

We declare the subclass to be static because there only needs to be one data type Node, shared among all stacks. It would still work if we didn't use static, but it would be somewhat less efficient. By declaring the subclass Node to be private we effectively restrict access to methods within the enclosing class ListStack. Regardless of whether we declare its data members public or private, they can be directly accessed from within ListStack, but nowhere else. We don't use any access modifiers to emphasize its unimportance.

Linked List implementation of a stack (insert)

Array implementation. A natural way to implement a stack is with an array s of objects. Program ArrayStack.java implements the stack interface using this approach. We maintain an integer N that counts the number of objects currently in the stack and an array a that holds the stack elements. To insert a new object, we set a[N] equal to the new element and increment N. To remove an object, we return a[N-1] and decrement N.

The trickiest part is to dynamically adjust the size of the array a so that it is always big enough to hold all of the elements. We use a popular strategy known as repeated doubling: initially we make the array big enough to hold 1 object. Then before we insert an new object, we check that the array is big enough. If it is, then we insert it as described above. If it is not big enough, we create a new array of twice the size. This doubling strategy is a judicious tradeoff between wasting space (by setting the initial size of the array to be too big) and wasting time (by resizing the array after each insertion).

private void resize() {
   Object[] temp = new Object[2*N];
   for (int i = 0; i

When popping an Object from the stack in the array implementation, it's best to set a[N] to null before returning the deleted element. This removes the reference to a[N] and enables the garbage collector to reclaim the memory for the object as soon as the client is done with it.

Library implementation. Java has a built in library called Stack, but you should avoid using it. It has additional operations that are not normally associated with a stack, e.g., getting the ith element and adding an element to the bottom of the stack (instead of the top). Although having such extra operations may appear to be a bonus, it is actually a curse. We use ADTs not because they provide every available operation, but rather because they limit the types of operations we are allowed to perform! This prevents us from performing operations that we don't actually want. If we need more than just LIFO access, we should use a different data type. We can still build a stack data type from the Java libraries, but we are careful to limit the types of operations. Program LibraryStack.java implements a stack using the LinkedList library.

Balanced parentheses. Program Parentheses.java reads in a text stream from standard input and uses a stack to determine whether or not its parentheses are balanced. The basic idea is to read in characters, ignoring everything except left and right parentheses or braces. If we read in a left delimiter, we push it onto the stack. If we read in a right delimiter, we pop the stack and check that it matches the type (parentheses of braces) of the character read in. If it doesn't, then we have discovered a mismatch in the nesting of delimiters.

Arithmetic expression evaluation. An important application of stacks is in parsing. For example, a compiler must parse arithmetic expressions written using infix notation. For example the following infix expression evaluates to 212.

( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )

We break the problem of parsing infix expressions into two stages. First, we convert from infix to a different representation called postfix. Then we parse the postfix expression, which is a somewhat easier problem than directly parsing infix.

Evaluating a postfix expression. A postfix expression is....
2 3 4 + 5 6 * * +
First, we describe how to parse and evaluate a postfix expression. We read the tokens in one at a time. If it is an integer, push it on the stack; if it is a binary operator, pop the top two elements from the stack, apply the operator to the two elements, and push the result back on the stack. Program Postfix.java reads in and evaluates postfix expressions using this algorithm.
Converting from infix to postfix. Now, we describe how to convert from infix to postfix. We read in the tokens one at a time. If it is an operator, we push it on the stack; if it is an integer, we print it out; if it is a right parentheses, we pop the topmost element from the stack and print it out; if it is a left parentheses, we ignore it. Program Infix.java reads in an infix expression, and uses a stack to output an equivalent postfix expression using the algorithm described above. Relate back to the parse tree example in Section 4.3.

Function calls. Perhaps the most import application of stacks is to implement function calls. Most compilers implement function calls by using a stack. This also provides a technique for eliminating recursion from a program: instead of calling a function recursively, the programmer uses a stack to simulate the function calls in the same way that the compiler would have done so. Conversely, we can often use recursion instead of using an explicit stack. Some programming languages provide a mechanism for recursion, but not for calling functions.

Queue.

A queue supports the insert and remove operations using a FIFO discipline. We name insert operation enqueue and the remove operation dequeue. Lincoln tunnel. Student has tasks that must be completed. Put on a queue. Do the tasks in the same order that they arrive.

Event-based simulation. Computing applications: serving requests of a single shared resource (printer, mass-storage devices), transferring data asynchronously (data not necessarily received at same rate as sent) between two processes (IO buffers), e.g., pipes, file IO, sockets. Buffers on MP3 players and portable CD players, iPod playlist.

M/M/1 queue. The Markov/Markov/Single-Server model is a fundamental model in operations research and queuing theory. Tasks arrive according to a Poisson process at a certain rate λ. Tasks are serviced in FIFO order at a different rate μ. What can we say about various parameters? Program MM1Queue.java simulates an M/M/1 queue and plots a histogram of the average time a customer is waiting in the queue.

W = average time a customer spends in the system. WQ = average time a customer spends in the queue. NQ = average number of customers in the queue. N = average number of customers in the system. Could also look at distributions. For simple models like M/M/1 we can analyze these quantities analytically using probability theory. However, for model complex model we need to resort to simulation. Applications: customers in McDonalds, packets in an internet router, Variants: multiple queues, multiple servers, sequential multi-stage servers, using a finite queue and measuring number of customers that are turned away. Exercise: M/M/2 with two FIFO queues.

Perception that you always pick the longer line (or wrong lane) when approaching a toll plaza. Suppose two cars enter the toll plaza at the same time and pick different queues of the same length. Compute average length in time that one car will beat the other car by.

Linked list implementations. Program Queue.java implements a FIFO queue using a linked list. It maintains two references first and last, to the first node and last node of the linked list, respectively.

Linked List implementation of a queue (insert)

Array implementation. Similar to array implementation of stack, but a little trickier since need to wrap-around. Program ArrayQueue.java implements the Queue interface using an array. The array is dynamically resized if it is too small to accommodate the next item.

Library implementation. Java does not have a built in data type for FIFO queues. However, it is easy to build one from Java's LinkedList, ArrayList or Vector libraries. Program LibraryQueue.java implements a queue using the LinkedList library.

Listing files. A Unix directory is a list of files and directories. Program Directory.java takes the name of a directory as a command line parameter and prints out all of the files contained in that directory (and any subdirectories) in level-order. It uses a queue.

Level-order traversal of tree.

Built-in support for queues. Programming languages have built in support for stacks (recursion), but no analogous mechanism for dealing with queues. When you click on a link in a browser, the browser pushes this page on to a stack. When you hit the "Back" button, the browser pops from the stack. Most modern browsers (Safari, Mozilla, Netscape, Opera, Konqueror) except Internet Explorer also support tabbed browsing. You can view this is a queue. When you Option-click a hyperlink, the browser creates a new tab with that page. The browser displays a list (queue) of tabs, and each tab contains its own independent stack of web pages.

Autoboxing. We have designed our stacks and queues so that they can store any type of Object. This enables us to reuse the code, but there is a tradeoff to this approach. First, we would like our code to work for primitive types as well. Java 1.5 provides an mechanism known as auto-boxing and auto-unboxing that facilitates this. Associated with each primitive type, e.g. int, is a full blown object type, e.g., Integer. When we assign a primitive to the corresponding object type (or vice versa), Java automatically performs the transformation. This enables us to write code like the following.

ArrayStack stack = new ArrayStack();
stack.push(17);                      // auto-boxing
int a = (Integer) stack.pop();       // auto-unboxing

The 17 is automatically cast to be of type Integer when we invoke the push method. When we invoke the pop method, we must cast the result to be of type Integer since this is the type that is stored on the stack. We can then assign this value to a variable of type int since Java automatically casts form the object version to the primitive type. We should be aware of what is going on behind the scenes since this can affect performance.

Program Josephus.java uses Queue to solve the Josephus problem.

Generic implementations.

We have developed one stack implementation that allows us to build both a stack of integers and a stack of strings by using inheritance. Our implementation supports inserting and deleting objects of type Object. We push an object of any type onto the stack, and cast each element back to the appropriate type when we pop it. Since all objects in Java are derived from Object, the cast is always valid. This approach can expose us to subtle bugs in our programs that cannot be detected until runtime. For example, there is nothing to stop a programmer from putting different types of objects on the same stack, then encountering a runtime type-checking error, as in the following example:

ArrayStack s = new ArrayStack();
Apple  a = new Apple();
Orange b = new Orange();
s.push(a);
s.push(b);
a = (Apple)  (s.pop());   // throws a ClassCastException
b = (Orange) (s.pop());

This toy example illustrates a basic problem. When we use type casting with an implementation such as ArrayStack for different types of items, we are assuming that clients will cast objects popped from the stack to the proper type. This implicit assumption contradicts our requirement for ADTs that operations are to be accessed only through an explicit interface. One reason that programmers use precisely defined ADTs is to protect future clients against errors that arise from such implicit assumptions. The code cannot be type-checked at compile time: there might be an incorrect cast that occurs in a complex piece of code that could escape detection until some particular runtime circumstance arises. Such an error is to be avoided at all costs because it could happen long after an implementation is delivered to a client, who would have no way to fix it.

One way to address this problem is to use the generic ArrayStack class to implement a stack that can contain objects of only one type. This means that we need separate classes for every type of object, but their implementations are trivial, and we do not have to duplicate the (potentially complicated) algorithm and data-structure implementations. It is actually quite common in Java programming to define a class whose sole purpose is to match the needs of a client with the capability of an existing class. Such a class is called an adapter class. Program IntQueue.java is a wrapper class for a queue of integers.

AppleStack s = new AppleStack();
Apple  a = new Apple();
Orange b = new Orange();
s.push(a);
s.push(b);     // compile-time error

Now if we try to write the following code fragment, it will not compile since it attempts to insert an Orange object onto an Apple stack.

There is a second approach, but it involves a more advanced feature of Java called generics. Generics is a built-in mechanism for limiting the type of all objects on a stack or queue to be of the same type. This involves some new syntax.

Lessons

Q + A.

Q. Is it necessary to set a[N-1] to null when deleting an item from a stack?

A. It is not required for the correctness of the data type; however it can lead to a memory leak if you don't. That is, the stack data type might keep a reference to an object that the client program is done with with, and the object would not get garbage-collected.

Exercises

Suppose that an intermixed sequence of (stack) push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the return value. Which of the following sequence(s) could not occur?
(a) 4 3 2 1 0 9 8 7 6 5 (b) 4 6 8 7 5 3 2 9 0 1 (c) 2 5 6 7 4 8 9 3 1 0 (d) 4 3 2 1 0 5 6 7 8 9
Suppose that an intermixed sequence of (stack) push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the return value. Which of the following sequence(s) could not occur?
(a) 1 2 3 4 5 6 9 8 7 0 (b) 0 4 6 5 3 8 1 7 2 9 (c) 1 4 7 9 8 6 5 3 0 2 (d) 2 1 4 3 6 5 8 7 9 0
Write a program that reads in a sequence of words and prints them in reverse order. Use a stack.

What does the following code fragment do if N = 50?

Stack s = new Stack();
while (n > 0) {
   s.push(n % 2);
   n = n / 2;
}
while (!s.isEmpty())
    System.out.print(s.pop());
System.out.println();

Give a high level description of what the code fragment in the previous exercise does when presented with a positive integer n.
Answer: prints binary representation of n.

What does the following code fragment do to the queue q?

Stack s = new Stack();
while(!q.isEmpty())
   s.push(q.dequeue());
while(!s.isEmpty())
   q.enqueue(s.pop());

Modify Parentheses.java to match left and right square braces, [ and ], too.
Add a method Object peek() that returns the top element on the stack, or null if the stack is empty.
Add a method int size() to Stack and ArrayStack that returns the number of elements on the stack.
Add a method Object[] multiPop(int k) to Stack that pops k elements from the stack and returns them as an array of objects.
Add a method Object[] toArray() to Queue that returns all N elements on the queue as an array of length N.
Suppose that an intermixed sequence of (queue) put and get operations are performed. The puts put the integers 0 through 9 in order; the gets print out the return value. Which of the following sequence(s) could not occur?
(a) 0 1 2 3 4 5 6 7 8 9 (b) 4 6 8 7 5 3 2 9 0 1 (c) 2 5 6 7 4 8 9 3 1 0 (d) 4 3 2 1 0 5 6 7 8 9

What does the following code fragment do?

IntQueue q = new IntQueue();
for (int i = 0; i <10; i++) q.enqueue(i); while (!q.isempty()) { for (int i=0; i < 3; i++) q.enqueue(q.dequeue()); system.out.println(q.dequeue()); }

What does the following code fragment do?

IntQueue q = new IntQueue();
q.enqueue(0);
q.enqueue(1);
for (int i = 0; i <10; i++) { int a=q.dequeue(); int b=q.dequeue(); q.enqueue(b); q.enqueue(a + b); system.out.println(a); }

What data type would you choose to implement an "Undo" feature in a word processor?
Suppose you have a single array of size N and want to implement two stacks so that you won't get overflow until the total number of elements on both stacks is N+1. How would you implement this?
Suppose that you implemented push in the linked list implementation of StackList with the following code. What is the mistake?
public void push(Object value) { Node second = first; Node first = new Node(); first.value = value; first.next = second; }
Answer: By redeclaring first, you are create a new local variable named first, which is different from the instance variable named first.

Creative Exercises

Deque A double-ended queue or deque is a combination of a stack and and a queue. It stores a collection of objects and supports the following operations:

public Dequeue()                   // constructor
public void addFirst(Object o)     // insert at front
public void removeFirst(Object o)  // delete and return first
public void addLast(Object o)      // insert at back
public void removeLast(Object o)   // delete and return last
public boolean isEmpty()           // is the deque empty?

Write a data type Deque.java that implements the deque interface using a singly linked list.

Random queue. Create an abstract data type RandomQueue.java that supports the following operations: isEmpty, insert, and removeRandom, where the deletion operation deletes and returns a random object. Hint: maintain an array of objects. To delete an object, swap a random object (indexed 0 through N-1) with the last object (index N-1). Then, delete and return the last object.
Delete ith element. Create an ADT that supports the following operations: isEmpty, insert, and remove(int i), where the deletion operation deletes and returns the ith least recently added object on the queue. Do it with an array, then do it with a linked list. See Exercise XYZ for a more efficient implementation that uses a BST.
Dynamic shrinking. With the array implementations of stack and queue, we doubled the size of the array when it wasn't big enough to store the next element. If we perform a number of doubling operations, and then delete alot of elements, we might end up with an array that is much bigger than necessary. Implement the following strategy: whenever the array is 1/4 full or less, shrink it to half the size. Explain why we don't shrink it to half the size when it is 1/2 full or less.
Copy a queue. Create a new constructor so that LinkedQueue r = new LinkedQueue(q) makes r reference a new and independent queue. Hint: delete all of the elements from q and add to both q and this.

Copy a stack. Create a new constructor for the linked list implementation of Stack.java so that Stack t = new Stack(s) makes t reference a new and independent copy of the stack s. You should be able to push and pop from s or t without influencing the other.

Should it work if argument is null? Recursive solution: create a copy constructor for a Node and use this to create the new stack.

Node(Node x) {
   item = x.item;
   if (x.next != null) next = new Node(x.next);
}

public Stack(Stack s) { first = new Node(s.first); }

Nonrecursive solution (untested):

Node(Node x, Node next) { this.x = x; this.next = next; }

public Stack(Stack s) {
   if (s.first != null) {
      first = new Node(s.first.value, s.first.next) {
      for (Node x = first; x.next != null; x = x.next)
         x.next = new Node(x.next.value, x.next.next);
   }
}

Ring buffer. A ring buffer or circular queue is a FIFO data structure of a fixed size N. It is useful for transferring data between asynchronous processes or storing log files. When the buffer is empty, the consumer waits until data is deposited; when the buffer is full, the producer waits to deposit data. A ring buffer has the following methods: isEmpty, isFull, enqueue, and dequeue. Implement a ring buffer using an array (with circular wrap-around).
Listing files with a stack. Write a program that takes the name of a directory as a command line argument, and prints out all of the files contained in this directory and any subdirectories. Also prints out the file size (in bytes) of each file. Use a stack instead of a queue.
Listing files with recursion. Repeat the previous exercise but use recursion. Name your program DirectoryR.java.
Sizes of directories. Modify DirectoryR.java so that it prints out each subdirectory and its total size. The size of a directory is equal to the sum of all of the files it contains or that its subdirectories contain.
Merging two sorted queues. Given two queues with strings in ascending order, move all of the strings to a third queue so that the third queues ends up with the strings in ascending order.
Merging two sorted queues. Repeat the previous exercise, but instead of using a third queue, move all of the strings from the second queue to the first queue so that the first queue ends up with all the strings in ascending order.
Mergesort. Given N strings, create N queues, each containing one of the strings. Create a queue of the N queues. Then repeatedly apply the sorted merging operation to the first two queues and reinsert the merged queue at the end. Repeat until the queue of queues contains only one queue.
Queue with two stacks. Show how to implement a queue using two stacks. Hint: If you push elements onto a stack and then pop them all, they appear in reverse order. If you repeat this process, they're now back in order.
Stack with one queue. Show how to implement a stack using one queue. Hint: to delete an item, get all of the elements on the queue one at a time, and put them at the end, except for the last one which you should delete and return.
Turing tape. Implement an one-dimensional Turing tape. The tape consists of a sequence of cells, each of which stores an integer (that is initialized to 0). At any instant, there is a tape head which points to one of the cells. Support the following interface methods: moveLeft to move the tape head one cell to the left, moveRight to move the tape head one cell to the right, look to return the contents of the active cell, and write(int a) to change the contents of the active cell to a. Hint: use an int for the active cell, and two stacks for the left and right parts of the tape.
Stack + max. Create a data structure that efficiently supports the stack operations (pop and push) and also return the maximum element. Assume the elements are integers or reals so that you can compare them. Hint: use two stacks, one to store all of the elements and a second stack to store the maximums.
PostScript. PostScript is a stack-based language used by most printers. Implement a small subset of PostScript using a stack.
Interview question. Given a stack of an unknown number of strings, print out the 5th to the last one. It's ok to destroy the stack in the process. Hint: use a queue of 5 elements.
Move-to-front. Read in a sequence of characters from standard input and maintain the characters in a linked list with no duplicates. When you read in a previously unseen character, insert it at the front of the list. When you read in a duplicate character, delete it from the list and re-insert it at the beginning. Name your program MoveToFront.java. This move-to-front strategy is useful for caching and data compression (Burrows-Wheeler) algorithms where items that have been recently accessed are more likely to be re-accessed.
Tag systems. Write a program that reads in a binary string from the command line and applies the following (00, 1101) tag-system: if the first bit is 0, delete the first three bits and append 00; if the first bit is 1, delete the first three bits and append 1101. Repeat as long as the string has at least 3 bits. Try to determine whether the following inputs will halt or go into an infinite loop: 10010, 100100100100100100. Use a queue.
Text editor buffer. Implement an ADT for a buffer in a text editor. It should support the following operations:
- insert(c): insert character c at cursor
- delete: delete and return the character at the cursor
- left: move the cursor one position to the left
- right: move the cursor one position to the right
- get(i): return the ith character in the buffer
Hint: use two stacks.
Topological sort. You have to sequence the order of N jobs on a processor. Some of the jobs must complete before others can begin. Specifically, you are given a list of order pairs of jobs (i, j). Find a sequence of the jobs such that for each pair (i, j) job i is scheduled before job j. Use the following algorithm.... For each node, maintain a list of outgoing arcs using a queue. Also, maintain the indegree of each node. Finally, maintain a queue of all nodes whose indegree is 0. Repeatedly delete a node with zero indegree, and delete all of its outgoing arcs. Write a program TopologicalSorter.java to accomplish this.
Alternate application: prerequisites for graduating in your major. Must take COS 126 and COS 217 before COS 341, etc. Can you graduate?
PERT / CPM. Modify the previous exercise to handle weights (i, j, w) means job i is scheduled at least w units of time before job j.