CS 240: Lecture 12 – Stacks and Queues
Dear students:
It’s time to introduce a new abstract data type: the queue. Like the stack, queue is only an interface. It can be implemented many different ways. In fact, Java doesn’t even have a Queue class. Today we’ll examine some of the possible implementations and look at some situations in which stacks and queues are useful.
Muddiest Points
But first I wanted to address a few of your muddiest points. Here’s a sample of your questions:
I would like to see some example code of stack implementations walked through on the board. How to decide which data structure to use then a step by step example of how to develop one in Java.
The muddiest point this week for me was understanding why would we ever use a non doubly linked list. It doesn’t seem particularly useful ever to use a single linkedlist structure. Could it be to protect previous nodes?
My confusion is with the book’s description of the “break-even point”, at least that’s what I think it is called. The book gives a formula, n>DE/(P+E), but I am still incredibly confused as to what each variable means, the reason for implementation, and what a break-even point describes.
Queue
A queue is a linear collection processed in oldest-to-newest order. This is in contrast to a stack, which is processed in newest-to-oldest order. Items are enqueued and dequeued, as opposed to pushed and popped. What we call lines at the bank or grocery store are often called queues in the British Commonwealth. The oldest end of a queue is called the front and the newest end is called the back.
Imagine designing a printer driver. Jobs might come in faster than the printer can process them. Your driver spools them, or stores them in a collection until the printer is free. That collection is usually a queue. The first job in is the first job out.
Imagine designing an ultra-private chat client that showed you only one message at a time and destroyed it as soon as you read it. For the conversation to make sense, it should queue up unread messages.
Like a stack, it is an abstract data type. It could be implemented with an array list or a linked list. Items are added at one end of the structure and removed at the other. If new items are enqueued in an array queue by prepending them to the array, then the operations have the following complexities:
| operation | array list | linked list |
|---|---|---|
| enqueue | $\Theta(n)$ | $\Theta(1)$ |
| dequeue | $\Theta(1)$ | $\Theta(1)$ |
| peek | $\Theta(1)$ | $\Theta(1)$ |
| size | $\Theta(1)$ | $\Theta(1)$ |
| isEmpty | $\Theta(1)$ | $\Theta(1)$ |
If we enqueued new items at the end of an array queue, then the complexities of enqueue and dequeue would flip. It would seem that that we are going to be stuck with a linear time algorithm one way or another. Bummer.
We can get better performance from an array queue if we don’t force the oldest or newest item to be at index 0. Instead, the indices of the first and last elements are allowed to float. Suppose we have this implementation of enqueue:
to enqueue item assert an empty slot increment newIndex with wrapping items[newIndex] = item increment itemCount
And this implementation of dequeue:
to dequeue assert items item = items[oldIndex] increment oldIndex with wrapping decrement itemCount return item
We’ll also assume that newIndex and oldIndex both start at 0. What will an array queue with a capacity of 4 elements look like after this code is executed?
queue = new ArrayQueue() queue.enqueue(4) queue.enqueue(10) queue.enqueue(15) queue.dequeue() queue.enqueue(3) queue.dequeue() queue.dequeue() queue.enqueue(7) queue.enqueue(1)
This implementation with floating indices is called a circular queue. It behaves as if the array circled around in memory.
Stack and Queue Problems
Now let’s example algorithms that make use of stacks and queues.
Postfix Evaluation
Let’s see an example of an algorithm that uses a stack. Support you want to write code to evaluate an arbitrary arithmetic expression. Something of this form:
You might break the expression up into a list of tokens and then iterate through it. You read the 7, the +, and the 5. But you can’t do anything with them. The multiplication operation must happen first. Evaluating expressions requires you to find the operation with the highest precedence, which can be challenging given parentheses and the need to scan the whole expression.
An alternative form was used by some early calculators. Instead of using infix notation, which places the operators between the operands, these calculators used postfix notation, which places the operators after the operands. The expression above has this postfix form:
A postfix expression can be evaluated in one pass through the sequence of tokens. With your neighbors, design an algorithm in pseudocode that evaluates a postfix expression.
Maze
Suppose you have dropped a programmable robot at cell (1, 1) of a maze. It must reach the exit. Write an algorithm to do so. The maze provides these methods:
visit(x, y): moves to cell (x, y)isVisited(x, y): returns true if you have visited (x, y)isExited(): returns true if you have visited the exit
We’ll visualize your solutions live.
TODO
- Read 7.14 of OpenDSA.
- Submit Friday’s lab by 11 PM tonight.
See you next time.
P.S. It’s time for a haiku!
Ice cream sounded good
The rest of town got there first
An hour to DQ