Chapter 8 introduces the queue data type. Several example

Download Report

Transcript Chapter 8 introduces the queue data type. Several example

ADT Queue
1.
2.
3.
4.
5.
What is a Queue?
STL Queue
Array Implementation of Queue
Linked List Implementation of Queue
Priority Queue
Queue
 Which
of the following cases use similar
structures?
 Cars
lined up at tollgate
 Cars on a 4-lane highway
 Customers at supermarket check-out
 Books on a book shelf
 Clients airport check-in counter
 Pile of bath towels on linen closet shelf
2
Queue
 Is
a linear data structure with removal of
items at one end (front) and insertion of
items at the opposite end (rear)
 FIFO – first-in-first-out
front
rear
3
Queue Operations

Enqueue(item)


Dequeue()


Return item at front
IsEmpty()


Remove item at front
Front()


Insert item at rear
Is queue empty?
IsFull()

Is queue full?
 Clear()
 Make
queue empty
4
The Queue Operations

A queue is like a line
of people waiting for a
bank teller. The queue
has a front and a rear.
$ $
Rear
Front
The Queue Operations

New people must enter the queue at the
rear. The C++ queue class calls this a
push, although it is usually called an
enqueue operation.
$ $
Front
Rear
The Queue Operations

When an item is taken from the queue,
it always comes from the front. The
C++ queue calls this a pop, although it
is usually called a dequeue operation.
$ $
Front
Rear
The Queue Class
The C++ standard
template library has
a queue template
class.
 The template
parameter is the
type of the items
that can be put in
the queue.

