Queue - Logical Data Structure

[Suraj-Ajjampur]

First in First Out

Will have 2 ends, tail and head.

Insertion done from tail, deletion done from head.

Queue ADT

Data we need

1. Space for storing elements
2. Head - for deletion
3. Tail - for Insertion

Operation

1. Enqueue(x)
2. dequeue
3. isEmpty()
4. isFull
5. first
6. last

Implemented using

• Arrays
• LinkedList

Arrays

1. Implementation using single pointer

There is a drawback where the time complexity for insert is 0(1) but delete is (n)

2. Implementation using 2 pointers

Time complexity Insert is O(1) and delete is also O(1)

Initially head = tail = -1

Empty Condition if(head == tail)

Full Condition if(tail =size -1)

[Suraj-Ajjampur]

Structure for a queue

struct Queue{
int size;
int head;
int tail;
int*q; //array space - to create array dynamically based on size
};

[Suraj-Ajjampur]

Code from Udemy - DSA 117.+Queue+using+Array+C.pdf 242.QueueUsingArrayC++.txt

[Suraj-Ajjampur]

Drawback of a Linear Queue is that there is waste of array elements as we cannot reuse them

Suppose if the queue is empty we can we can reset the tail and head to initial value (-1) But what if the queue is never empty?

We can use Circular Queue

[Suraj-Ajjampur]

Circular Buffer

Initially head = tail = 0

Empty Condition if (head == tail)

Full Condition if((tail+1) % size = front)

Enqueue

void Enqueue(int x)
{
if (tail+1)%size == head)
printf("Queue is Full");
else{
tail = (tail+1)%size;
//Add new element here
}

Dequeue

int dequeue(){
if(tail == head)
printf("Queue is empty");
else{
head = (head+1)%size;
//Remove element here
}