Stacks, Queues, and Deques

• A stack is a last in, first out (LIFO) data structure

– Items are removed from a stack in the reverse order
from the way they were inserted
• A queue is a first in, first out (FIFO) data structure
– Items are removed from a queue in the same order as
they were inserted
• A deque is a double-ended queue—items can be
inserted and removed at either end

1
 Queues
• Queue data structure
– Elements added at one end (rear), deleted from other
end (front)
– First In First Out (FIFO)
– Middle elements inaccessible

2
 Queue Operations

• Two key operations

– addQueue
– deleteQueue
• Additional operations
– initializeQueue, isEmptyQueue,
isFullQueue, front, back
• queueFront, queueRear pointers
– Keep track of front and rear

3
 Implementation of Queues as Arrays
• Four member variables
– Array to store queue elements
– Variables queueFront, queueRear
– Variable maxQueueSize
• Using queueFront, queueRear to access queue
elements
– queueFront: first queue element index
– queueRear: last queue element index
• queueFront changes after each deleteQueue
operation
• queueRear changes after each addQueue operation

4
 Implementation of Queues as Arrays
(cont’d.)
• Execute operation
– addQueue(Queue,'A');
• Execute
– addQueue(Queue,'B');
– addQueue(Queue,'C');
• Execute
– deleteQueue();

5
1 Queue after the first addQueue operation

2 Queue after two more addQueue operations

3 Queue after the deleteQueue operation

6
 Implementation of Queues as Arrays
(cont’d.)
• Consider the sequence of operations:
AAADADADADADADADA...
– Eventually index queueRear points to last array
position
• Looks like a full queue
• Reality: queue has two or three elements, array empty
in the front

4 Queue after the sequence

of operations AAADADADADADA...
7
 Implementation of Queues as Arrays
(cont’d.)
• First solution
– Upon queue overflow to the rear
• Check value of queueFront
• If room in front: slide all queue elements toward first
array position
– Works if queue size very small
• Second solution: assume circular array

5 Circular queue
8
 Implementation of Queues as Arrays
(cont’d.)
• queueRear = (queueRear + 1) %
maxQueueSize;
– Advances queueRear (queueFront) to next array
position

6 Queue before and after the add operation

9
 Implementation of Queues as Arrays
(cont’d.)
• If queueRear < maxQueueSize – 1
– queueRear + 1 <= maxQueueSize – 1
– (queueRear + 1) % maxQueueSize = queueRear +
1
• If queueRear == maxQueueSize – 1
– queueRear + 1 == maxQueueSize
– (queueRear + 1) % maxQueueSize = 0
• queueRear set to zero
– First array position

10
 Implementation of Queues as Arrays
(cont’d.)
• Two cases with identical queueFront, queueRear
values
– 7 represents an empty queue
– 8 represents a full queue

7 Queue before and after the delete operation

8 Queue before and after the add operation

11
 Implementation of Queues as Arrays
(cont’d.)
• First solution: use variable count
– Incremented when new element added
– Decremented when element removed
– Functions initializeQueue, destroyQueue
initialize count to zero

12
 Implementation of Queues as Arrays
(cont’d.)
• Second solution
– queueFront indicates index of array position
preceding first element of the queue
– Assume queueRear indicates index of last element
• Empty queue if queueFront == queueRear
– Slot indicated by index queueFront is reserved
– Queue is full
• If next available space represents special reserved slot

13
Implementation of Queues as Arrays
(cont’d.)

9 Array to store the queue

elements with a reserved slot

14
 Empty Queue and Full Queue
• Empty queue
– If count == 0
• Full queue
– If count == maxQueueSize

15
 Initialize Queue
• Initializes queue to empty state
– First element added at the first array position
– Initialize queueFront to zero, queueRear to
maxQueueSize - one, count to zero

10 Empty queue

16
 Front

• Returns first queue element

– If the queue nonempty
• Element indicated by index queueFront returned
– Otherwise
• Program terminates

17
 Back

• Returns last queue element

– If queue nonempty
• Returns element indicated by index queueRear
– Otherwise
• Program terminates

18
Add Queue

19
Delete Queue

20
Constructors and Destructors

21
 Constructors and Destructors (cont’d.)

• Array storing queue elements

– Created dynamically
– When queue object goes out of scope
• Destructor deallocates memory occupied by the array
storing queue elements

22
 Linked Implementation of Queues

• Array implementation issues

– Fixed array size
• Finite number of queue elements
– Requires special array treatment with the values of
the indices queueFront, queueRear
• Linked implementation of a queue
– Simplifies special cases of the array implementation
– Queue never full

