3.8.3 Queue

Knowledge Base > Algorithm > Data Structure

Overview

A Queue is a popular FIFO (First-In-First-Out) data structure, where its first element will be the first one out. In other words, whenever an element is added, all elements that were added before have to be removed before the new element can be invoked. There are also non-FIFO queue data structure, such as priority queue. There are two basic operations associated with a queue: enqueue and dequeue, and will be explained below. Theoretically, q queue does not need to specify the capacity. Regardless of how many elements are already contained, a new element can always be added. A queue can also be empty, at which point removing an element will be impossible until a new element has been added again. In practice, we usually define a FIXED length on the capacity of the queue, while we determine the size of the queue dynamically by the start and tail positions of the queue. Or, the pointer to the start and end nodes of the queue in Linked-List Implementation.

Basic Operation

• void enqueue(<E>):
  adding a new item to the rear of the queue.
• <E> dequeue(void):
  removing the front item from the queue and returning it to the calling entity.

Source Code

A practical implementation of a queue does have some capacity limit, that depends on the concrete situation it is used in. Usually, a queue can be implemented by array or linked-list.

• Array Implemented Queue (C)
  
  
• Linked List Implemented Queue (C)

Related Topics

• Priority Queue