Queue Operations

Download Report

Transcript Queue Operations 

Queues
Chapter 5
Ceng-112 Data Structures I
2007
1
Linear Lists
Operations are;
1. Insertion
2. Deletion
3. Retrieval
4. Traversal (exception for restristed lists).
Ceng-112 Data Structures I
2007
Figure 3-2
2
Queue
A queue is a linear list. Data can be inserted at one end (rear) and
deleted from the other end (front).
First In First Out - FIFO
Figure 5-1
Ceng-112 Data Structures I
2007
3
Queue Operations
There are four basic queue operations.
Data can be inserted at the rear and processed from the front.
1.
Enqueue ; inserts an element at the rear of the queue.
2.
Dequeue ; deletes an element at the front of the queue.
3.
Queue Front; examines the element at the front of the queue.
4.
Queue Rear; examines the element at the rear of the queue.
Ceng-112 Data Structures I
2007
4
Queue Operations
Figure 5-2
Ceng-112 Data Structures I
2007
5
Queue Operations
Figure 5-3
Ceng-112 Data Structures I
2007
6
Queue Operations
If there are no data in the queue, then the queue is in an underflow
state.
Figure 5-4
Ceng-112 Data Structures I
2007
7
Queue Operations
If there are no data in the queue, then the queue is in an underflow
state.
Figure 5-5
Ceng-112 Data Structures I
2007
8
Figure 5-6
Ceng-112 Data Structures I
2007
9
Queue Linked List Design
Figure 5-7
Ceng-112 Data Structures I
2007
10
Queue Data Structure
Figure 5-8
Ceng-112 Data Structures I
2007
11
Figure 5-9, Part I
Ceng-112 Data Structures I
2007
12
Queue Algorithms - Create Queue
algorithm createQueue
Allocates memory for a queue head node from dynamic memory and returns
its address to the caller.
Pre Nothing
Post head has been allocated and initialized
Return head’s address if successful, null if memory owerflow.
1.
if (memory available)
1.
2.
3.
4.
5.
2.
allocate (newPtr)
newPtrfront = null pointer
newPtrrear = null pointer
newPtrcount = 0
return newPtr
else
1.
return null pointer
end createQueue
Ceng-112 Data Structures I
2007
13
Queue Algorithms - Enqueue
Figure 5-10
Ceng-112 Data Structures I
2007
14
Queue Algorithms - Enqueue
algorithm enqueue(val queue <head pointer>, val item <dataType>)
This algorithm inserts data into queue.
Pre queue has been create
Post item data have been inserted
Return boolean, true if successful, false if overflow.
1.
if (queue full)
1.
2.
3.
4.
5.
return false
allocate (newPtr)
newPtrdata = item
newPtrnext = null pointer
if (queuecount zero) //inserting into null queue
1.
6.
queuefront = newPtr
else // insert data and adjust meta data
1.
queuerearnext = newPtr
7.
queuerear = newPtr
8.
queuecount = queuecount +1
9.
return true
end enqueue
Ceng-112 Data Structures I
2007
15
Figure 5-9, Part II
Ceng-112 Data Structures I
2007
16
Figure 5-11
Ceng-112 Data Structures I
2007
17
Queue Algorithms - Dequeue
algorithm dequeue(val queue <head pointer>, ref item <dataType>)
This algorithm deletes a node from a queue.
Pre queue has been create
Post data at front of the queue returned to user through item and front element
deleted and recycled.
Return boolean, true if successful, false if overflow.
1.
if (queuecount is 0)
1.
2.
3.
4.
return false
item = queuefrontdata
deleteLoc = queuefront
if (queuecount is 1) // deleting only item in queue
1.
queuerear = null pointer
5.
queuefront = queuefrontnext
6.
queuecount = queuecount – 1
7.
recycle (deleteLoc)
8.
return true
end dequeue
Ceng-112 Data Structures I
2007
18
Queuing Theory
• A single server queue can provide service to only one customer at a time.
• Multiserver queues, can provide service to many customers at a time.
• A customer is any person or thing needing service.
• The service is any activity needed to accomplish the required result.
• The rate at which customers arrive in the queue for service is known as the
arrival rate.
• Service time is the avarage time required to complete the processing of a
customer request.
Figure 5-12
Ceng-112 Data Structures I
2007
19
Queuing Theory
• Queuing theory attempts to predict some patterns,
such as;
– Queuing time, which is defined the avarage length of time
customers wait in the queue,
• Avarage and maximum size of queue,
– Response time is an important statistical tool for online
computer systems
• There are two factors that affect the performance of
queues;
– Arrival rate
– Service time
Ceng-112 Data Structures I
2007
20
Queue Data Structures
Figure 5-13
Ceng-112 Data Structures I
2007
21
Queues Array Implementation
Figure 5-15
Ceng-112 Data Structures I
2007
22
Queues Array Implementation
Figure 5-16
Ceng-112 Data Structures I
2007
23
• Store the address of the queue array.
• Store the max. number of elements in array.
Figure 5-17
Ceng-112 Data Structures I
2007
24
Exercise
Imagine the contents of queue Q1 and Q2 are as shown. What would be the
content of Q3 after the following code is executed? The queue contents are
shown front (left) to rear (right).
Q1: 42 30 41 31 19 20 25 14 10 11 12 15
Q2: 1
4
5
4 10 13
1 Q3 = createQueue
2 count = 0
3 loop (not empty Q1 and not empty Q2)
1 count = count + 1
2 dequeue (Q1, x)
3 dequeue (Q2, y)
4 if (y equal count)
1 enqueue (Q3, x)
Ceng-112 Data Structures I
2007
25
Exercise
Imagine the contents of queue Q1 and Q2 are as shown. What would be the content of
Q3 after the following code is executed? The queue contents are shown front (left) to
rear (right).
Q1: 42 30 41 31 19 20 25 14 10 11 12 15
Q2: 1
4
5
4 10 13
1 Q3 = createQueue
2 count = 0
3 loop (not empty Q1 and not empty Q2)
1 count = count + 1
2 dequeue (Q1, x)
3 dequeue (Q2, y)
4 if (y equal count)
1 enqueue (Q3, x)
Step
count
Q1
Q2
Q3
1
0,1
42,30,..
1,4,5,4,..
2
2
30,41,..
3
3
4
y
42
1
4,5,4,..
30
4
42,31,19,..
5,4,10,13
42
5
4
31,19,20,..
4,10,13
31
4
5
5
19,20,25,..
10,13
19
10
6
6
20,25,14,..
13
20
13
25,14,10,..
NULL
7
42
x
42,31
Q3: 42, 31
Ceng-112 Data Structures I
2007
26