23
 Empty and Full Queue
• Empty queue if queueFront is NULL
• Memory allocated dynamically
– Queue never full
– Function implementing isFullQueue operation
returns the value false

24
 Initialize Queue

• Initializes queue to an empty state

– Empty if no elements in the queue

25
 addQueue, front, back, and
deleteQueue Operations
• addQueue operation adds a new element at end of
the queue
– Access the pointer queueRear

26
 addQueue, front, back, and
deleteQueue Operations (cont’d.)
• If queue nonempty
– Operation front returns first element
– Element indicated queueFront returned
• If queue empty: front terminates the program

27
 addQueue, front, back, and
deleteQueue Operations (cont’d.)
• If queue nonempty
– Operation back returns last element
– Element indicated by queueRear returned
• If queue empty: back terminates the program

28
 addQueue, front, back, and
deleteQueue Operations (cont’d.)
• If queue nonempty
– Operation deleteQueue removes first element
• Access pointer queueFront

29
 addQueue, front, back, and
deleteQueue Operations (cont’d.)
• Default constructor
– When queue object goes out of scope
• Destructor destroys the queue
• Deallocates memory occupied by the queue elements
– Function definition similar to function
initializeQueue

30
 Queue Derived from the class
unorderedLinkedListType
• Linked queue implementation
– Similar to forward manner linked list implementation
– Similar operations
• add Queue, insertFirst
• initializeQueue , initializeList
• isEmptyQueue, isEmptyList
– deleteQueue operation implemented as before
– Same pointers
• queueFront and first, queueRear and last

31
 Queue Derived from the class
unorderedLinkedListType
(cont’d.)
• Linked queue implementation (cont’d.)
– Can derive the class to implement the queue from the
class linkedListType
– class linkedListType
• An abstract
• Does not implement all operations
– class unorderedLinkedListType
• Derived from class linkedListType
• Provides definitions of the abstract functions of the
class linkedListType

32
STL class queue (Queue Container
Adapter)
• Standard Template Library (STL)
– Provides a class to implement queues in a program
– Queue
• Name of class defining the queue
• Name of header defining class queue

33
 STL class queue (cont’d.)
• Queue container class
– Provides relational operators comparing two queues
• See Example 8-2
TABLE 1 Operations on a queue object

34
 Priority Queues
• Queue structure ensures items processed in the
order received
• Priority queues
– Customers (jobs) with higher priority pushed to the
front of the queue
• Implementation
– Ordinary linked list
• Keeps items in order from the highest to lowest priority
– Treelike structure
• Very effective

35
 STL class priority_queue
• class template priority_queue<elemType>
– Queue element data type specified by elemType
– Contained in the STL header file queue
• Specifying element priority
– Default priority criteria for the queue elements
• Less-than operator (<)
– Overloading the less-than operator (<)
• Compare the elements
– Defining a comparison function to specify the priority

36
 Application of Queues: Simulation

• Simulation
– Technique in which one system models the behavior
of another system
• Computer simulation
– Represents objects being studied as data
– Actions implemented with algorithms
• Programming language implements algorithms with
functions
• Functions implement object actions

37
 Application of Queues: Simulation
(cont’d.)
• Computer simulation (cont’d.)
– C++ combines data, data operations into a single unit
using classes
• Objects represented as classes
• Class member variables describe object properties
• Function members describe actions on data
– Change in simulation results occurs if change in data
value or modification of function definitions occurs
– Main goal
• Generate results showing the performance of an existing
system
• Predict performance of a proposed system
38
 Application of Queues: Simulation
(cont’d.)
• Queuing systems
– Computer simulations
• Queues represent the basic data structure
– Queues of objects
• Waiting to be served by various servers
– Consist of servers and queues of objects waiting to be
served

39
 Designing a Queuing System

• Server
– Object that provides the service
• Customer
– Object receiving the service
• Transaction time (service time)
– Time required to serve a customer
• Queuing system consists of servers, queue of
waiting objects
– Model system consisting of a list of servers; waiting
queue holding the customers to be served
40
 Designing a Queuing System (cont’d.)
• Modeling a queuing system: requirements
– Number of servers, expected customer arrival time,
time between customer arrivals, number of events
affecting system
• Time-driven simulation
– Clock implemented as a counter
– Passage of time
• Implemented by incrementing counter by one
• Run simulation for fixed amount of time
– Example: run for 100 minutes
• Counter starts at one and goes up to 100 using a loop
41