Lecture 04

(Part II)

Data Structures

Saqib Saleem
Memory Organization

Process 1
(browser) Code
Process 3
(word) Static data

Process 4 Stack
(excel)
Process 2
(dev-c++)

Windows OS Heap
Stack Layout during a call
 Here is stack layout when function F calls function G:

Parameters(F) Parameters(F) Parameters(F)

Local variables(F) Local variables(F) Local variables(F)

Return address(F) Return address(F) Return address(F)

sp
Parameters(G) Parameters(G)
sp
Local variables(G)

Return address(G)
sp
At point of call During execution of G After call
Queues

 A stack is LIFO (Last-In First Out) structure.

 In contrast, a queue is a FIFO (First-In First-Out ) structure.
 A queue is a linear structure for which items can be only inserted
at one end and removed at another end.
Queue Operations

Enqueue(X) – place X at the rear of the

queue.
Dequeue() -- remove the front element and
return it.
Front() -- return front element without removing
it.
IsEmpty() -- return TRUE if queue is
empty, FALSE otherwise
Implementing Queue

 Using linked List: Recall

 Insert works in constant time for either end of a linked list.
 Remove works in constant time only.
 Seems best that head of the linked list be the front of the queue so
that all removes will be from the front.
 Inserts will be at the end of the list.
Implementing Queue

 Using linked List:

front rear front rear

1 7 5 2 1 7 5 2
Implementing Queue

 Using linked List:

front rear front rear

1 7 5 2 1 7 5 2

dequeue()

front rear front rear

7 5 2 1 7 5 2
Implementing Queue

 Using linked List:

front rear front rear

1 7 5 2 1 7 5 2

enqueue(9)

front rear front rear

7 5 2 9 7 5 2 9
Implementing Queue
int dequeue()
{
int x = front->get();
Node* p = front;
front = front->getNext();
delete p;
return x;
}
void enqueue(int x)
{
Node* newNode = new Node();
newNode->set(x);
newNode->setNext(NULL);
rear->setNext(newNode);
rear = newNode;
}
Implementing Queue

int front()
{
return front->get();
}

int isEmpty()
{
return ( front == NULL );
}
Queue using Array

 If we use an array to hold queue elements, both insertions and

removal at the front (start) of the array are expensive.
 This is because we may have to shift up to “n” elements.
 For the stack, we needed only one end; for queue we need both.
 To get around this, we will not shift upon removal of an element.
Queue using Array

front rear
1 7 5 2
1 7 5 2
0 1 2 3 4 5 6 7
front rear
0 3
 Queue using Array

enqueue(6)

front rear
1 7 5 2 6
1 7 5 2 6
0 1 2 3 4 5 6 7
front rear
0 4
 Queue using Array

enqueue(8)

front rear
1 7 5 2 6 8
1 7 5 2 6 8
0 1 2 3 4 5 6 7
front rear
0 5
 Queue using Array

dequeue()

front rear
7 5 2 6 8
7 5 2 6 8
0 1 2 3 4 5 6 7
front rear
1 5
 Queue using Array

dequeue()

front rear
5 2 6 8
5 2 6 8
0 1 2 3 4 5 6 7
front rear
2 5
 Queue using Array

enqueue(9)
enqueue(12)
front rear
5 2 6 8 9 12
5 2 6 8 9 12
0 1 2 3 4 5 6 7
front rear
2 7
enqueue(21) ??
Queue using Array

 We have inserts and removal running in constant time but we

created a new problem.
 Cannot insert new elements even though there are two places
available at the start of the array.
 Solution: allow the queue to “wrap around”.
Queue using Array

 Basic idea is to picture the array as a circular array.

0 1
front
front rear
7 2 2
12 5
5 2 6 8 9 12
6 9 2
8 6 3 rear
7
5 4
Queue using Array

enqueue(21)
0 1
front rear 21 front size
7 2 2 8
12 5
5 2 6 8 9 12 21
6 9 2
8 6 3 rear noElements
0 7
5 4
void enqueue(int x)
{
rear = (rear+1)%size;
array[rear] = x;
noElements = noElements+1;
}
Queue using Array

enqueue(7)
0 1
front rear 21 7 front size
7 2 2 8
12 5
5 2 6 8 9 12 21 7
6 9 2
8 6 3 rear noElements
1 8
5 4
int isFull()
{
return noElements == size;
}

int isEmpty()
{
return noElements == 0;
}
Queue using Array

dequeue()
0 1

front rear 21 7 front size

7 2 4 8
12
6 8 9 12 21 7
6 9
8 6 3 rear noElements
1 6
5 4
int dequeue()
{
int x = array[front];
front = (front+1)%size;
noElements = noElements-1;
return x;
}
Use of Queues

 Out of the numerous uses of the queues, one of the most useful is
simulation.
 A simulation program attempts to model a real-world phenomenon.
 Many popular video games are simulations, e.g., SimCity,
FlightSimulator
 Each object and action in the simulation has a counterpart in real
world.
Uses of Queues

 If the simulation is accurate, the result of the program should

mirror the results of the real-world event.
 Thus it is possible to understand what occurs in the real-world
without actually observing its occurrence.
 Let us look at an example. Suppose there is a bank with four
tellers.
Simulation of a Bank

 A customer enters the bank at a specific time (t1) desiring to

conduct a transaction.
 Any one of the four tellers can attend to the customer.
 The transaction (withdraw, deposit) will take a certain period of
time (t2).
 If a teller is free, the teller can process the customer’s transaction
immediately and the customer leaves the bank at t1+t2.