Stacks and Queues
A LINKED LIST is a particular type of
data structure, made up of objects linked together by pointers. In the previous section,
we used a linked list to store an ordered list of Strings, and we implemented insert, delete,
and find operations on that
list. However, we could easily have stored the list of Strings in an array or Vector, instead of in a linked list. We
could still have implemented insert,
delete, and find operations on the list. The
implementations of these operations would have been different, but their
interfaces and logical behavior would still be the same.
The term abstract data type, or ADT, refers to a set of possible values and a set of
operations on those values, without any specification of how the values are to
be represented or how the operations are to be implemented. An “ordered
list of strings” can be defined as an abstract data type. Any sequence of Strings that is arranged in increasing
order is a possible value of this data type. The operations on the data type
include inserting a new string, deleting a string, and finding a string in the
list. There are often several different ways to implement the same abstract
data type. For example, the “ordered list of strings” ADT can be
implemented as a linked list or as an array. A program that only depends on the
abstract definition of the ADT can use either implementation, interchangeably.
In particular, the implementation of the ADT can be changed without affecting
the program as a whole. This can make the program easier to debug and maintain,
so ADT's are an important tool in software engineering.
In this section, we'll look at two common abstract data types, stacks and queues.
Both stacks and queues are often implemented as linked lists, but that is not
the only possible implementation. You should think of the rest of this section
partly as a discussion of stacks and queues and partly as a case study in ADTs.
A stack consists of a sequence of items, which should be thought of piled
one on top of the other like a physical stack of boxes or cafeteria trays. Only
the top item on the stack is accessible at any given time. It can be removed
from the stack with an operation called pop.
An item lower down on the stack can only be removed after all the items on top
of it have been popped off the stack. A new item can be added to the top of the
stack with an operation called push. We can
make a stack of any type of items. If, for example, the items are values of
type int, then the push and pop
operations can be implemented as instance methods
void push (int newItem) -- Add newItem to top of stack.
int pop() -- Remove the top int from the stack and return it.
It is an error to try to pop an item from an empty stack, so it is important
to be able to tell whether a stack is empty. We need another stack operation to
do the test, implemented as an instance method
boolean isEmpty() -- Returns true if the stack is empty
This describes a “stack of ints” as an abstract data type. This
ADT can be implemented in several ways, but however it is implemented, its
behavior must correspond to the abstract mental image of a stack.

In the linked list implementation of a stack, the top of the stack is
actually the node at the head of the list. It is easy to add and remove nodes
at the front of a linked list — much easier than inserting and deleting nodes
in the middle of the list. Here is a class that implements the “stack of
ints” ADT using a linked list. (It uses a static nested class to represent
the nodes of the linked list. See Section 7.6 for
a discussion of nested classes. If the nesting bothers you, you could replace
it with a separate Node class.)
public class StackOfInts {
private static class Node {
// An object of type Node holds one of the
// items in the linked list that represents the stack.
int item;
Node next;
}
private Node top; // Pointer to the Node that is at the top of
// of the stack. If top == null, then the
// stack is empty.
public void push( int N ) {
// Add N to the top of the stack.
Node newTop; // A Node to hold the new item.
newTop = new Node();
newTop.item = N; // Store N in the new Node.
newTop.next = top; // The new Node points to the old top.
top = newTop; // The new item is now on top.
}
public int pop() {
// Remove the top item from the stack, and return it.
// Note that this routine will throw a NullPointerException
// if an attempt is made to pop an item from an empty
// stack. (It would be better style to define a new
// type of Exception to throw in this case.)
int topItem = top.item; // The item that is being popped.
top = top.next; // The previous second item is now on top.
return topItem;
}
public boolean isEmpty() {
// Returns true if the stack is empty. Returns false
// if there are one or more items on the stack.
return (top == null);
}
} // end class StackOfInts
You should make sure that you understand how the push and pop
operations operate on the linked list. Drawing some pictures might help. Note
that the linked list is part of the private
implementation of the StackOfInts
class. A program that uses this class doesn't even need to know that a linked
list is being used.
Now, it's pretty easy to implement a stack as an array instead of as a
linked list. Since the number of items on the stack varies with time, a counter
is needed to keep track of how many spaces in the array are actually in use. If
this counter is called top, then
the items on the stack are stored in positions 0,
1, …, top-1 in the array. The item in position 0 is on the bottom of the stack, and the
item in position top-1 is on the
top of the stack. Pushing an item onto the stack is easy: Put the item in
position top and add 1 to the value of top. If we don't want to put a limit on
the number of items that the stack can hold, we can use the dynamic array
techniques from Section
8.3. Note that the typical picture of the array would show the stack
“upside down”, with the top of the stack at the bottom of the array.
This doesn't matter. The array is just an implementation of the abstract idea
of a stack, and as long as the stack operations work the way they are supposed
to, we are OK. Here is a second implementation of the StackOfInts class, using a dynamic array:
public class StackOfInts {
private int[] items = new int[10]; // Holds the items on the stack.
private int top = 0; // The number of items currently on the stack.
public void push( int N ) {
// Add N to the top of the stack.
if (top == items.length) {
// The array is full, so make a new, larger array and
// copy the current stack items into it.
int[] newArray = new int[ 2*items.length ];
System.arraycopy(items, 0, newArray, 0, items.length);
items = newArray;
}
items[top] = N; // Put N in next available spot.
top++; // Number of items goes up by one.
}
public int pop() {
// Remove the top item from the stack, and return it.
// Note that this routine will throw an
// ArrayIndexOutOfBoundsException if an attempt is
// made to pop an item from an empty stack.
// (It would be better style to define a new
// type of Exception to throw in this case.)
int topItem = items[top - 1] // Top item in the stack.
top--; // Number of items on the stack goes down by one.
return topItem;
}
public boolean isEmpty() {
// Returns true if the stack is empty. Returns false
// if there are one or more items on the stack.
return (top == 0);
}
} // end class StackOfInts
Once again, the implentation of the stack (as an array) is private to the
class. The two versions of the StackOfInts
class can be used interchangeably. If a program uses one version, it should be
possible to substitute the other version without changing the program.
Unfortunately, though, there is one detail in which the classes behave
differently: When an attempt is made to pop an item from an empty stack, the
first version of the class will generate a NullPointerException
while the second will generate an ArrayIndexOutOfBoundsException.
It would be better to define a new EmptyStackException
class and use it in both versions. In fact, the original description of the
“stack of ints” ADT should have specified exactly what happens when
an attempt is made to pop an item from an empty stack. This is just the sort of
small detail that is often left out of interface specifications, causing no end
of problems!
Source: http://math.hws.edu/eck/cs124/javanotes3/c11/s3.html