STACKS & QUEUES

Princeton 1
Stacks and queues. In this section, we introduce two
closely-related data types for manipulating arbitrarily
large collections of objects: the stack and the queue.
Each is defined by two basic operations: insert a new
item, and remove an item. When we insert an item,
our intent is clear. But when we remove an item, which
one do we choose? The rule used for a queue is to
always remove the item that has been in the collection
the most amount of time. This policy is known as first-
in-first-out or FIFO. The rule used for a stack is to
always remove the item that has been in the collection
the least amount of time. This policy is known as last-
in first-out or LIFO.

Princeton 2
Pushdown stacks. A pushdown stack (or just a stack) is a
collection that is based on the last-in-first-out (LIFO)
policy. When you click a hyperlink, your browser displays
the new page (and inserts it onto a stack). You can keep
clicking on hyperlinks to visit new pages. You can always
revisit the previous page by clicking the back button
(remove it from a stack). The last-in-first-out policy
offered by a pushdown stack provides just the behavior
that you expect.

Princeton 3
By tradition, we name the stack insert method push()
and the stack remove operation pop(). We also include a
method to test whether the stack is empty. The
following API summarizes the operations:

The asterisk indicates that we will be considering more

than one implementation of this API.

Princeton 4
Array implementation. Representing stacks with arrays
is a natural idea. The first problem that you might
encounter is implementing the constructor
ArrayStackOfStrings(). An instance variable a[] with an
array of strings to hold the stack items is clearly needed,
but how big should it be? For the moment, We will
finesse this problem by having the client provide an
argument for the constructor that gives the maximum
stack size. We keep the items in reverse order of their
arrival. This policy allows us to add and remove items at
the end without moving any of the other items in the
stack.

Princeton 5
We could hardly hope for a simpler implementation of
ArrayStackOfStrings.java: all of the methods are one-
liners! The instance variables are an array a[] that hold
the items in the stack and an integer N that counts the
number of items in the stack. To remove an item, we
decrement N and then return a[N]; to insert a new
item, we set a[N] equal to the new item and then
increment N. These operations preserve the following
properties: the items in the array are in their insertion
order the stack is empty when the value of N is 0 the top
of the stack (if it is nonempty) is at a[N-1]

Princeton 6
Princeton 7
The primary characteristic of this implementation is that
the push and pop operations take constant time. The
drawback of this implementation is that it requires the
client to estimate the maximum size of the stack ahead
of time and always uses space proportional to that
maximum, which may be unreasonable in some
situations.

Princeton 8
Linked lists. For classes such as stacks that implement
collections of objects, an important objective is to
ensure that the amount of space used is always
proportional to the number of items in the collection.
Now we consider the use of a fundamental data
structure known as a linked list that can provide
implementations of collections (and, in particular,
Stacks) that achieves this important objective.

Princeton 9
A linked list is a recursive data structure defined as
follows: a linked list is either empty (null) or a reference
to a node having a reference to a linked list. The node in
this definition is an abstract entity that might hold any
kind of data in addition to the node reference that
characterizes its role in building linked lists. With object-
oriented programming, implementing linked lists is not
difficult. We start with a simple example of a class for
the node abstraction:

class Node {
String item;
Node next;
}

Princeton 10
A Node has two instance variables: a String and a Node. The String
is a placeholder in this example for any data that we might want to
structure with a linked list (we can use any set of instance
variables); the instance variable of type Node characterizes the
linked nature of the data structure. Now, from the recursive
definition, we can represent a linked list by a variable of type Node
just by ensuring that its value is either null or a reference to a Node
whose next field is a reference to a linked list.
We create an object of type Node by invoking its (no-argument)
constructor. This creates a reference to a Node object whose
instance variables are both initialized to the value null. For example,
to build a linked list that contains the items "to", "be", and "or", we
create a Node for each item:
Node first = new Node();
Node second = new Node();
Node third = new Node();

Princeton 11
and set the item field in each of the nodes to the desired
item value:
first.item = "to";
second.item = "be";
third.item = "or";
and set the next fields to build the linked list:
first.next = second;
second.next = third;
third.next = null;

Princeton 12
Princeton 13
When tracing code that uses linked lists and other linked
structures, we use a visual representation of the
changes where we draw a rectangle to represent each
object we put the values of instance variables within the
rectangle we depict references as arrows that point to
the referenced object This visual representation
captures the essential characteristic of linked lists and
allows us to focus on the links.

