Introduction
A queue is an abstract data type with two functions, pop and push. Removal from the front is called "pop" or "dequeue". Insertion from the back is called "push" or "enqueue". A queue follows a First In First Out (FIFO) structure meaning the first element pushed should be the first element popped and the last element pushed should be the last element popped.
Imagine you are standing in line for a restaurant. Whoever is first in line will be served first and whoever is last in line will be served last. People can be served while more people join the line and the line may get very long because it takes a while to serve one person while more people join the queue. This is called a queue.
Queues are often used for buffer systems, such as a text message service. The messages that arrive at the server first are relayed first and the messages that arrive later are relayed later. If there are too many text messages in the system such that the rate texts are received overwhelm the number of texts that are sent the buffer may overflow and messages will get dropped. Most of the time this won't happen because the systems are designed to handle large loads, but if there were an emergency that caused everyone to start texting many texts could be dropped.
Example of push:
Example of pop:
Implementations
We can implement a queue most efficiently using a linked list because it uses efficient memory allocation.
| Implementation | Pop | Push |
|---|---|---|
| Linked List | O(1) | O(1) |
Exercises
Given a list of letters representing instructions where the first instruction is executed, output what the final list should look like after N instructions are executed.
First instruction:
- A. Add B to the end of the list of instructions
- B. Do nothing
- C. Add two A's to the front of the list of instructions
Example:
- ABC
- BCB
- CB
- AAB
- ABB
- BBB
- BB
- B