Queue

A queue is a data structure that stores the data in a linear list which can be accessed in first-in, first-out order, also known as "FIFO". In a queue, the value that is added the first will be the first one to be removed. A data structure queue is similar to a real life queue. For example, in a queue outside a ticket booth, the person standing in the front will be the first one to get the ticket and move out of the queue. Similarly in a data structure queue, the first item placed on the queue is the first item retrieved, the second item put in is the second item retrieved, and so on. This is the only method of storage and retrieval in a queue, you can not randomly access any specific item in a queue.

Queues are similar to stacks in that a queue consists of a sequence of items, and there are restrictions about how items can be added to and removed from the list. However, a queue has two ends, called the front and the back of the queue. Items are always added to the queue at the back and removed from the front. The operations of adding and removing items are usually called enqueue and dequeue. An item that is added to the back of the queue will remain on the queue until all the items in front of it have been removed. This should sound familiar. A queue is like a "line" or "queue" of customers waiting for service. Customers are serviced in the order in which they arrive on the queue.Queues seem very natural because they occur so often in real life, but there are times when stacks are appropriate and even essential. For example, consider what happens when a routine calls a subroutine. The first routine is suspended while the subroutine is executed, and it will continue only when the subroutine returns. Now, suppose that the subroutine calls a second subroutine, and the second subroutine calls a third, and so on. Each subroutine is suspended while the subsequent subroutines are executed. The computer has to keep track of all the subroutines that are suspended. It does this with a stack.

To undestand how a queue works, consider two functions: add( ) and remove( ). The add( ) function places an item in the queue, and remove( ) removes the first item from the queue and returns its value.

Action                                                                         Contents of Queue

add(A)                                                                                     A

add(B)                                                                                   A B

add(C)                                                                                 A B C

remove( ) returns                                                                  A B C

add(D)                                                                                 B C D

remove( ) returns                                                                 B C D

remove( ) returns                                                                  C D