Queues

implementation

Queue

data structure

the first one to come in a line would be the first one to be served, which means that the order in which the items are added is the same order in which the items will be removed, similar to the analogy of standing in a line waiting for your pizza.

in computers, an internal queue is implemented to handle the tasks that we ask for, processed in the same order that is instructed to it, we say, task cpu scheduling by os.

in web browsers or applications, event handling on a graphical user interface is internally implemented using queues, where every action performed has the same priority in which they occurred on the interfaces, and even website traffic or handling http responses from the server are handled using queues.

queues implementation

front and rear

we take two pointers, front and rear, where front shows the first person standing in the line, and also the first one to come out of the queue, and once he comes out, the front pointer will go to the next person, and the rear, which shows the last person standing in the line, and when more people join the line at the last, the rear pointer will always increment and reach out to the last person.

using arrays,

int queue[MaxSize]
int front = -1
int rear = -1

insertion

when people join back at the line, only the rear pointer is incremented, however, there is a limited space where people could stand, that is our overflow condition for the max size, and there is an edge case, when the first person stands in the queue, it itself represents both the front and the rear, so both has to be handled.

enqueue(e)

overflow condition if( rear == MaxSzie - 1 )

return overflow error

if first element if( front == -1 )

front = 0

push item rear++

arr[rear] = e

deletion

when people move out of the queue, it is always the front that moves next towards the rear, and in case the front has reached the rear, it cannot move further next to the rear, because the rear holds the last person standing, and in such a case, when the last person standing has moved out, the front moves one step ahead of the rear, and the queue gets empty.

dequeue()

underflow condition if( front == -1 )

return underflow error

get item item = arr[front]

front++

last element if( front > rear )

front = -1, rear = -1

other operations

we can create functions to check whether the queue is empty or full, and peek at who is standing at the front and the rear pointers.

isempty()

if empty if( front == - 1 )

return true

if not empty else

return false

isfull()

if full if( rear == MaxSize - 1 )

return true

if not full else

return false

frontpeek()

if not empty if ( !isempty() )

return arr[front]

rearpeek()

if not emptyif( !isempty() )
return arr[rear]








queues implementation in c using arrays,
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
intqueue[MAX];
int front = -1;
int rear = -1;
voidenqueue(int e){
if( rear == MAX - 1){
printf("overflow");
return;
}
if( front == -1 ){
front = 0;
}
rear++;
queue[rear] = e;
}
intdequeue(){
if( front == -1 ){
printf("underflow");
return0;
} else{
int e = queue[front++];
if( front > rear ){
front = -1;
rear = -1;
}
return e;
}
}
boolisempty(){
if( front == -1 ){
returntrue;
} else {
returnfalse;
}
}
intfrontpeek(){
if( !isempty() ){
returnqueue[front];
} else {
return-1;
}
}
intrearpeek(){
if( !isempty() ){
returnqueue[rear];
} else {
return-1;
}
}
intmain(){
enqueue(10);
enqueue(15);
enqueue(20);
printf(" %d ", frontpeek());
printf(" %d ", rearpeek());
printf(" %d ", dequeue());
printf(" %d ", dequeue());
printf(" %d ", dequeue());
printf(" %d ", dequeue());
return0;
}




queues implementation in c using linkedlist,
#include <stdio.h>
#include <stdlib.h>
typedefstructNode{
int data;
structNode* next;
} Node;
typedefstructQueue{
Node *front, *rear;
} Queue;
voidinitialize(Queue *q){
q->front = NULL;
q->rear = NULL;
}
voidenqueue(Queue *q, int e){
Node* new = (Node*)malloc(sizeof(Node));
new->next = NULL;
new->data = e;
if( q->front == NULL){
q->front = new;
q->rear = new;
} else {
q->rear->next = new;
q->rear = new;
}
}
intdequeue(Queue *q){
if( q->front == NULL ){
printf("underflow");
return-1;
} else {
Node *temp = q->front;
int e = q->front->data;
q->front = q->front->next;
if( q->front == NULL ){
q->rear = NULL;
}
free(temp);
return e;
}
}
intmain(){
Queue q;
initialize(&q);
enqueue(&q, 10);
enqueue(&q, 20);
printf(" %d ", dequeue(&q));
printf(" %d ", dequeue(&q));
printf(" %d ", dequeue(&q));
return0;
}







Circular Queues

• it implements the first-in-first-out principle,

means that the first one in the line is the first to be out

• a normal queue would leave empty spaces in an array, but this is efficient for memory in array implementation
• it is used in data streams & memory management
• all operations are in O(1), max size is required

two pointers front and rear,
front is always behind and rear is always ahead
two main operations of circular queues, enqueue & dequeue
enqueue(item)
check whether queue is full if ( ( rear + 1 ) % maxsize == front )
return overflow
if queue is empty if ( front == -1 )
front == 0
update rear rear = ( rear + 1 ) % maxrize
insert the element arr[rear] = item


