Data Structure
Dr. Ahmed Hesham Mostafa
Lecture 3 –Queue based Arrays and
Linked
TextBooks
• s k chang, “data structures and algorithms”
• Kruse and Leung, “Data Structures & Program Design in C”
Online Martials
• CS214: Data Structures by Prof. Dr Waleed A. Yousef
• https://www.youtube.com/playlist?list=PLoK2Lr1miEm-
5zCzKE8siQezj9rvQlnca
• Data Structures Learning Course by Dr Mohammed El-Said
• https://www.youtube.com/playlist?list=PLfay0LLBd0wiNeOR_SGoYfC
3w-NxFwd0D
• Lectures Source code (updated frequently)
• https://github.com/ahmedheshamostafa/DataStructure
Motivation: Why Queue? First In First Out (FIFO)
• In a queue,
– new values are always added at the rear of the list
– values are removed from the opposite end of the list, the
front
Input D C B A Output
• Examples of queues
– checkout at supermarket
– Toll Station
• Car comes, pays, leaves
– Check-out in Big super market
• Customer comes, checks out and leaves
– More examples: Printer, Office Hours, …
© Waleed A. Yousef 2008 4
E.g., Printing Queue
• A.doc, B.doc, C.doc arrive to printer.
Now printing A.doc
C B A
A.doc is finished. Now printing B.doc
C B
D.doc comes Now still printing B.doc
D C B
B.doc is finished. Now printing C.doc
D C
C.doc is finished. Now printing D.doc
D
© Waleed A. Yousef 2008 5
Array Implementation1: Physical Model
(Front is fixed as in physical lines)
• Shifting all items to front in the array when
dequeue operation. ( Too Costly… )
• Why this was not a problem in the array
implementation of Stacks?
n-1 3 2 1 0 A leaves n-1 3 2 1 0
…… C B A …… C B
rear=2 front=0 rear=1 front=0
© Waleed A. Yousef 2008 6
Array Implementation2: Linear Model
(Two indices, front and rear)
n-1 3 2 1 0
D C B A
Max_Size rear front
After A leaves,
n-1 3 2 1 0
D C B
Max_Size rear front
© Waleed A. Yousef 2008 7
The problem is that there will be many empty places in the
front of array and rear is always incremented.
n-1 3 2 1 0
D C B A
Max_Size rear front
After A,B,C,D leave
n-1 3 2 1 0
K J I H G F E
Max_Size
rear front
© Waleed A. Yousef 2008 8
Array Implementation 3: Circular Implementation
0 Max-1
1
Occupied
Circular Queue
0 Max-1
2 Occupied
Unwinding
Front Rear
Occupied
0 1 … …
Max-1
Linear
© Waleed A. Yousef 2008
Implementation 9
Checking the Boundary conditions
Rear and Front advance in this direction
0 MAX-1
Queue with two elements
F R
Queue with one element
FR
With Empty condition:
Next to Rear = Front. R F
Queue with one element
FR
F R
Full Condition:
Next to Rear = Front
Therefore we waste one location R F 10
© Waleed A. Yousef 2008
Better solution: Use indicator variable to
distinguish between Empty and Full conditions.
Rear and Front advance in this direction
Empty queue:
Next to Rear = Front.
Size=0 R F
R F
Full queue:
Next to Rear = Front.
Size=MAX R F
© Waleed A. Yousef 2008 11
Again: Definitions, where every thing should start from!
Definition: type is a set of values and a set of operations on
those values.
Example: We can define a datatype boolean that takes the set
of values {0, 1} together with the operations AND, OR, and NOT.
Example: int, in C, is the set consisting all of the integers
between INT_MIN (-(215 − 1)) and INT_MAX (215 – 1),
which are defined in the header file limits.h
Definition: A Sequence of length 0 is empty. A sequence of
length n 1 of elements from a set T is an ordered pair (Sn-
1,t) where Sn-1 is a sequence of length n-1 of elements from T,
and t is an element of T.
© Waleed A. Yousef 2008 12
Definition: A queue of elements of type T is a finite sequence of
elements of T together with the following operations:
1. Create the queue, leaving it empty.
2. Determine whether the queue is empty or not
3. Determine whether the queue is full or not
4. Find the size of the queue
5. Append a new entry onto the top of the queue, provided the
queue is not full.
6. Retrieve the front entry in the queue, provided the queue is not
empty.
7. Serve (and remove) the front entry from the queue, provided
the queue is not empty.
8. Traverse the queue, visiting each entry
9. Clear the queue to make it empty
© Waleed A. Yousef 2008 13
User Level
typedef struct queue{ (interface)
int front;
int rear; void main(){
int size;
QueueEntry entry[MAXQUEUE]; Queue q;
}Queue;
front
rear
size
entr
© Waleed A. Yousef 2008
y 14
void CreateQueue(Queue *pq){ User Level
pq->front= 0; (interface)
pq->rear = -1;
void main(){
pq->size = 0;
}
//Initializing front =5 and rear =4 will Queue q;
work if MAXQUEUE >=6. But, since MAXQUEUE
can be 1 we intialize as above. CreateQueue(&q);
MAXQUEUE-1
}
front
&q
rear pq
size
0
entr
© Waleed A. Yousef 2008
y 15
void Append(QueueEntry e, Queue* pq){
pq->rear = (pq->rear + 1) % MAXQUEUE;
pq->entry[pq->rear] = e;
pq->size++;
} if (pq->rear == MAXQUEUE-1)
pq->rear=0;
else
pq->rear++;
MAXQUEUE-1
front
&q
pq rear
size
0
© Waleed A. Yousef 2008
entr 16
void Serve(QueueEntry *pe, Queue* pq){
*pe = pq->entry[pq->front];
pq->front = (pq->front + 1) % MAXQUEUE;
pq->size--;
}
MAXQUEUE-1
front
&q
pq rear
&e size
pe
0
© Waleed A. Yousef 2008
entr 17
int QueueEmpty(Queue* pq){
return !pq->size;
}
int QueueFull(Queue* pq){
return (pq->size == MAXQUEUE);
}
MAXQUEUE-1
front
rear
size
0
© Waleed A. Yousef 2008
entr 18
int QueueSize(Queue* pq){
return pq->size;
}
void ClearQueue(Queue* pq){
pq->front = 0;
pq->rear = -1;
pq->size = 0;
}//same as CreateQueue. No nodes to free.
MAXQUEUE-1
front
rear
size
0
© Waleed A. Yousef 2008
entr 19
void TraverseQueue(Queue* pq, void (*pf)(QueueEntry)){
int pos, s;
for(pos=pq->front, s=0; s<pq->size; s++){
(*pf)(pq->entry[pos]);
pos=(pos+1)%MAXQUEUE;
}
}
MAXQUEUE-1
front
rear
size
0
© Waleed A. Yousef 2008
entr 20
Linked Queues(to overcome fixed size limitations):
Just get the idea now, do not worry about details.
q.rear q.front q.rear q.front
Node
q
Empty Queue Queue of size 1
pn
New
node
First In Second in Last in
q.rear q.Front How to insert a node
© Waleed A. Yousef 2008 21
Linked Queues(to overcome fixed size limitations):
Just get the idea now, do not worry about details.
How to serve a node
Last in
First In Second in Before Last
q.rear q.Front
pn
© Waleed A. Yousef 2008 22
Type Definition
New
node
First In Second in Last in
typedef struct queuenode{
QueueEntry entry;
struct queuenode *next;
}QueueNode;
typedef struct queue{
QueueNode *front;
QueueNode *rear;
int size;//old trick
}Queue;
© Waleed A. Yousef 2008 23
Implementation level User Level
(what really happens) (interface)
void CreateQueue(Queue *pq){ void main(){
pq->front=NULL;
pq->rear=NULL; Queue q;
pq->size=0;
} CreateQueue(&q);
}
CreateQueue
&q
pq
q
© Waleed A. Yousef 2008 24
void Append(QueueEntry e, Queue* pq){
QueueNode*pn=(QueueNode*)malloc(sizeof(QueueNode));
pn->next=NULL;
pn->entry=e;
User Call:
Queue q;
QueueEntry e;
pq->rear->next=pn;
pq->rear=pn; Append(e, &q);
e
pq->size++; pn
}
&q
pq e
First In Second in Last in
© Waleed A. Yousef 2008 25
Always take care of special cases (queue is empty)
void Append(QueueEntry e, Queue* pq){
QueueNode*pn=(QueueNode*)malloc(sizeof(QueueNode));
pn->next=NULL;
pn->entry=e;
if (!pq->rear)
pq->front=pn;
else
pq->rear->next=pn;//run time error for empty queue
pq->rear=pn;
pq->size++;
}
&q pn
pq
e
© Waleed A. Yousef 2008 26
void Serve(QueueEntry *pe, Queue* pq){
QueueNode *pn=pq->front;
*pe=pn->entry;
pq->front=pn->next;
free(pn);
Last in
pq->size--;
}
First In Second in Before last
&q
pq pn
© Waleed A. Yousef 2008 27
Always take care of special cases: Only one element exists
void Serve(QueueEntry *pe, Queue* pq){
QueueNode *pn=pq->front;
*pe=pn->entry;
pq->front=pn->next;
free(pn);
if (!pq->front)
pq->rear=NULL;
pq->size--;
}
Last in
&q
pq pn
© Waleed A. Yousef 2008 28
Implementation level User Level
(what really happens) (interface)
int QueueEmpty(Queue* pq){ void main(){
return !pq->front;
} Queue q;
int QueueFull(Queue* pq){ CreateQueue(&q);
return 0;
}
}
int QueueSize(Queue* pq){
return pq->size;
}
&q
pq
q
© Waleed A. Yousef 2008 29
void ClearQueue(Queue* pq){
while(pq->front){
pq->rear=pq->front->next;
free(pq->front);
pq->front=pq->rear;
}
pq->size = 0;
}/*Moving with two pointers,
Exactly as in LinkedStacks*/ Last in
First In Second in Before last
&q
pq
© Waleed A. Yousef 2008 30
void TraverseQueue(Queue* pq, void(*pf)(QueueEntry)){
for(QueueNode *pn=pq->front; pn; pn=pn->next)
(*pf)(pn->entry);
}
Last in
First In Second in Before last
&q
pq
pn
© Waleed A. Yousef 2008 31
Very important note for all linked structures. E.g., in Queues:
In Push and Append we have to check for exhausted memory. The code can be
modified to:
int Append(QueueEntry e, Queue* pq){
QueueNode*pn=(QueueNode*)malloc(sizeof(QueueNode));
if (!pn)
return 0;
/*This is much better than the Error message of the book
because this is more flexible. Also, the same function for
contiguous implementation has to return 1 always to have consistent
interface*/
else{
//Put here exactly all of the remaining code
return 1; ...;
} If (!Append(e, &q)){
...;
}
© Waleed A. Yousef 2008 32
