Data Structures and Algorithms: 2018

Queue

Array Implementation of Queue

Queue is First-In-First-Out (FIFO) data structure.

Storage structure

Array / Dynamic Array / Linked-list

Operations

* create a queue (Create memory space for the queue)

* is Empty (There is no element)

* is Full (Queue reach MAX size. You can not insert more element.)

* queue Size (Currently, How much element in it.)

* en-queue / Insert element (Insert an element into a queue)

* de-queue / delete element (Delete an element to a queue)

* delete queue (Delete queue and free memory space)

Example.

1. Vehicle on Road

2. Ticket Counter

Programing (C Language)

struct Queue {

int front, rear;

int maxSize;

int *array;

}

// front = Start point / frist element index

// rear = End point / last element index

// maxSize = Capacity of array / limit of array / How much element you can enter in array.

// array = Hold all element in it. / Point to array which store data

* Always insert element to rear and delete element to the front

* initial position front and rear are -1.

Create Queue

it looks like this somewhere on memory

[Fig 1.]

(C Language)

struct Queue *createQueue(int qSize) {

struct Queue *q = malloc(sizeof(struct Queue)); // Create memory space [Fig 1.1]

if (!q) {

return NULL;

}

q->maxSize = qSize; // Assign the limit or define the max size [Fig 2.]
// let suppose qSize = 5

q->front = q->rear = -1; // Assign front and rear is initialize with -1 [Fig 3.]

q->array = malloc(q->maxSize * sizeof(int)); // Create memory space for queue array [Fig 4.]

if (!q->array) {

return NULL;

}

return q;

}

Understand

malloc(sizeof(struct Queue)); This line allocate some memory for queue. like below figure

[Fig 1.]

struct Queue *q = malloc(sizeof(struct Queue)); This line mean a Pointer named q point this memory address. like below figure

[Fig 1.1]

q->maxSize = qSize; Now, assign qSize in maxSize. qSize is defining the size that this queue can hold maximum range hold in queue array. like below figure (we define here qSize is 5)

[Fig 2.]

q->front = q->rear = -1; assign front and rear with -1 because when we create a queue, the queue is empty and front and rear to nothing have to point. it like blank. So, front and rear are -1.

[Fig 3.]

malloc(q->maxSize * sizeof(int)); Create a memory block which use hold interger value sizeof(int) and how much block you need 'q->maxSize * sizeof(int)' mean 5 * sizeof(int) and integer size in C language is 4 bytes that mean 5 * 4 = 20 bytes in memory. All 5 block total bytes is 20. 4 bytes each

q->array = malloc(q->maxSize * sizeof(int)); and q array assign it pointer.

[Fig 4.] This is the final figure create when createQuere method run

Now check is the queue empty.

int isQueueEmpty(struct Queue *q) {
return (q->front == -1); // Check if no increment in front and it is on his initial value -1 that mean //no value insert in array and nothing here to delete.
}
in C language 1 mean true and 0 mean false. So q->front is -1, now (-1 == -1) its return 1 or true.

Check is the queue full
int isQueueFull(struct Queue *q) {
return ((q->rear + 1) % q->maxSize == q->front );
}

if queue 'rear + 1 modular(mod) queue max size to equal queue front' that mean queue is full.
let's understand with some example

case 1. Insert value
q->array only 1 value and we know that value insert rear only. now we front and rear point on 1 value only
Index value front rear maxSize
0 35 0 0 5 --> front 0 and rear 0
1 - - - 5
2 - - - 5
3 - - - 5
4 - - - 5
(q->rear + 1) % q->maxSize = (0 + 1) % 5 = (1) % 5 = 1
q->front = 0
that mean 1==0 false return 0 or false

case 2. Insert value
Index value   front rear maxSize
0 35 0 0 5 --> front 0
1 66 0 1 5 --> rear 1
2 - - - 5
3 - - - 5
4 - - - 5
(q->rear + 1) % q->maxSize = (1 + 1) % 5 = (2) % 5 = 2
q->front = 0
that mean 2==0 false return 0 or false