Princeton 14
Insert. Suppose that you want to insert a new node into a linked list. The
easiest place to do so is at the beginning of the list. For example, to insert
the string "not" at the beginning of a given linked list whose first node is
first, we save first in oldfirst, assign to first a new Node, assign its item field
to "not" and its next field to oldfirst.

Princeton 15
Remove. Suppose that you want to remove the first node from a list. This
operation is even easier: simply assign to first the value first.next.
Normally, you would retrieve the value of the item (by assigning it to some
String variable) before doing this assignment, because once you change
the value of first, you may not have any access to the node to which it was
referring. Typically, the node object becomes an orphan, and the memory
it occupies is eventually reclaimed by the Java memory management
system.

Princeton 16
These two operations take constant time (independent
of the length of the list).
Implementing stacks with linked lists. Program
LinkedStackOfStrings.java uses a linked list to implement
a stack of strings. The implementation is based on a
nested class Node like the one we have been using. Java
allows us to define and use other classes within class
implementations in this natural way. The class is private
because clients do not need to know any of the details of
the linked lists.

Princeton 17
Princeton 18
List traversal. One of the most common operations we
perform on collections is to iterate through the items in
the collection. For example, we might wish to
implement the toString() method to facilitate debugging
our stack code with traces. For ArrayStackOfStrings, this
implementation is familiar:
public String toString() {
String s = "";
for (int i = 0; i < N; i++)
s += a[i] + " ";
return s;
}

Princeton 19
As usual, this solution is intended for use only when N is small - it takes
quadratic time because string concatenation takes linear time. Our focus
now is just on the process of examining every item. There is a
corresponding idiom for visiting the items in a linked list: We initialize a
loop index variable x that references the the first Node of the linked list.
Then, we find the value of the item associated with x by accessing x.item,
and then update x to refer to the next Node in the linked list assigning to it
the value of x.next, repeating this process until x is null (which indicates
that we have reached the end of the linked list). This process is known as
traversing the list, and is succinctly expressed in this implementation of
toString() for LinkedStackOfStrings:
public String toString() {
String s = "";
for (Node x = first; x != null; x = x.next)
s += x.item + " ";
return s;
}

Princeton 20
Array doubling. Next, we consider an approach to
accommodating arbitrary growth and shrinkage in a data
structure that is an attractive alternative to linked lists.
As with linked lists, The idea is to modify the array
implementation to dynamically adjust the size of the
array a[] so that it is (i) both sufficiently large to hold all
of the items and (ii) not so large as to waste an excessive
amount of space. Program DoublingStackOfStrings.java
is a modification of ArrayStackOfStrings.java that
achieves these objectives.

Princeton 21
First, in push(), we check whether the array is too
small. In particular, we check whether there is room for
the new item in the array by checking whether the stack
size N is equal to the array size a.length.
If not, we just insert it with a[N++] = item as before;
if so, we double the size of the array, by creating a new
array of twice the size, copying the stack items to the
new array, and resetting the a[] instance variable to
reference the new array. Similarly, in pop(), we begin
by checking whether the array is too large, and we halve
its size if that is the case.

Princeton 22
Princeton 23
Parameterized data types. We have developed one stack
implementation that allows us to build a stack of one particular
type (String). In other applications we might need a stack of
integers or a stack of oranges or a queue of customers.
Create a stack of Objects. We could develop one stack
implementation StackOfObjects.java whose elements are of type
Object. Using inheritance, we can insert an object of any type.
However, when we pop it, we must cast it back to the appropriate
type. 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:

Princeton 24
StackOfObjects stack = new StackOfObjects();
Apple a = new Apple();
Orange b = new Orange();

stack.push(a);
stack.push(b);

// throws a classCastException
a = (Apple) (stack.pop());

b = (Orange) (stack.pop());

Princeton 25
This toy example illustrates a basic problem. When we use
type casting with an implementation such as Stack 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.

Princeton 26
Java generics. We use Java generics to limit the objects on a stack or queue
to all be of the same type within a given application. The primary benefit is
to discover type mismatch errors at compile-time instead of run-time. This
involves a small bit of new Java syntax. We name the generic class Stack. It
is identical to StackOfStrings except that we replace every occurrence of
String with Item and declare the class as follows:
public class Stack<Item>
Program Stack.java implements a generic stack using this approach. The
client
Stack<Apple> stack = new Stack<Apple>();
Apple a = new Apple();
Orange b = new Orange();
stack.push(a);
stack.push(b); // compile-time error
Program DoublingStack.java implements a generic stack using an array. For
technical reasons, one cast is needed when allocating the array of generics.

