Learning Activity: Queues
Overview
Previously, we learned about the stack. The Stack was "Last In, First Out" (LIFO). The queue is characterized as "First In, First Out" (FIFO) and can also be implemented using a variety of data structures including a List. In C# there is a also a built-in Queue class.
Preparation Material
Grocery Story Queue
In the example below, we can see a line at a busy grocery store used to represent a queue. The person next in line for the cashier is called the front and the person at the end of the line is called the back. When the person at the front is removed from the queue we call this a dequeue operation. When a new person joins the queue at the back, we call this an enqueue operation. Note that someone cannot cheat and enter the line in the middle of the queue.
Queues are used when we need to process a collection of requests in a fair and orderly way. Consider the following two common queues used in software: the Web Server Queue and the Reader/Writer Queue.
Web Server Queue
A web server receives numerous HTTP (Hypertext Transfer Protocol) requests for web pages from clients throughout the world. Each request requires the web server to send back information. The amount of time it takes to send that information makes it difficult to respond timely to all requests. This would be similar to a customer service desk that had only one phone. If the customer service agent is helping someone else, then no one would pick up your call. To solve the problem, a queue is used to pick up all the phone calls and transfer you to the customer service agent when they are ready for the next person.
The web server does the same thing. When a request is sent, it is put into a queue until the web server can process the request. In this way, all requests are received and none of them are lost. Queues frequently have a self-imposed maximum size. If a queue is full, then the software may need to send an error message back to the client.
Reader/Writer Queue
Frequently, we have the need to run different software components concurrently (for example, it looks like they are running at the same time). Each component is called a process or a thread. Each process will likely have their own set of variables that are maintained. Frequently, there is need to have shared data between the processes. The diagram below shows a variable which is being shared by multiple processes.
Processes P1 through P6 are all trying to use the variable at the same time. Processes P1, P2, and P3 are reading the variable and processes P4, P5, and P6 are writing to the variable. The concurrent reading is not a problem. However, if everyone tries to both read and write at the same time, new and modified values may be missed or overwritten. One solution is to protect the code that is writing to the shared data so that only one process can change the variable at a time. A queue is used to ensure order and integrity. When a process wants to write, it is enqueued. When a process is dequeued, it is then allowed to modify the shared variable. When the process is done, then the next process is dequeued.
Queues in C#
Queues are an abstraction that you can represent in many ways. You might create your own queue using an fixed array or a list (dynamic array). There is also a built-in data type in the Collections library which provides a Queue for optimal performance.
| Common Queue Operation | Description | C# Code | Performance |
|---|---|---|---|
| enqueue(value) | Adds "value" to the back of the queue | myQueue.Enqueue(value) |
O(1) |
| dequeue() | Removes items from the queue | var value = myQueue.Dequeue() |
O(1) |
| size() | Number of elements in the queue | myQueue.Count |
O(1) |
| empty() | Returns true if the length of the queue is zero. | if (myQueue.Count == 0) |
O(1) |
Because a queue is just an abstraction, you can implement your own queue using a List object. In that case, performance my be worse than it could be since it requires O(n) to add or remove from the front of your List - causing either the Enqueue or Dequeue operation to take longer than O(1).
Here is an example of creating a new built-in queue for characters:
var q = new Queue<char>();
q.Enqueue('A');
char ch = q.Dequeue(); // retrieves the 'A'
Video Discussion (Optional)
The following video is optional. It presents a brief discussion of the topic.
Activity Instructions
Complete each of the following:
- Open the following snippet of code: SimpleQueue.cs (Note: You should not execute this code. After you complete these practice problems, you are welcome to execute the code).
- This code has a varied mix of enqueue and dequeue operations performed on a queue. Individually, manually walk through the code and predict what the final contents of the queue will be. Even if you are good at keeping track of information in your mind, you should use a sheet of paper to keep track of the stack after each step.
- When you are done, compare your your work to this solution. If you have questions, make sure to post them to Microsoft Teams.
Key Terms
- back
- Refers to the location in the queue where an enqueue occurs. The last item put in the queue is found in the back.
- dequeue
- The operation to remove an item from the queue. The item is removed from the front of the queue.
- enqueue
- The operation to add an item to the queue. The item is added to the back of the queue.
- front
- Refers to the location in the queue where a dequeue occurs. The first item put in the queue is found in the front. If you use a dynamic array (List) this is index 0.
- queue
- A data structure that follows a First In, First Out (FIFO) rule. The queue is used both to maintain order in data and to remember data when there is not time to process it.
Submission
When you have completed all of the learning activities for this week, you will return to I-Learn and submit the associated quiz there.
Other Links:
- Return to: Week Overview | Course Home