Queue: Difference between revisions
| Line 9: | Line 9: | ||
A '''queue''' is a [[Data_Structures#Dynamic_Set|dynamic set]] in which the the [[Data Structures#DELETE|DELETE]] operation, which does not have any argument, removes the oldest element in the queue. The queue implements the ''first-in-first-out'', or FIFO, policy. The queue has a '''head''' and a '''tail'''. The INSERT operation for a queue is called '''ENQUEUE''' and places the new element at the tail. The DELETE operation is called '''DEQUEUE''', and has no argument. It simply returns the element at the head of the queue, if any. If we attempt to dequeue an element from an empty queue, it is said that the queue '''underflows'''. If we attempt to enqueue an element on a full queue, it is said that the queue '''overflows'''. | A '''queue''' is a [[Data_Structures#Dynamic_Set|dynamic set]] in which the the [[Data Structures#DELETE|DELETE]] operation, which does not have any argument, removes the oldest element in the queue. The queue implements the ''first-in-first-out'', or FIFO, policy. The queue has a '''head''' and a '''tail'''. The INSERT operation for a queue is called '''ENQUEUE''' and places the new element at the tail. The DELETE operation is called '''DEQUEUE''', and has no argument. It simply returns the element at the head of the queue, if any. If we attempt to dequeue an element from an empty queue, it is said that the queue '''underflows'''. If we attempt to enqueue an element on a full queue, it is said that the queue '''overflows'''. | ||
=Implementation= | |||
The following implementation uses an array, which dictates the queue length. The queue grows circularly and wraps around the edge of the array. | |||
Revision as of 04:21, 11 August 2018
Internal
Overview
Overview
A queue is a dynamic set in which the the DELETE operation, which does not have any argument, removes the oldest element in the queue. The queue implements the first-in-first-out, or FIFO, policy. The queue has a head and a tail. The INSERT operation for a queue is called ENQUEUE and places the new element at the tail. The DELETE operation is called DEQUEUE, and has no argument. It simply returns the element at the head of the queue, if any. If we attempt to dequeue an element from an empty queue, it is said that the queue underflows. If we attempt to enqueue an element on a full queue, it is said that the queue overflows.
Implementation
The following implementation uses an array, which dictates the queue length. The queue grows circularly and wraps around the edge of the array.