You should be reasonably familiar with the concept of a queue in the real world. The way it works in computing is exactly the same! A queue is a linear data structure, with a front and a back. Items enter the queue by joining the back of the queue, and items are removed one at a time from the front of the queue. The operations of adding an item to the back and removing an item from the front are known as enqueuing and dequeuing respectively.
An important thing to emaphasise is that the Queue is an abstract data type (ADT). This means that users of the Queue know what operations can be performed on the Queue (e.g., enqueue, dequeue), but they do not need to know how the Queue is implemented. The operations that can be performed on an ADT are collectively called the interface to the ADT, and are declared in a header (*.h) file, while the implementation details go in the corresponding *.c file. The implementation (the *.c file) is not directly #included in the program, which means that the user of the ADT does not have access to the internal representation of the ADT (i.e., what fields does it contain and what concrete data structures does it use) and does not know how the functions declared in the header file are implemented.
Since the Queue is an ADT, it could be implemented in several different ways, for example, using a linked list or using an array. The choice of implementation determines the time and space complexities of the operations. Here are the different queue implementations we will explore:
In this implementation, the items in the queue are stored in a linked list. To enqueue an item, the item is added to the end of the list, and to dequeue an item, the item is removed from the beginning of the list. To enable both operations to be efficient, the queue contains pointers to the first and last nodes in the list. Here are some diagrams demonstrating the enqueue and dequeue operations on the list queue:
After enqueuing 5:
After dequeuing 3:
In this implementation, the items in the queue are stored in an array. To enqueue an item, the item is simply placed in the next available slot in the array, and to dequeue an item, the item at index 0 is removed and the rest of the items are shifted down. Since the implementation uses an array, the array may become full and if more items need to be inserted, the array will need to be expanded. Also, since the array will usually not be full, we will need to keep track of both the number of items (i.e., the size of the queue) and the size of the array (i.e., the capacity). Here are some diagrams demonstrating the enqueue and dequeue operations on the array queue:
After enqueuing 5:
After dequeuing 3: