Queue

Previously, we have seen how a stack works. In this blog, I want to give you some insights on another elementary data structure, queue. Queue works on First-In-First-Out (FIFO) principle. Queue can be modeled in real life by a line of customers waiting to pay the bill. The new customers are added at the end of the queue and the customer at the front of the queue comes out after paying the bill. Similar to the push and pop operation of stack, queue has enqueue and dequeue operation. Enqueue adds the element to the end of the queue while dequeue removes the first element from the queue.

Loading
(a) Queue Q has 5 elements at location Q[7...11]. (b) Queue Q after ENQUEUE(Q, 17), ENQUEUE(Q, 3), and ENQUEUE(Q, 5). (c) Queue Q after DEQUEUE(Q). [Source: Introduction to Algorithms]

Here, we implement a queue using an array Q [1…n]. Queue has its attribute, Q.head which points to the head of the queue. Also, Q.tail points to the next location at which the new element will be inserted. When Q.head == Q.tail then, we can infer that the queue is empty. The queue is full if Q.head = Q.tail + 1. Similar to stack, the queue underflows if we try to dequeue an empty queue and the queue overflows if we try to enqueue an element in the full queue.

Pseudocode: ENQUEUE(Q, x)

Q[Q.tail] = x
if Q.tail == Q.length   //queue is made circular when all array space has been used
    Q.tail = 1
 else
    Q.tail = Q.tail + 1

DEQUEUE(Q)

x = Q[Q.head]
if Q.head == Q.length
    Q.head = 1      //when all the elements has been dequeue then Q.head points to first location
else
    Q.head = Q.head + 1
return x

We can see that the both operations above are constant time operation i.e. the running time of both enqueue and dequeue operation is bounded by θ(1). Queue has an important application in breadth first search (BFS) where it is used to store the nodes which have been visited and remove the nodes which have been expanded. The main disadvantage of implementing queue using an array is that the array space should be defined for the maximum number of elements. If this space is not sufficient, then it is difficult to add more while if too much space is allocated then, there will be wastage of space.

To read about stack data structure, visit https://selfstudygeek.blogspot.com/2018/11/stack.html.

Reference:
Introduction to Algorithms by CLRS

Comments

Post a Comment

Popular posts from this blog

Binary Search

Image
Binary search is used to locate an element in an array efficiently than the linear search. To use a binary search, the array must be sorted in non-decreasing order. If T[1…n] is the sorted array, then the binary search returns an index i at which the element(say x) is found. If the element is not in the array then, it returns a possible index where the element might be inserted. Here, we wish to find the index i such that 1 < i < n + 1 and T[i - 1] < x < T[i]. At first, let’s see how do we locate an element in an array using linear or sequential approach. LINEAR-SEARCH (T[1…n], x) for i = 1 to n if T[i] > x return i return n + 1 From the above algorithm, we can see clearly that the algorithm takes the time in θ(n) in the worst case where n is the number of elements. Now, let’s see how binary search algorithm will improve this running time. Basically, a binary search algorithm works like this. First, we compare the element x with the middle element of...
Read more

System Bus

Image
Have you ever wondered how the microprocessor communicates with the devices connected to it? Well, there are a group of wires (communication path) between microprocessor and its peripherals (and memory) to carry bits which are known as system bus. The system bus performs the following steps to communicate with the peripheral: i.         Identify the peripheral or the memory location (with its address). ii.       Transfer data and instructions in the form of bits. iii.     Provide timing and synchronization signals. According to the above functions, system bus can be classified into three types which are described below: Address Bus: It is a set of wires that is used to transmit address from the microprocessor to its peripheral devices (or memory. It is unidirectional. Each peripheral or memory is identified by its address. This is similar to the postal address of the house. For example...
Read more

Differences between hardwired and micro-programmed control unit

S.N. Hardwired Control Unit Micro-programmed Control Unit 1. It is implemented through the use of sequential logic circuit. Its input logic signals are transformed into a set of output logic signals which are control signals. It is implemented through the use of micro-programs. Micro-programs (control information) are organized as a sequence of micro-instructions stored in a special control memory. 2. This design uses a fixed architecture so, it require changes in wiring if the instruction set is modified. It is easy to reconfigure and modify instruction set. 3. It is difficult to build a circuit that satisfies all the operations. It is simple in structure. 4. It has faster mode of operation. It is comparatively slower. 5. It is comparatively expensive. It is cheaper. 6. It is preferred for less number of instruction sets. I...
Read more