Hello! How are you?
As we discussed in the previous post on stacks,
The linear arrays discussed in the previous posts allows one to insert and delete at any position in the list – at the beginning, at the middle or at the end. There are certain frequent situations in computer science when one wants to restrict insertions and deletions so that they can take place only at the beginning or at the end of the list, not at the middle. Two of the data structures that are useful in such situations are queues and stacks.As we completed our analysis of stacks in the previous post, here, in this post we will continue it with our analysis of queues. Hence lets get started!
Introduction
A queue is a linear list of elements in which deletions can take place only at one end, called the FRONT, and insertions can take place only at the other end, called the REAR. The terms "FRONT" and "REAR" are used in describing a linear list only when it is implemented as a queue.
Queues are also called First-In-First-Out (FIFO) lists, since the first element in a queue will be the first element out of the queue. In other words, the order in which elements enter a queue is the order in which they leave. This contrasts with stacks, which are Last-In-First-Out (LIFO) lists.
Queues abound in everyday life. The automobiles waiting to pass through an intersection from a queue, in which the first car in line is the first car through; the people waiting in line at a bank from a queue, where the first person in line is the first person to be waited on; and so on. An important example of a queue in computer science occurs in a time sharing system, in which programmes with the same priority from a queue while waiting to be executed.
Representation of Queues
Queues may be represented in the computer in various ways, usually by means at one-way lists or linear arrays. Each of our queues will be maintained by a linear array QUEUE, two pointer variables: FRONT, containing the location of the front element of the queue; and REAR, containing the location of the rear element of the queue. The condition FRONT=NULL will indicate that the queue is empty.
In the diagram shown, a queue is stored in memory using an array QUEUE with N elements. Whenever an element is deleted from the queue, the value of FRONT is increased by 1, as below
FRONT := FRONT + 1
Similarly, whenever an element is added to the queue, the value of REAR is increased by 1; shown below
REAR := REAR + 1
This means that after N insertions, the rear element of the queue will occupy QUEUE(N) or in other words eventually the queue will occupy the last part of the array. This occurs even though the queue is itself may not contain many elements. While the queue is empty
FRONT := REAR := NULL
With this we are ready to study Insertions and Deletions in a queue. Hence lets start with those two data structure operations in queues.
Insertion and Deletion Algorithms for Queues
To insert an element into our QUEUE, follow the below algorithm:
Insertion Algorithm
This procedure inserts an element ITEM into a queue.
QINSERT(QUEUE, N, FRONT, REAR, ITEM)
1. If REAR>=N then print: "OVERFLOW" & return. [Checking for Overflow Condition]
2. If FRONT=0, make FRONT=1 [Checking for an Empty Queue]
3. REAR=REAR+1 [Make space for the new element to be inserted]
4. QUEUE[REAR]=ITEM [Put the new element into the queue]
5. Return.
2. If FRONT=0, make FRONT=1 [Checking for an Empty Queue]
3. REAR=REAR+1 [Make space for the new element to be inserted]
4. QUEUE[REAR]=ITEM [Put the new element into the queue]
5. Return.
Deletion Algorithm
This procedure deletes an element from a QUEUE and assigns it to the variable ITEM.
1. If FRONT=0, then print: "UNDERFLOW" [Checking for the underflow condition]
2. ITEM = QUEUE [FRONT] [Initialize ITEM, which stores the element to be deleted.]
3. If FRONT = REAR, then FRONT=REAR=0 and Return. [Checking if Queue is empty.]
4. FRONT=FRONT+1 [increment FRONT Pointer.]
5. Return. [Exit.]
Having covered all the fundamental concepts of linear queues, we can move on towards its code implementation.
//Shubham Mehta, Write a program to perform insertions and deletions in a queue.
#include <stdio.h>
void main()
{
int i=0, choice=0, choice1=0, choice2=0, arr[10], top=-1, bottom=-1, element=0;
do
{
printf("%s", "Please enter the correct choice for the operation you want to perform: \n\n");
printf("%s", "Enter 1 to insert into the queue\n");
printf("%s", "Enter 2 to delete from the queue\n");
printf("%s", "Enter 3 to display the current queue status\n");
printf("%s", "Press any other key to exit\n\n");
printf("%s", "Your choice: ");
scanf("%d", &choice);
if(choice==1)
{
printf("\n\nProceeding to insert the element...\n\n");
if(top==10)
{
printf("%s", "OVERFLOW! EXITING!");
goto a;
}
printf("Enter the element to be inserted into the queue: ");
scanf("%d", &element);
++top;
arr[top]=element;
printf("\n\nElement inserted successfully!\n\n");
goto a;
}
else if(choice==2)
{
printf("\n\nProceeding to delete the element...\n\n");
if(bottom==top)
{
printf("%s", "UNDERFLOW! EXITING!");
goto a;
}
printf("%s%d", "The element to be deleted from the queue is: ", arr[bottom]);
printf("\n%s", "Are you sure you want to delete this element? (Press 1 for yes, any other key for no)\nYour Choice: ");
scanf("%d", &choice2);
if(choice2==1)
{
++bottom;
printf("\n\n%s\n\n", "Element deleted successfully!");
}
else
printf("\n\n%s\n\n", "Fine then.");
goto a;
}
else if(choice==3)
{
printf("\n\n%s\n\n", "Proceeding to display the current queue status...");
printf("The current queue status is:\n");
for(i=(bottom+1); i <=top; i++)
printf("%d\t", arr[i]);
printf("\n\n%s\n\n", "Elements displayed successfully!");
}
a:
printf("%s", "Do you want to perform any operations once more? (Press 1 for yes, any other key for no)\nYour choice: ");
scanf("%d", &choice1);
}while(choice1==1);
getch();
}
Now that we have seen both the theoretical aspects of queues as well as its code implementation, we can perhaps spend some time towards learning other type of linear queues. We shall cover Deques and Priority Queues in this lesson, with Circular Queues to be covered in the next lesson.
Deques
A deque is a linear list in which elements can be added or removed from either end but not in the middle. The term deque is a contraction of the term double-ended queue.
Let us see a diagram illustrating its function:
There are two variations of a deque - namely an input restricted deque and an output restricted deque, which are intermediate between a queue and a deque. Specifically an input restricted deque allows insertions only at one end of the list, but allows deletions at both of its ends. Similarly, the output restricted deque allows deletions only at one end of the queue while allowing insertions at both of its ends.
Priority Queue
A priority queue is a collection of elements such that each element has been assigned a priority and such that the order in which elements are deleted and processed comes from the following rules:
- An element of higher priority is processed before any element of a higher priority.
- Two elements with the same priority are processed according to the order they were added in the queue.
A prototype of priority queue is a time-sharing system: programs of a higher priority are processed first while programs of a same priority form a standard queue.
And hence, with this we finish our lesson on linear queue. I hope you'd have had a good experience of it. With this we can move on and start with our next lesson on Circular Queues. Take care till then :)
0 comments:
Post a Comment