Linear Queue
Implementation of operations on a linear queue:
Creating an Empty Queue
Before we can use a queue, it must be created. The purpose of initializing the queue is served by assigning -1 (as a sentinel value) to the front and rear variables. Note that the valid range of an index for the array is 0 to CAPACITY-1.
.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }
void createqueue(queue *q)
{
q->front=q->rear=-1;
}
Testing the Queue for Underflow
bool isempty(queue q)
{
if(q.front==-1)
return true;
else
return false;
}
Testing the Queue for Overflow
bool isfull(queue q)
{
if ((q.front==0) && (q.rear==CAPACITY-1))
return true;
else
return false;
}
Note: bool can be defined as typedef enum {false, true} bool;
Performing the enqueue Operation on a Linear Queue
There are two scenarios that we should consider, assuming that the queue is not full.
- If the linear queue is empty, then the value of the front and the rear variable will be -1 (the sentinel value), then both front and rear are set to 0.
-
If the linear queue is not empty, then there are two further possibilities:
- If the value of the rear variable is less than CAPACITY-1, then the rear variable is incremented.
- If the value of the rear variable is equal to CAPACITY-1, then the elements of the linear queue are moved forward, and the front and rear variables are adjusted accordingly.
C Code
void enqueue(queue *q, int value)
{
int i;
if(isempty(*q))
q->front=q->rear=0;
else if (q->rear==CAPACITY-1)
{
for(i=q->front;i<=q->rear;i++)
q->elements[i-q->front]=q->elements[i];
q->rear=q->rear-q->front+1;
q->front=0;
}
else
{
q->rear++;
}
&nbs; q->elements[q->rear]=value;
}
Performing the dequeue Operation on a Linear Queue
There are two possibilities:
- If there is only one element in the linear queue then after dequeueing it will become empty. This state of the linear queue is reflected by setting the front and rear variables to -1, the sentinel value.
- Otherwise, the value of the front variable is incremented.
C Code
int dequeue(queue *q)
{
int temp;
temp=q->elements[q->front];
if(q->front==q->rear)
q->front=q->rear=-1;
else
q->front++;
return temp;
}
Complete Program
/*
* Linear Queue
* http://www.tech-faq.com
*/
#include <stdio.h>
#define CAPACITY 10
typedef struct
{
int front;
int rear;
int elements[CAPACITY];
} queue;
typedef enum {false, true} bool;
void createqueue(queue *);
bool isempty(queue );
bool isfull(queue );
void enqueue(queue *, int );
int dequeue(queue *);
void display(queue );
int main()
{
queue q;
int elem, count;
createqueue(&q);
printf("Enter integers to enqueue or -99 to stop: ");
scanf("%d", &elem);
for (count=0; elem!=-99 && count<CAPACITY; count++)
{
enqueue(&q, elem);
puts("Now, the queue is (front..to..rear): ");
display(q);
printf("nEnter another element: ");
scanf("%d", &elem);
}
puts("nDequeueing elements...");
while (!isempty(q))
{
dequeue(&q);
printf("An element has been dequeued...the queue is now: ");
display(q);
}
return 0;
}
void createqueue(queue *q)
{
q->front=q->rear=-1;
}
bool isempty(queue q)
{
if(q.front==-1)
return true;
else
return false;
}
bool isfull(queue q)
{
if ((q.front==0) && (q.rear==CAPACITY-1))
return true;
else
return false;
}
void enqueue(queue *q, int value)
{
int i;
if(isempty(*q))
q->front=q->rear=0;
else if (q->rear==CAPACITY-1)
{
for(i=q->front;i<=q->rear;i++)
q->elements[i-q->front]=q->elements[i];
q->rear=q->rear-q->front+1;
q->front=0;
}
else
{
q->rear++;
}
q->elements[q->rear]=value;
}
int dequeue(queue *q)
{
int temp;
temp=q->elements[q->front];
if(q->front==q->rear)
q->front=q->rear=-1;
else
q->front++;
return temp;
}
void display(queue q)
{
int i;
if (!isempty(q))
{
for (i=q.front; i<=q.rear; i++)
printf(" %d -->", q.elements[i]);
printf("bbb n"); /*erase the last arrow*/
}
else
puts("Empty");
}
Output
Enter integers to enqueue or -99 to stop: 7 Now, the queue is (front..to..rear): 7
Enter another element: 4 Now, the queue is (front..to..rear): 7 –> 4
Enter another element: 8 Now, the queue is (front..to..rear): 7 –> 4 –> 8
Enter another element: 2 Now, the queue is (front..to..rear): 7 –> 4 –> 8 –> 2
Enter another element: -99
Dequeueing elements… An element has been dequeued…the queue is now: 4 –> 8 –> 2 An element has been dequeued…the queue is now: 8 –> 2 An element has been dequeued…the queue is now: 2 An element has been dequeued…the queue is now: Empty
|
|
- Circular Queue
The difficulty of managing front and rear in an array-based non-circular queue can be overcome if we treat the queue position with index 0 as if it comes after the last position (in our case, index 9), i.e., we treat the queue as circular. Note that we use the same array declaration of the queue. [...]...
- Queues
A queue is a line of persons waiting for their turn at some service counter. The service counter can be a ticketing window of a cinema hall, a railway station, etc. Depending on the type of service provided by the service counter and number of persons interested in service, there could be queues of varying [...]...
- Traversing and Searching a Linear Linked List
Traversing a list A linear list can be traversed in two ways In order traversal Reverse order traversal In order Traversal To traverse the linear linked list, we walk the list using the pointers, and process each element until we reach the last element. .cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; [...]...
- Linear Search
This method traverses a list sequentially to locate the search key. The algorithm that one chooses generally depends on the organization of the array elements. If the elements are in random order, then one should choose the linear search technique. Algorithm linearsearch (a,n,item,loc) Here "a" is an array of the size n. This algorithm finds [...]...
- Deleting an Element from a Linear Linked List
To delete an element from the list, first the pointers are set properly and then the memory occupied by the node to be deleted is deallocated (freed). This tutorial covers the deletion of a node from the following three positions: At the beginning of the list At the end of the list After a given [...]...