Queue implementation

Queue implementation

1. Queues

2. 07/04/15 CS 201
Queue ADT
•Queues implement the FIFO (first-in first-out)
policy
–An example is the printer/job queue!
enqueue(o)
dequeue()
isEmpty()
getFront() createQueue()

3. 07/04/15 CS 201
Sample Operation
Queue *Q;
enqueue(Q, “a”);
enqueue(Q, “b”);
enqueue(Q, “c”);
d=getFront(Q);
dequeue(Q);
enqueue(Q, “e”);
dequeue(Q);
q
front back
abce
d

4. 07/04/15 CS 201
Queue ADT interface
•The main functions in the Queue ADT are (Q is
the queue)
void enqueue(o, Q) // insert o to back of Q

void dequeue(Q); // remove oldest item

Item getFront(Q); // retrieve oldest item

boolean isEmpty(Q); // checks if Q is empty

boolean isFull(Q); // checks if Q is full
void clear(Q); // make Q empty

}

5. 07/04/15 CS 201
Implementation of Queue
(Linked List)
•Can use LinkedListItr as underlying implementation of Queues
a
1 a
2 a
3 a
4
head
tail
Queue
lst
LinkedList
addTail

6. 07/04/15 CS 201
Code
struct Node {
int element;
Node * next;
};
struct QUEUE {
Node * front;
Node * rear;
};

7. 07/04/15 CS 201
More code

8. More code
07/04/15 CS 201
CELL is a list node

9. 07/04/15 CS 201
Implementation of Queue
(Array)
•use Array with front and back pointers as implementation of
queue
Queue
arr
0 1 7 8 923 4 5 6
ABCDEFG
front
back

10. 07/04/15 CS 201
Circular Array
•To implement queue, it is best to view arrays as circular structure
0 1 7 8 923 4 5 6
ABCDEFG
front
back
front
back
A
B
C
D
EF
G
0
1
7
8
9
2
3
4
5
6
Circular view of arrays.

11. 07/04/15 CS 201
How to Advance
•Both front & back pointers should make advancement until they
reach end of the array. Then, they should re-point to beginning
of the array
front = adv(front);
back = adv(back);
int adv(int p)
{ return ((p+1) % maxsize);
}
Alternatively, use modular arithmetic:
mod operator
int adv(int p)
{ int r = p+1;
if (r<maxsize) return r;
else return 0;
}
upper bound of the array

12. 07/04/15 CS 201
Sample
Queue *Q;
enqueue(Q, “a”);
enqueue(Q, “b”);
enqueue(Q, “c”);
dequeue(Q);
dequeue(Q);
enqueue(Q, “d”);
enqueue(Q, “e”);
dequeue(Q);
a
Q
F=front
B=back
F
B
bcd
F
BBB
FF
BB
e

13. 07/04/15 CS 201
Checking for Full/Empty State
What does (F==B) denote?
F
B
Queue
Empty
State
cde
B
F
f Queue
Full
State
size 0 size 4
cde
BF
Alternative - Leave a Deliberate Gap!
No need for size field.
Full Case : (adv(B)==F)

14. 07/04/15 CS 201
Summary
•The definition of the queue operations
gives the ADT queue first-in, first-out
(FIFO) behavior
•The queue can be implemented by
linked lists or by arrays
•There are many applications
–Printer queues,
–Telecommunication queues,
–Simulations,
–Etc.