We have taken a look at stacks, which implement a LIFO ("last-in, first-out") functionality.
But what if we want to implement a “first-in, first-out”, or FIFO, functionality like a line at Disneyland?
For that, we have a different data type, called a queue.
We can think of the two ends of the queue as the head and the tail. The head is where elements are removed from the queue, and the tail is where they are added to the queue. For linear queues, like the one above, every time an element is removed from the queue, all the other elements are moved up one.
As for stacks, queues have four operators, two basic operators:
enqueue(i)--inserts element i at the tail end of the queue;
dequeue()--removes the element at the head of the queue and return its value.
And two additional operators provided for convenience:
size()--returns current size of the queue;
peek()--peeks at the element at the head of the queue without changing the queue.
All four of these operators have very similar functionality to the four stack operators. In fact they are identical, except for the
enqueue() command which inserts a new element at the tail of the queue, rather than the top of the stack.
Suppose we store data as an array. The first element is the head, where items get removed from the queue, and the last element is the tail, where items get added to the queue. In this way queues are expressed left to right, head to tail.
What does the queue of an initially empty queue look like after the following operations?
1 2 3 4 5
How does the average runtime for “popping” elements off the top of a stack compare with the average runtime for “dequeuing” elements from a queue? (Assume there are at least 100 elements on the stack/queue and that we are using simple arrays to represent the stack and queues in the way outlined in previous slides)
Hint: In our implementation, the head of our queue must always be the first element of our array. What would we have to do for this to remain true after a dequeuing operation?
A) They are about the same.
B) The pop routine takes longer.
C) The dequeue routine takes longer.
We saw from the last example that one of the major downfalls of traditional linear queues is that they can be slow. It takes time to shift all the elements along during a dequeuing.
However, this can be avoided by introducing circular queues.
With circular queues, instead of all the elements needing to shift toward the head, we simply change the position of the head!
You can think of it as a line in Disneyland. When the person at the front of the line gets on the ride, everyone has to shift forward one. If we could somehow redefine the front of the line, it could save everyone the trouble…
OK, OK, this may not be a very practical solution for a Disneyland ride, but in computer science it can save significant runtime!
In fact, circular queues take the runtime down from \(O(n)\) to \(O(1)\).
This is great!
But what happens if we would like to have more elements in the queue than the size of the circle?
One disadvantage to circular queues is that they are limited in total size (i.e. the number of elements in the circle). So when programming a circular queue, make sure the size of the circle is big enough to accommodate the maximum number of elements you will have in your queue.
Let’s suppose that Martha uses a queue to model a waiting list for people wanting to enroll in a swimming class. Currently she has 250 swimmers, and is fully booked. However, she has 1,200 waiting in line to enroll.
Suddenly she has an opening, so the first person on the waiting list can now enroll and be removed from the queue.
If the waiting list is modeled as a typical, non-circular queue, stored in an array, how many elements must be shifted in the array for this update to take place?
Hint: In this type of non-circular queue, the head of the queue must always be at the first index of our array, with every subsequent element stored sequentially afterwards.
You have a stack with \(20\) elements and a queue with \(35\) elements. Then you perform the following set of operations \(80\) times:
Here, the first line above removes the top element of the stack and inserts it into the queue, while the second removes the last element of the queue and insert it into the stack.
How many of the \(55\) total elements are involved in this process? That is, how many distinct elements from the stack and the queue get enqueued, popped, pushed, or dequeued?
Note: This is not asking how many times elements move, but how many elements move.
Stephanie Stacker decides she wants to set up a queue using two stacks. She assumes that stack1 will always contain the data in the “correct” order, so the top of stack1 will represent the tail of the queue where data is added and the bottom will represent the head. Removing from the top of stack1 will always give the most recently added data.
In contrast, when stack2 contains data, it is reversed, with its top representing the head of a queue where data is removed. Removing from its top will always give the oldest data still stored. We will also assume that at any given time at least one stack is completely empty.
With these assumptions, she puts together the following to implement the
And, she implements the
enqueue(i) function as follows:
Will this algorithm work?
Consider the algorithm in the last example. What is the performance of an enqueue operation directly after a dequeue operation?