Flood Filling with Stacks or Queues
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.
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. 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!
Queues are similar to stacks in that a queue consists of a sequence of items, and there are restrictions about how items can be added to and removed from the list. However, a queue has two ends, called the front and the back of the queue. Items are always added to the queue at the back and removed from the queue at the front. The operations of adding and removing items are called enqueue and dequeue. An item that is added to the back of the queue will remain on the queue until all the items in front of it have been removed. This should sound familiar. A queue is like a "line" or "queue" of customers waiting for service. Customers are serviced in the order in which they arrive on the queue.
A queue can hold items of any type. For a queue of ints, the enqueue and dequeue operations can be implemented as instance methods in a "QueueOfInts" class. We also need an instance method for checking whether the queue is empty:
void enqueue(int N) -- Add N to the back of the queue.
int dequeue() -- Remove the item at the front and return it.
boolean isEmpty() -- Return true if the queue is empty.
A queue can be implemented as a linked list or as an array. An efficient array implementation is a little trickier than the array implementation of a stack, so I won't give it here. In the linked list implementation, the first item of the list is the front of the queue. Dequeueing an item from the front of the queue is just like popping an item off a stack. The back of the queue is at the end of the list. Enqueueing an item involves setting a pointer in the last node on the current list to point to a new node that contains the item. To do this, we'll need a command like "tail.next = newNode;", where tail is a pointer to the last node in the list. If head is a pointer to the first node of the list, it would always be possible to get a pointer to the last node of the list by saying:
Node tail; // This will point to the last node in the list.
tail = head; // Start at the first node.
while (tail.next != null) {
tail = tail.next;
}
// At this point, tail.next is null, so tail points to
// the last node in the list.
However, it would be very inefficient to do this over and over every time an item is enqueued. For the sake of efficiency, we'll keep a pointer to the last node in an instance variable. We just have to be careful to update the value of this variable whenever a new node is added to the end of the list. Given all this, writing the QueueOfInts class is not very difficult:
public class QueueOfInts {
private static class Node {
// An object of type Node holds one of the items
// in the linked list that represents the queue.
int item;
Node next;
}
private Node head = null; // Points to first Node in the queue.
// The queue is empty when head is null.
private Node tail = null; // Points to last Node in the queue.
void enqueue( int N ) {
// Add N to the back of the queue.
Node newTail = new Node(); // A Node to hold the new item.
newTail.item = N;
if (head == null) {
// The queue was empty. The new Node becomes
// the only node in the list. Since it is both
// the first and last node, both head and tail
// point to it.
head = newTail;
tail = newTail;
}
else {
// The new node becomes the new tail of the list.
// (The head of the list is unaffected.)
tail.next = newTail;
tail = newTail;
}
}
int dequeue() {
// Remove and return the front item in the queue.
// Note that this can throw a NullPointerException.
int firstItem = head.item;
head = head.next; // The previous second item is now first.
if (head == null) {
// The queue has become empty. The Node that was
// deleted was the tail as well as the head of the
// list, so now there is no tail. (Actually, the
// class would work fine without this step.)
tail = null;
}
return firstItem;
}
boolean isEmpty() {
// Return true if the queue is empty.
return (head == null);
}
} // end class QueueOfInts
Queues are typically used in a computer (as in real life) when only one item can be processed at a time, but several items can be waiting for processing. For example:
- In a Java program that has multiple threads, the threads that want processing time on the CPU are kept in a queue. When a new thread is started, it is added to the back of the queue. A thread is removed from the front of the queue, given some processing time, and then -- if it has not terminated -- is sent to the back of the queue to wait for another turn.
- Events such as keystrokes and mouse clicks are stored in a queue called the "event queue". A program removes events from the event queue and processes them. It's possible for several more events to occur while one event is being processed, but since the events are stored in a queue, they will always be processed in the order in which they occurred.
- A ServerSocket has an associated queue which contains connection requests that have been received but not yet serviced. The ServerSocket's accept() method gets the next connection request from the front of this queue.
Queues are said to implement a FIFO policy: First In, First Out. Or, as it is more commonly expressed, first come, first served. Stacks, on the other hand implement a LIFO policy: Last In, First Out. The item that comes out of the stack is the last one that was put in. Just like queues, stacks can be used to hold items that are waiting for processing (although in applications where queues are typically used, a stack would be considered "unfair").
To get a better handle on the difference between stacks and queues, consider the applet shown below. When you click on a white square in the grid, the applet will gradually mark all the squares in the grid, starting from the one where you click. To understand how the applet does this, think of yourself in the place of the applet. When the user clicks a square, you are handed an index card. The location of the square -- its row and column -- is written on the card. You put the card in a pile, which then contains just that one card. Then, you repeat the following: If the pile is empty, you are done. Otherwise, take an index card from the pile. The index card specifies a square. Look at each horizontal and vertical neighbor of that square. If the neighbor has not already been encountered, write its location on an index card and put the card in the pile.
While a square is in the pile, waiting to be processed, it is colored red. When a square is taken from the pile and processed, its color changes to gray. Eventually, all the squares have been processed and the procedure ends. In the index card analogy, the pile of cards contains all the red squares.
The applet can use your choice of three methods: Stack, Queue, and Random. In each case, the same general procedure is used. The only difference is how the "pile of index cards" is managed. For a stack, cards are added and removed at the top of the pile. For a queue, cards are added to the bottom of the pile and removed from the top. In the random case, the card to be processed is picked at random from among the cards in the pile. The order of processing is very different in these three cases.
You should experiment with the applet to see how it all works. Try to understand how stacks and queues are being used. Try starting from one of the corner squares. While the process is going on, you can click on other white squares, and they will be added to the pile. When you do this with a stack, you should notice that the square you click is processed immediately, and all the red squares that were already waiting for processing have to wait. On the other hand, if you do this with a queue, the square that you click will wait its turn. The source code for this applet can be found in the file DepthBreadth.java.