A queue is a data structure of ordered entries such that entries can be inserted at one end (called the rear) and removed from the other end (called the front).
Since a queue inserts an item at the rear and removes an item from the front, this means that the first item into the queue is the first one removed. Therefore a queue is a "First In First Out" (FIFO) data structure.
A stack and a queue are very similar data structures. They differ only in the rule that determines which entry is removed first.
Just like a stack, adding items to a queue is called pushing, and removing items from a queue is called popping.
Also like a stack, errors can occur if there is an attempt to push an item onto a full queue or if there is an attempt to pop an item from an empty queue.
A really simple use is to read and print a word.
while there are characters in the input string push the current character onto the queue endwhile while the queue is not empty pop a character off the queue and print it endwhile
A second common use of queues is in simulating real world situations. For example, think of an automatic car wash. You could write a program to determine which type of setting would be most cost effective.
The car wash could have two settings: a fast one that can wash a car in a minute, but uses a lot of soap and water; and a slow setting that takes longer to wash a car, but uses less soap and water.
You could then figure out the number of customers that will be served and how long they will have to wait in line before their car is washed if the slower setting is used. Or if the fast setting is used.
Just like a stack, a queue can be implemented as either a fixed/dynamic array or as a linked list.
Array Implementation
This implementation is similar to that of a stack, except that the top variable would hold the subscript of the front entry and that there must be an extra variable that holds the subscript of the rear entry.
Therefore, to add an entry, the rear subscript will be incremented and then the entry is put in the array at this new rear subscript.
To remove an entry, you retrieve the data at the front of the array and then increment the front subscript. This ensures that the next element is the new front element.
There is a problem with this type of implementation though. What is it?
One way to solve the problem is to ensure that the front item of the queue is always at subscript 0. This means that after an item is popped, all of the following elements must be shifted and then the rear subscript decremented. This will work, but is horribly inefficient.
A better way to solve the problem is to implement a circular queue. With this type of queue, when the rear subscript reaches the end of the array, it is wrapped around to the start of the array, namely to subscript 0. Of course, this can only happen if the start of the array has an available spot open.
Since the rear subscript was able to wrap around to he beginning when it reached the end, the front subscript must also have the same property.
For example, suppose that you have a queue with the capacity to hold 5 characters. Add the characters 'A', 'B', and 'C'. Remove two entries. Add two more entries 'D' and 'E'. Now add 'F'.
With this type of implementation, we don't have to worry about running out of space. The queue will be able to grow and shrink as needed.
For this implementation, the head pointer will point at the front item. We will also need a tail pointer, which will point at the rear item.