This content is archived!For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.
The following is a diagram of a queue. It is depicted as a linear structure. The first element is called the front. It is the next element to be removed. Conversely, the last element is called the back. It is the most recently inserted element.
Elements may only be inserted to the back and removed from the front.
To understand how a queue might be used to solve programming problems, let’s solve a simple problem:
There are N customers waiting in line, each wanting to buy a certain amount of bread slices. Q events occur, where each one is one of two types:
Type 1: A customer goes to the back of the line, with a certain amount of bread slices.
Type 2: The customer at the front of the link leaves the line without purchasing any bread.
Everyone remaining buys the bread they have. Output how many slices of bread are sold.
To solve this problem, use a queue to represent the customers waiting in line, as shown below:
When an event of type 1 occurs, we add the customer to the back of the line, as shown below:
When an event of type 2 occurs, we remove the customer at the front of the line, as shown below:
Finally, after all Q events are over, we can simply sum up all the bread slices held by customers remaining in the line, as shown below:
Queues are extremely important data structures that are used in many programming problems, especially in the field of graph theory, where they are most commonly associated with BFS algorithms. While they are rarely the only part of a solution to a problem, they are used as utility data structures in many solutions.