dequeue()
check whether queue is empty if( front == -1 )
return underflow
get item item = arr[front]
if last element if( front == rear )
front == -1
rear == -1
else
update front front = ( front + 1 ) % maxsize





circular queues implementation usng arrays,
#include <stdio.h>
#define MaxSize 3
int circular_queue[MaxSize];
int front = -1;
int rear = -1;
voidenqueue(int e){
if( ( rear + 1 ) % MaxSize == front ){
printf("overflow");
return;
} elseif( front == -1 ){
front = 0;
rear = 0;
circular_queue[rear] = e;
} else{
rear = ( rear + 1 ) % MaxSize;
circular_queue[rear] = e;
}
}
intdequeue(){
if( front == -1 ){
printf("underflow");
return-1;
} elseif( front == rear ){
int e = circular_queue[front];
front = -1;
rear = -1;
return e;
} else{
int e = circular_queue[front];
front = ( front + 1 ) % MaxSize;
return e;
}
}
intmain(){
enqueue(5);
enqueue(10);
enqueue(15);
printf(" %d ", dequeue() );
printf(" %d ", dequeue() );
enqueue(20);
enqueue(40);
printf(" %d ", dequeue() );
printf(" %d ", dequeue() );
printf(" %d ", dequeue() );
printf(" %d ", dequeue() );
return0;
}







deque: double ended queues

• can insert and delete in both ends.
• implements both lifo and fifo.
• used for more flexibility.

front_enqueue & rear_dequeue

typically, people stand from the rear end and move out from the front end, which means a normal queue would have insertion at rear end and deletion at front end, but here we need the flexibility if someone takes a vip pass, and stands straight at the front of the line, then that vip pass is treated as insertion at front, and if someone gets tired standing up in a line and moves out from the last end, those tired people are treated as deletion at rear.

delete operations

whenever delete operation takes place, people moving out from the front, then front is always updated to reach forward towards rear, then there is an edge case where if front reaches n - 1 end then it goes back to index 0, the opposite is true for delete operation in rear end, people moving out from the last, where rear moves backwards towards front, with an edge case if rear reaches to index 0, it has to go towards n - 1 end, where both edge cases of front and rear satisfy the circular queue.

insert operations
whenever a person wants to stand in a line, they typically stand behind each other, normally insertion from the rear end, and if rear reaches n - 1 from then it goes ot 0, and and if people with those vip passes are standing at the front always, they will keep standing till front reaches index 0, then it goes back to n - 1, where both edge cases satisfy circular queue.
pointer changes
front_dequeue => left to right pop => if n - 1 then 0 index
rear_dequeue => right to left pop => 0 index then n - 1
front_enqueue => right to left push => 0 index then n - 1
rear_endqueue => left to right push => if n - 1 then 0 index
double ended queues implementation in c using arrays,
#include <stdio.h>
#define MAX 100
intdeque[MAX];
int front = -1;
int rear = -1;
voidenqueue_front(int e){
if( front == 0 && rear == MAX - 1 || ( front - 1 ) == rear){
printf("overflow");
} elseif (front == -1) {
front = 0;
rear = 0;
} elseif( front == 0 ){
front = MAX - 1;
} else {
front--;
}
deque[front] = e;
}
intdeque_front(){
if( front == -1 ){
printf("underflow");
return-1;
}
int e = deque[front];
if(front == rear) {
front = -1;
rear = -1;
} elseif (front == MAX - 1) {
front = 0;
} else {
front++;
}
return e;
}
intdeque_rear(){
if( rear == -1 ){
printf("underflow");
return-1;
}
int e = deque[rear];
if(front == rear) {
front = -1;
rear = -1;
} elseif (rear == 0) {
rear = MAX - 1;
} else {
rear--;
}
return e;
}
voidenqueue_rear(int e){
if( front == 0 && rear == MAX - 1 || ( rear + 1) == front ){
printf("overflow");
} elseif (rear == -1) {
front = 0;
rear = 0;
} elseif (rear == MAX - 1) {
rear = 0;
} else {
rear++;
}
deque[rear] = e;
}
intmain(){
enqueue_front(5);
enqueue_front(10);
enqueue_front(15);
enqueue_rear(20);
enqueue_rear(25);
enqueue_rear(30);
printf("Deque rear: %d\n", deque_rear());
printf("Deque rear: %d\n", deque_rear());
printf("Deque rear: %d\n", deque_rear());
printf("Deque rear: %d\n", deque_rear());
printf("Deque front: %d\n", deque_front());
printf("Deque front: %d\n", deque_front());
return0;
}

priority queues will be well understood after studying heaps which uses a self-balancing binary tree known as avl tree