PowerPoint Presentation
Queues and Priority Queue
Implementations
Chapter 14
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Content
Implementations of the ADT Queue
An Implementation of the ADT Priority Queue
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
An Implementation That Uses the ADT List
View Listing 14-1 header for class ListQueue
Note implementation, Listing 14-2
FIGURE 14-1 An implementation of the ADT queue that stores its entries in a list
.htm code listing files must be in the same folder as the .ppt files for these links to work
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
A Link-Based Implementation
FIGURE 14-1 An implementation of the ADT queue that stores its entries in a list
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
A Link-Based Implementation
FIGURE 14-3 A circular chain of linked nodes
with one external pointer
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
A Link-Based Implementation
View header file for class LinkedQueue,
Listing 14-3
The enqueue method to insert a new node
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
A Link-Based Implementation
FIGURE 14-4 Adding an item to a nonempty queue
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
A Link-Based Implementation
FIGURE 14-5 Adding an item to an empty queue:
(a) before enqueue; (b) after enqueue
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
A Link-Based Implementation
Definition for the method enqueue
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
A Link-Based Implementation
Definition of
the method
dequeue
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
A Link-Based Implementation
FIGURE 14-6 Removing an item from
a queue of more than one item
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
A Link-Based Implementation
FIGURE 14-6 Removing an item from
a queue of more than one item
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
An Array-Based Implementation
Possible (naïve) definition
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
An Array-Based Implementation
FIGURE 14-7 (a) A naive array-based
implementation of a queue; (b) rightward drift
can cause the queue to appear full
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
An Array-Based Implementation
FIGURE 14-8 A circular array as an
implementation of a queue
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
An Array-Based Implementation
FIGURE 14-9 The effect of three consecutive
operations on the queue in Figure 14-8
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
An Array-Based Implementation
FIGURE 14-10 (a) front passes back
when the queue becomes empty;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
An Array-Based Implementation
FIGURE 14-10 (b) back catches up to
front when the queue becomes full
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
An Array-Based Implementation
The header file for the class ArrayQueue, Listing 14-4
View implementation file, Listing 14-5
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Variation of Circular Queue
FIGURE 14-11 A more time-efficient circular implementation: (a) a full queue; (b) an empty queue
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Implementation of the ADT Priority Queue
View header file, Listing 14-6
Note add and remove functions
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
End
Chapter 14
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013