Oct 7: Stacks, Queues, Dequeues


Code discussed in lecture

Analysis of Algorithms

I ended last class with a problem for people to work on before this class. Suppose you have a program that runs the insertion sort algorithm, whose worst and average case run times are Θ(n2), where n is the number of items to sort. Someone has given you a list of 10,000 randomly ordered things to sort. Your program takes 0.1 seconds. Then you are given a list of 1,000,000 randomly ordered things to sort. How long do you expect your program to take? Should you wait? Get coffee? Go to dinner? Go to bed? How can you decide?

The expected run time for insertion sort on random data is Θ(n2). The means that the run time approaches cn2 asymptotically. 10,000 is fairly big - the lower-order terms shouldn't have much effect. Therefore we approximate the actual function for the run time by f(n) = cn2.

There are two ways we can solve this. The more straighforward way (and the way that will work for run times like Θ(n log n)) is to solve for c:

f(10,000) = c 10,0002 = 0.1
c = 0.1/(104)2 = 10-9

Therefore we can approximate f(n) as:

f(n) = 10-9n2

Plugging in n = 1,000,000 we get:

f(1,000,000) = 10-9 (106)2 = 1000

We therefore estimate 1000 seconds or a 16.666 minutes. Time enough to get a cup of coffee, but not to go to dinner.

We can use a shortcut for polynomials. If the run time is approximately cnk for some k, then what happens to the run time if we change the input size by a factor of p? That is, the old input size is n and the new input size is pn. Thus if

f(n) = cnk

then

f(pn) = c(pn)k = pkcnk = pkf(n)

Therefore changing the input size by a factor of p changes the run time by a factor of pk. In the problem I gave you, p = 1,000,000/10,000 = 100 and k = 2, so the run time changes by a factor of 10,000. So the time is 10,000 times 0.1, or 1000 seconds.

Suppose that you were running mergesort instead of insertion sort in the example above. Merge sort's run time is Θ(n log n). We approximate the run time as f(n) = cn log n. Note that log210,000 = 13.29. Solving for c gives:

f(10,000) = c 10,000 log 10,000 = c 10,000 (13.29) = 0.1
c = 0.1/132,900 = 7.52 x 10-7
f(n) = (7.53 x 10-7) n log n

Plugging in n = 1,000,000 and using the fact that log 1,000,000 is a bit less than 20 gives:

f(1,000,000) = (7.53 x 10-7) 1,000,000 log 1,000,000 = .753 x 20 = 15.05

So the run time in this case is 15 seconds. Might as well wait for it to finish.

Stacks

A stack is a LIFO (Last In, First Out) data structure. The book compares a stack to a spring-loaded stack of cafeteria trays or a pez machine. The ADT Stack has at least the following operations (in addition to a constructor to create an empty stack):

So what good is a stack? It has many, many applications. You already know that the run-time stack handles allocating memory in method calls and freeing memory on returns. (It also allows recursion). A stack is an easy way to reverse a list or string: push each item on the stack then pop them all off. They come off in the opposite order that they went on. They are good for matching parentheses or braces or square brackets or open and close tags in HTML.

A stack is also how an HP calculators handle reverse Polish notation. In this notation the operator follows both operands, and no parentheses are needed. So the expression (3 + 5) * (4 - 6) becomes 3 5 + 4 6 - *. To evaluate it push operands onto the stack when you encounter them. When you reach an operator, pop the top two things off the stack and apply the operator to them. (The first popped becomes the second operand in the operation.) Push the result of the operation back on the stack. At the end there is a single value on the stack, and that is the value of the expression. (Demonstrate on the expression above.)

A stack is also how you can do depth first search of a maze or a graph. Let's consider a maze. Start by pushing the start square onto the stack. The repeatedly:

  1. pop the stack to get the next square to visit
  2. push all unvisited adjacent squares onto the stack

Quit when you reach the goal square.

Implementing a stack

Stack is an ADT, so it makes sense to have an interface to specify the operations. The interface CS10Stack has the operations given above.

The class java.util.Stack also has these operations, but instead of the name isEmpty they use empty. It also has an additional operation, size.

The book has its own version of the ADT, but instead of the name peek they use top, and they also add size. You would think that computer scientists could agree on a standard set of names! Well, at least we all agree on push and pop!

One question is how to handle pop or peek on an empty stack. Both Java and the book throw an exception. CS10Stack is more forgiving: it returns null. Either can work.