Princeton 27
Autoboxing. We have designed our stacks so that they can store
any generic object type. We now describe the Java language
feature, known as auto-boxing and auto-unboxing, that enables us
to reuse the same code with primitive types as well. 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.

Stack<Integer> stack = new Stack<Integer>();

// auto-boxing (converts int to Integer)

stack.push(17);

// auto-unboxing (converts Integer to int)

int a = stack.pop();

Princeton 28
The value 17 is automatically cast to be of type Integer
when we pass it to the push() method. The pop()
method returns an Integer, and this value is cast to an
int when we assign it to the variable a.
We should be aware of what is going on behind the
scenes since this can affect performance.
Java supplies built-in wrapper types for all of the primitive
types: Boolean, Byte, Character, Double, Float,
Integer, Long, and Short. These classes consist primarily of
static methods (e.g., Integer.parseInt(),
Integer.reverse()), but they also include some non-static
methods (compareTo(), equals(), doubleValue()).

Princeton 29
Queue. A queue supports the insert and remove
operations using a FIFO discipline. By convention, we
name the queue 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.

public class Queue<Item> {

public boolean isEmpty();
public void enqueue(Item item);
public Item dequeue();
}

Princeton 30
Linked list implementation. Program Queue.java
implements a FIFO queue of strings using a linked list.
Like Stack, we maintain a reference first to the least-
recently added Node on the queue. For efficiency, we
also maintain a reference last to the least-recently added
Node on the queue.

Princeton 31
Princeton 32
Array implementation. Similar to array implementation
of stack, but a little trickier since need to wrap-around.
Program DoublingQueue.java implements the queue
interface. The array is dynamically resized using repeated
doubling.
Iteration. Sometimes the client needs to access all of the
items of a collection, one at a time, without deleting
them. To maintain encapsulation, we do not want to
reveal the internal representation of the queue (array or
linked list) to the client. "Decouple the thing that needs
to traverse the list from the details of getting each
element from it." We solve this design challenge by using
Java's java.util.Iterator interface:

Princeton 33
 public interface Iterator<Item> {
boolean hasNext();
Item next();
void remove(); // optional
}
That is, any data type that implements the Iterator interface
promises to implement two methods:

hasNext() and next(). The client uses these methods to access

the list elements one a time using the following idiom.
Queue<String> queue = new Queue<String>();
...
Iterator<String> i = queue.iterator();
while (i.hasNext()) {
String s = i.next();
StdOut.println(s);
}
Princeton 34
Queue iterator in Java. Queue.java illustrates how to implement an Iterator
when the items are stored in a linked list.
public Iterator iterator() {
return new QueueIterator(); }
private class QueueIterator implements Iterator<Item> {
Node current = first;
public boolean hasNext() { return current != null; }
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
It relies on a private nested subclass QueueIterator that implements the
Iterator interface. The method iterator() creates an instance of type
QueueIterator and returns it as an Iterator. This enforces the iteration
abstraction since the client will only the items through the hasNext() and
next() methods. The client has no access to the internals of the Queue or
even the QueueIterator. It is the client's responsibility to only add elements
to the list when no iterator is in action.
Princeton 35
Enhanced for loop. Iteration is such a useful abstraction
that Java provides compact syntax (known as the
enhanced for loop) to iterate over the elements of a
collection (or array).

Iterator<String> i = queue.iterator();
while (i.hasNext()) {
String s = i.next();
StdOut.println(s);
}
for (String s : queue)
StdOut.println(s);

Princeton 36
To take advantage of Java's enhanced foreach syntax, the
data type must implement Java's Iterable interface.
public interface Iterable<Item> {
Iterator<Item> iterator();
}
That is, the data type must implement a method named
iterator() that returns an Iterator to the underlying
collection. Since our Queue ADT now includes such a
method, we simply need to declare it as implementing
the Iterable interface and we are ready to use the
foreach notation.
public class Queue<Item> implements Iterable<Item>

Princeton 37
Stack and queue applications. Stacks and queues have numerous
useful applications.
Queue applications: Computing applications: serving requests of a
single shared resource (printer, disk, CPU), 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.
Playlist for jukebox - add songs to the end, play from the front of
the list. Interrupt handling: When programming a real-time system
that can be interrupted (e.g., by a mouse click or wireless
connection), it is necessary to attend to the interrupts immediately,
before proceeding with the current activity. If the interrupts should
be handles in the same order they arrive, then a FIFO queue is the
appropriate data structure.

Princeton 38
Arithmetic expression evaluation. Program Evaluate.java
evaluates a fully parenthesized arithmetic expression.
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.

Princeton 39
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.

Princeton 40
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.

Princeton 41