Scribd
Upload
15 views9 pages

Queue Data Structure Overview

The document provides an overview of queues, which are data structures that operate on a first-in first-out (FIFO) basis. It details the operations associated with queues, including creation, checking if empty, adding (enQueue), and removing (deQueue) items. Additionally, it includes a pointer implementation of a queue using a node structure in C++.

Uploaded by

kenetfikru
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
15 views9 pages

Queue Data Structure Overview

The document provides an overview of queues, which are data structures that operate on a first-in first-out (FIFO) basis. It details the operations associated with queues, including creation, checking if empty, adding (enQueue), and removing (deQueue) items. Additionally, it includes a pointer implementation of a queue using a node structure in C++.

Uploaded by

kenetfikru
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

: Data Structures & Algorithm Analysis

• Chapter 6: Queue

1
Queue

Queue is a list with restrictions imposed upon


the way in which entries may be added and
removed. The restriction is that entries are
always added at one end of the queue (tail,
rear) while removal is made at the other end
(head, front). Queue is a first-in first-out
(FIFO) structure.

2
Queue…

3
Queue Operation

• create(queue): Create the queue

• isEmpty(queue): Check if queue is empty

• enQueue(queue, item): Add an item

• deQueue(queue, item): Remove and item

4
Pointer implementation of Queue

Node Construction/Declaration:
struct node {
<appropriate_type> data;
node * next;
};
struct queue{
node *front;
node *rear;
};
Queue Construction:
queue q;
5
Create Queue

void create (queue & q) {


[Link] = NULL;
[Link] = NULL;
}

6
Is Queue Empty

int isEmpty (queue q) {


if ([Link] == NULL) return 1;
else return 0;
// or if ([Link] == NULL) …
}

7
Add Item on to the Queue

void enQueue (queue & q, <appr_type> item) {


node * p;
p = new nothrow node;
if (p != NULL) {
p->data = item;
p->next = NULL;
if (isEmpty(q)) [Link] = [Link] = p;
else {
[Link]->next = p;
[Link] = p;
}
}
}
8
Remove Item from the Queue

void deQueue (queue & q, <appr_type> & item) {


node * p;
if (!isEmpty(q)) {
p = [Link];
item = [Link]->data;
if ([Link] == [Link])
[Link] = [Link] = NULL;
else [Link] = [Link]->next;
delete(p);
}
}
9

You might also like