template <class Item>
class queue<Item>
{
public:
queue( );
void push(const Item& entry);
void pop( );
bool empty( ) const;
Item front( ) const;
…
Array Implementation
9
Problem with Array Implementation
front
rear
8
23 12 7
14
 With frequent queueing and dequeing, end of
array can be reached quickly.
 Can we somehow use the empty spaces?
10
“Circular” Array
11
Queue Implementation (2)
front
0
1
2
3
rear
4 5
8

8
9
MAX_SIZE
23 12 7
14
10
6
7
Suppose, currently,
front = 5
 rear = 9


For next values,
front = (front + 1) mod MAX_SIZE = 6
 rear = (rear + 1) mod MAX_SIZE = 0

12
#define MAX_SIZE 5
#define NIL -1
typedef char elemType;
queue.h
(Declarations)
class Queue {
public:
Queue();
void enqueue(elemType item);
void dequeue();
elemType front();
bool isEmpty();
bool isFull();
. . .
13
queue.h
(Declarations)
. . .
private:
elemType data[MAX_SIZE];
int front;
int rear;
int count; // to simply full, empty
};
// Note ; ‘;’
14
Queue() (Constructor)
Queue::Queue(){
front = 0;
rear = -1;
count = 0;
}
15
Enqueue()
void Queue::enqueue(elemType item){
if (!full()){
rear = (rear + 1) % MAX_SIZE;
data[rear] = item;
count++;
}
}
16
Efficiency of enqueue() operation
 If
it takes t seconds to enqueue an element
into a queue of 1000 elements, how long
does it take to enqueue one into a queue of
2000 elements?
 The same time.
 Thus, O(n) = 1.
17
Dequeue()
void Queue::dequeue(){
if (!empty()){
result = data[front];
front = (front + 1) % MAX_SIZE;
count--;
}
}
18
Efficiency of dequeue() operation
 If
it takes t seconds to dequeue an element
from a queue of 1000 elements, how long
does it take to dequeue one from a queue of
2000 elements?
 The same time.
 Thus, O(n) = 1.
19
Your Turn
 Suppose
you want to add another queue
operation:
void clear();
// Postcondition: queue is made empty.
 Write the implemenation code for the
clear() operation.
Front()
elemTypeQueue::front(){
if (!empty()){
return data[front];
else
return NIL;
}
}
21
empty()
bool Queue::empty(){
return count == 0;
}
22
Your Turn
 Write
the implementation code for the operation
full().

bool Queue::isFull();
// Postcondition: True is returned when queue
// is full; false, otherwise.
Array Implementation




Easy to implement
But it has a limited capacity with a fixed array
Or you must use a dynamic array for an
unbounded capacity
Special behavior is needed when the rear reaches
the end of the array.
[0]
[1]
[2]
4
8
6
[3]
[4]
[5]
...
3
size
0
first
2
last
Linked List Implementation
A
queue can also be
implemented with a linked
list with both a head and a
tail pointer.
13
15
10
7
null
front_ptr
rear_ptr
Linked List Implementation
 Which
end do you think is
the front of the queue?
Why?
13
15
10
7
null
front_ptr
rear_ptr
Linked List Implementation
 The
head_ptr points to the
front of the list.
 Because it is harder to
remove items from the tail
of the list.
13
Front
15
10
7
null
front_ptr
rear_ptr
Rear
Your Turn
 Write
the class interface—public and
private sections—for the linked list version
of class queue.
typedef int elemType;
#define NIL -1
queue.h
(Declarations)
class Queue {
public:
Queue();
void enqueue(elemType item);
void dequeue();
elemType front();
bool isEmpty();
. . .
29
Queue Implemented by Linked List
class Queue {
. . .
private:
struct Node {
elemType value;
Node *next;
Node (elemType item, Node *link){
value = item;
next = link;
};
}
Node* front;
Node* rear;
int count;
};
Constructor
Queue
Set head and rear to NULL.
Set count to 0
End queue
Enqueue
void enqueue (elemType item)
Let temp point to new node(item, NULL).
If (empty queue) Then
Let front and rear point to new node
Else
Set rear->next pointer point to temp
End If
Let rear point to temp
Increment count
End enqueue
Enqueue
void enqueue (elemType item)
Node *t = new Nod(item, NULL);
if (isEmpty(){
front = t;
rear = t;
}
else {
rear->next = t;
}
count++;
}
Dequeue
elemType dequeue()
Set result to NIL
If (queue is not empty) Then
Set result to data of front node
Let temp point to front node
Set front to temp’s next
Delete temp
Decrement count
End If
If (front = NULL) Then
Set rear to NULL
Return result
End dequeue
Dequeue
elemType dequeue()
elemType result = NIL;
if (!isEmpty()){
result = front->value;
Node *t = front;
front = temp->next;
delete t;
count--;
}
if (front = NULL)
rear = NULL;
return result;
}
Clear
clear()
Loop (while front != NULL)
Set temp to front
Set front to front’s next
Delete temp
End Loop
Set rear to NULL
Set count to 0
End clear
Print
print()
Set temp to front
Loop(temp != NULL)
Output temp’s data
Set temp to temp’s next
End Loop
End print
Summary
 Like
stacks, queues have many applications.
 Items enter a queue at the rear and leave a
queue at the front.
 Queues can be implemented using an array
or using a linked list.
Priority Queue
Stand-by queue for a flight
 One with the highest priority is removed in
FIFO order—e.g., one who is attending
funeral, wedding.
 Print job queue
 Job with the highest priority is removed in
FIFO order—e.g. one with 3 pages or less
 Emergency Room queue


Most serious case treated first
ADT Priority Queue
 Insert
item into PQ
 Remove item with the highest priority frm PQ
 Change priority of a particular item in PQ
 Remove a particular item from PQ
 Check if PQ is empty
 Clear PQ
Implementation of Priority Queue
Use an array of queues (where index doubles as
priority level).
1
queue
2
queue
3
queue
4
queue
5
queue
Data Structure for Priority Queue
typedef int elemType;
typedef int priorityType;
const priorityType MAX = 5;
class PriorityQueue {
PriorityQueue();
void insert(elemType item,
prioritType pNum);
elemType removeNext();
. . .
public:
. . .
private:
Queue pq[MAX + 1]; // index 0 is unused
};
Constructor
PriorityQueue(){
for (int i = 0; i < MAX + 1; i++){
pqp[i].clear();
}
}
Insert(elemType item,
priorityType pNum)
insert (elemType item, priorityType pNum){
}
class PriorityQueue {
PriorityQueue();
void insert(elemType item,
prioritType pNum);
elemType removeNext();
. . .
public:
. . .
private:
Queue pq[MAX + 1]; // index 0 is unused
};