case 3. Insert value
Index value   front rear maxSize
0 35 0 0 5 --> front 0
1 66 0 1 5
2 97 0 2 5
3 85 0 3 5 --> rear 3
4 - - - 5
(q->rear + 1) % q->maxSize = (3 + 1) % 5 = (4) % 5 = 4
q->front = 0
that mean 4==0 false return 0 or false

case 4. Insert value
Index value   front rear maxSize
0 35 0 0 5 --> front 0
1 66 0 1 5
2 97 0 2 5
3 85 0 3 5
4 9 0 4 5 --> rear 4
(q->rear + 1) % q->maxSize = (4 + 1) % 5 = (5) % 5 = 0
q->front = 0
that mean 0==0 true return 1 or true

case 5. delete a value to front, Now front move to next point and rear still last position
Index value   front rear maxSize
0 - - - 5
1 66 1 1 5 --> front 1
2 97 1 2 5
3 85 1 3 5
4 9 1 4 5 --> rear 4
(q->rear + 1) % q->maxSize = (4 + 1) % 5 = (5) % 5 = 0
q->front = 1
that mean 0==1 false return 0 or false

case 6. delete one more value
Index value   front rear maxSize
0 - - - 5
1 - - - 5
2 97 2 2 5 --> front 2
3 85 2 3 5
4 9 2 4 5 --> rear 4
(q->rear + 1) % q->maxSize = (4 + 1) % 5 = (5) % 5 = 0
q->front = 2
that mean 0==2 false return 0 or false

case 7. Insert value because we do not enter value next so, rear pointer moves back and check again.
Index value   front rear maxSize
0 3 2 0 5 --> rear 0
1 - - - 5
2 97 2 2 5 --> front 2
3 85 2 3 5
4 9 2 4 5
(q->rear + 1) % q->maxSize = (0 + 1) % 5 = (1) % 5 = 1
q->front = 2
that mean 1==2 false return 0 or false

case 8. Insert a value
Index value   front rear maxSize
0 3 2 0 5
1 12 2 1 5 --> rear 1
2 97 2 2 5 --> front 2
3 85 2 3 5
4 9 2 4 5
(q->rear + 1) % q->maxSize = (1 + 1) % 5 = (2) % 5 = 2
q->front = 2
that mean 2==2 true return 1 or true

Next is queue size or currently how many elements is queue.
int queueSize(struct Queue *q) {
return ((q->maxSize - q->front + q->rear + 1) % q->maxSize);
}

case 1.
Index value front rear maxSize
0 35 0 0 5 --> front 0 and rear 0
1 - - - 5
2 - - - 5
3 - - - 5
4 - - - 5
q->maxSize - q->front + q->rear + 1 = 5 - 0 + 0 + 1 = 6
q->maxSize = 5
(q->maxSize - q->front + q->rear + 1) % q->maxSize
6 % 5
that mean 1 element only

case 2.
Index value   front rear maxSize
0 35 0 0 5 --> front 0
1 66 0 1 5
2 97 0 2 5
3 85 0 3 5 --> rear 3
4 - - - 5
q->maxSize - q->front + q->rear + 1 = 5 - 0 + 3 + 1 = 9
q->maxSize = 5
(q->maxSize - q->front + q->rear + 1) % q->maxSize
9 % 5
that mean 4 elements only

case 3.
Index value   front rear maxSize
0 35 0 0 5 --> front 0
1 66 0 1 5
2 97 0 2 5
3 85 0 3 5
4 9 0 4 5 --> rear 4
q->maxSize - q->front + q->rear + 1 = 5 - 0 + 4 + 1 = 10
q->maxSize = 5
(q->maxSize - q->front + q->rear + 1) % q->maxSize
10 % 5
that mean 5 elements only