How do we implement a stack? A simple option is to use an array. The implementation has two instance variables: the array stack and an int called top that keeps track of the position of the top of the stack. In an empty stack top == -1. (Draw the picture.) To push add 1 to top and save the thing pushed in stack[top]. To peek just return stack[top] (after checking that top >= 0). pop is peek but with a top--.

This implementation is fast (all operations are O(1)) and it is space efficient (except for the unused part of the array). The drawback is that the array can fill up, and you might get an exception on push as well.

An alternative that avoids that problem uses a linked list. A singly linked list suffices. The top of the stack is the head of the list. The push operation is add to the front of the list and the pop is remove from the front of the list. All operations are O(1) in this implementation, also. You need to have space for the links in the linked list, but you never have empty space as you do in the array implementation.

A compromise that avoids the problem of the array being full is to use an ArrayList. To push you add to the end of the ArrayList and to pop you remove the last item. The ArrayList can grow, so it never becomes full. The code to do this is in ArrayListStack.java. Note that you don't even need to keep track of the top! The ArrayList does it for you.

Do these operations all take O(1) time? It looks like it, as long as add and remove at the end of the ArrayList are O(1) time. The remove is O(1). The add usually is, but sometimes can take longer.

To understand why this is the case we need to look at how an ArrayList is implemented. The underlying data structure is an array. There is also a variable to keep track of the size, from which we can easily get the last occupied position in the array. Adding to the end just increases the size by 1 and assigns the thing added to the next position. However, what happens when the array is full? A new array is allocated and everything is copied to the new array. This takes time O(n), where n is the number of things in the ArrayList. When this happens the push operation takes O(n) time.

If this could happen after each add the process would be very slow. It would in fact take time n2 to add n things to the end of the ArrayList. This is too slow. So what happens is that when the ArrayList is full the new array allocated is not one bigger than the old one. One option is to double the size of the array. Then a lot of add operations can happen before the array needs to be copied again.

Because of this, n add operations will never take more than O(n) time. This is O(1) amortized time. Amortization is what accountants do when saving up to buy an expensive item like a computer. Suppose that you want to buy a computer every 3 years and it costs $1500. One way to think about this is to have no cost the first two years and $1500 the third year. An alternative is to set aside $500 each year. In the third year you can take the accumulated $1500 and spend it on the computer. So the computer costs $500 a year, amortized. (In tax law it goes the other direction - you spend the $1500, but instead of being able to deduct the whole thing the first year you have to spead it over the 3 year life of the computer, and you deduct $500 a year.)

For the ArrayList case, we can think in terms of tokens that can pay for copying something into the array. We charge 3 tokens for each add. One pays for adding the item to the array and two are set aside for later. Suppose that we have just expanded the array from size n to size 2n and copied the items in the old array to the first n positions of the new array. We have no accumulated tokens. The last n positions of the array are empty, so we will be able to do n add operations before the new array is full with 2n items in it. Each add sets aside 2 tokens. After n add operations we will have accumulated 2n tokens. That is enough to pay for copying all 2n things in the array when we do the next add and have to double the array size again. Therefore the cost is O(1) per add operation, amortized. (The current implementation of Java makes the new array 3/2 times the size of the old array to waste less space, but the argument can be modified to show that a charge of 4 tokens works.)

Queues

Queues are FIFO (First In, First Out). "Queueing up" is a mostly British way of saying standing in line. And a Queue data structure mimics a line at a grocery store or bank where people join at the back, are served when they get to the front, and nobody is allowed to cut into the line. The ADT Queue has at at least the following operations (in addition to a constructor to create an empty Queue):

What good is queue? An obvious answer is that it is useful in simulations of lines at banks, toll booths, etc. But more important are the queues within computer systems for things like printers. When you submit a print job you are enqueued. When you get to the front of the line you are dequeued and get to print. Time sharing systems use round-robin scheduling. The first job is dequeued and run for a fixed period of time or until it blocks for I/O or some other reason. Then it is enqueued. This repeats as long as there are jobs in the queue. New jobs are enqueued. Jobs that finish leave the system instead of enqueueing.This way every job gets a fair share of the CPU. The book shows how to solve the Josephus problem using a queue. It is basically a round-robin scheduler, where every kth job is killed instead of being enqueued again.

A queue can also be used to search a maze. The same process is used as for the stack, but with a queue as the ADT. This leads to breadth-first search, and will find the shortest path through the maze. (Demonstrate.)