case 4. delete a value to front, Now front move to next point and rear still last position
Index value   front rear maxSize
0 - - - 5
1 66 1 1 5 --> front 1
2 97 1 2 5
3 85 1 3 5
4 9 1 4 5 --> rear 4
q->maxSize - q->front + q->rear + 1 = 5 - 1 + 4 + 1 = 9
q->maxSize = 5
(q->maxSize - q->front + q->rear + 1) % q->maxSize
9 % 5
that mean 4 elements only

case 5. Insert value because we do not enter value next so, the rear pointer moves back and check again.
Index value front rear maxSize
0 3 2 0 5 --> rear 0
1 - - - 5
2 97 2 2 5 --> front 2
3 85 2 3 5
4 9 2 4 5
q->maxSize - q->front + q->rear + 1 = 5 - 2 + 0 + 1 = 4
q->maxSize = 5
(q->maxSize - q->front + q->rear + 1) % q->maxSize
4 % 5
that mean 4 elements only

enQueue or insert element in queue
Insert an element in queue we move rear previous to next and if front is -1 make it -1 to 0.
Insert an element move rear front move if it is -1 only
void enQueue(struct Queue *q, int item) {
if (isQueueFull(q)) { // Check if queue is already full inform user or print message
printf("Queue is already full");
}
else {
q->rear = (q->rear + 1) % q->maxSize; // Explanation is below
q->array[q->rear] = item;
if (q->front == -1) {
q->front = q->rear;
}
}
}

case 1.
front -1 and rear -1
Index value front rear maxSize
0 - - - -
1 - - - 5
2 - - - 5
3 - - - 5
4 - - - 5
Insert value 35 first time front and rear both are -1
(q->rear + 1) % q->maxSize = (-1 + 1) % 5 = 0 % 5 = 0
that mean q->rear = 0
and q->front=q->rear so, q->front = 0
Index value front rear maxSize
0 35 0 0 5 --> front 0 and rear 0
1 - - - 5
2 - - - 5
3 - - - 5
4 - - - 5
now, front 0 and rear 0

case 2.
Index value   front rear maxSize
0 35 0 0 5 --> front 0 and --> rear 0
1 - - - 5
2 - - - 5
3 - - - 5
4 - - - 5
Insert value 66 in previously front 0 and rear 0
(q->rear + 1) % q->maxSize = (0 + 1) % 5 = 1 % 5 = 1
q->rear = 1
Index value   front rear maxSize
0 35 0 0 5 --> front 0
1 66 0 1 5 --> rear 1
2 - - - 5
3 - - - 5
4 - - - 5
now, front 0 and rear 1

case 3.
Index value   front rear maxSize
0 - - - 5
1 - - - 5
2 97 2 2 5 --> front 2
3 85 2 3 5
4 9 2 4 5 --> rear 4
Insert value 3 if first 2 element is deleted. In this case front is 2 and rear is 4
(q->rear + 1) % q->maxSize = (4 + 1) % 5 = 5 % 5 = 0
q->rear = 0
Index value   front rear maxSize
0 3 2 0 5 --> rear 0
1 - - - 5
2 97 2 2 5 --> front 2
3 85 2 3 5
4 9 2 4 5
now, rear 0 and front 2

Delete / deQueue an element to queue
In delete / deQueue case we delete element to front only.
int deQueue(struct Queue *q) {
int item = -1; // No item
if (isQueueEmpty(q)) { //check queue is empty or not
printf("There is nothing to delete");
return item;
}
else {
item = q->array[q->front]; // save element in item;
if (q->front == q->rear) { // check if front and rear is equal that mean queue is empty now
q->front = q->rear = -1;
}
else {
q->front = (q->front + 1) % q->maxSize;
// move front to next element[check previous how move rear same here front move]
}
return item;
}
}

Delete queue
delete whole queue and free memory
void deleteQueue(struct Queue *q) {
if (q) {
if (q->array) {
free(q->array); // we need delete array first
}
free(q);
}
}

Tuesday, 10 July 2018

Queue

Array Implementation of Queue