Implementation of Queues

An obvious way to implement queues is to use a linked list. A singly linked list suffices, if it includes a tail pointer. Enqueue at the tail and dequeue from the head. All operations are Θ(1). Doing it the other way works for a DLL. For an SLL you keep having to run down the entire list to find the predecessor to the tail, so this operation is Θ(n) time. Even using a currentPred reference as we did in PS-2 won't help, because after you delete the tail you have to search the list to find the new tail.

The textbook presents a Queue interface and part of an implementation using an SLL. They also include a size method. The interface CS10Queue has the methods given above, and LinkedListQueue is an implementation that uses a DLL. It could be changed to use an SLL by changing one declaration and one constructor call. All operations would still be Θ(1).

Java also has a Queue interface. It does not use the conventional names. Instead of enqueue it has add and offer. Instead of front it has element and peek. Instead of dequeue it has remove and poll. Why two choices for each? The first choice in each pair throws an exception if it fails. The second fails more gracefully, returning false if offer fails (because the queue is full) and null if peek or poll is called on an empty queue. At least isEmpty and size keep their conventional names.

There are a number of Java implementations: ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingQueue, and LinkedList among them. LinkedList is probably the most common implementation used for normal purposes.

A blocking queue is a bounded buffer used for interprocess communication. The Unix operating system makes it easy to connect programs using "pipes", where the output of the first program becomes the input of the second. The first program is the producer and the second program is the consumer. The producer calls offer to enqueue and the consumer calls poll to dequeue. If the queue is full when the producer calls offer the producer blocks (waits) until something is removed from the queue. If the queue is empty when the consumer calls poll the consumer blocks until something is added to the queue. (Draw picture.)

It may seem strange to have an ArrayBlockingQueue and ArrayDeque. An array or an ArrayList seem unpromising as a data structure for implementing a queue. You could have an array (or ArrayList) where you enqueue at the end and dequeue from the front, but each dequeue requires moving everything else in the array (or ArrayList) one position forward. Enqueuing at the front and dequeueing from the end makes dequeuing fast, but now enqueueing requires moving everything else in the array (or ArrayList) one postion back.

You can make things more efficient if when dequeueing from the front of an array you simply leave the first spot empty and remember that the front of the queue is at the second position. By having two indicies f and r (for front and rear) you can make both enqueue and dequeue Θ(1) time. (Demonstrate with a diagram on the board.) However, when r reaches the end of the array you are stuck.

Or are you? There are probably a lot of free spaces at the front of the array. Suppose that you wrap around and start using them to hold items in the queue? If r < f this indicates that the queue has wrapped around. The book shows how to implement this. They have f contain the index of the first item in the queue and r contain the index of the space beyond the last item (the place were a new item should be enqueued). Then the way to indicate an empty queue is to have f == r. But this would be the same thing as a full queue! Therefore we always have to leave an empty space. An interesting thing is that if N is the size of the array, then (N - f + r) % N is the size of the queue. This works whether the queue has f < r, f == r, or f > r. (Draw diagrams and show why.)

Deques

A deque (pronounced "deck") is a double-ended queue. You can add or delete from either end. A minimum set of operations is:

Additional operations include:

The deque can be used as a stack, as a queue, or as something more complex. In fact, the Java documentation recommends using a Deque instead of the legacy Stack class when you need a stack. This is because the Stack class, which extends the Vector class, includes non-stack operations (e.g. searching through the stack for an item). (Vector was replaced by ArrayList and is deprecated.)

The way to implement a dequeue is with a DLL with head and tail pointers, for example SentinelDLL. If you look at the methods you will see that all of these operations are already there except for the two remove operations and size(). The remove operations can be implemented as a getFirst followed by a remove and a getLast followed by a remove. The size operation can be left out or can be implemented by adding a count instance variable to keep track of the number of items in the deque. All of these operations require Θ(1) time.

It is also possible to use an array with wrapping to implement a deque. The structure is the same as for a queue, but f and r can move forward or backward.

Once again, Java provides two versions of each of each deque operation. The two "add" operations have corresponding "offer" operations (offerFirst and offerLast). The two "remove" operations have corresponding "poll" operations, and the two "get" operations have corresponding "peek" operations. These alternate operations do not throw exceptions. The Java implementations are ArrayDeque, LinkedBlockingDeque, and LinkedList.