Transcript Chapter 18 part 3

C++ Programming:
Program Design Including
Data Structures, Fourth Edition
Chapter 18: Stacks and Queues
(part 3)
Queues
• Queue: group of homogeneous elements
• Elements are:
− Added at one end (the back or rear)
− Deleted from the other end (the front)
• First In First Out (FIFO) data structure
− Middle elements are inaccessible
• Example:
− Waiting line in a bank
C++ Programming: Program Design Including Data Structures, Fourth Edition
2
Queue Operations
• Some of the queue operations are:
− initializeQueue
− isEmptyQueue
− isFullQueue
− front
− back
− addQueue
− deleteQueue
• Abstract class queueADT defines these
operations
C++ Programming: Program Design Including Data Structures, Fourth Edition
3
Implementation of Queues as
Arrays
• You need at least four (member) variables:
− An array to store the queue elements
− queueFront and queueRear
• To keep track of first and last elements
− maxQueueSize
• To specify the maximum size of the queue
C++ Programming: Program Design Including Data Structures, Fourth Edition
4
Implementation of Queues as
Arrays (continued)
• To add an element to the queue:
− Advance queueRear to next array position
− Add element to position pointed by queueRear
• Example: array size is 100; originally empty
C++ Programming: Program Design Including Data Structures, Fourth Edition
5
Implementation of Queues as
Arrays (continued)
• To delete an element from the queue:
− Retrieve element pointed to by queueFront
− Advance queueFront to next queue element
C++ Programming: Program Design Including Data Structures, Fourth Edition
6
Implementation of Queues as
Arrays (continued)
• Will this queue design work?
− Suppose A stands for adding an element to
the queue
− And D stands for deleting an element from the
queue
− Consider the following sequence of
operations:
• AAADADADADADADADA...
C++ Programming: Program Design Including Data Structures, Fourth Edition
7
Implementation of Queues as
Arrays (continued)
• The sequence AAADADADADADADADA...
would eventually set queueRear to point to
the last array position
− Giving the impression that the queue is full
C++ Programming: Program Design Including Data Structures, Fourth Edition
8
Implementation of Queues as
Arrays (continued)
• Solution 1:
− When the queue overflows to the rear (i.e.,
queueRear points to the last array position):
• Check value of queueFront
• If value of queueFront indicates that there is
room in the front of the array, slide all of the
queue elements toward the first array position
• Problem: too slow for large queues
• Solution 2: assume that the array is circular
C++ Programming: Program Design Including Data Structures, Fourth Edition
9
Implementation of Queues as
Arrays (continued)
• To advance the index in a (logically) circular
array:
C++ Programming: Program Design Including Data Structures, Fourth Edition
10
Implementation of Queues as
Arrays (continued)
• Case 1:
C++ Programming: Program Design Including Data Structures, Fourth Edition
11
Implementation of Queues as
Arrays (continued)
• Case 2:
C++ Programming: Program Design Including Data Structures, Fourth Edition
12
Implementation of Queues as
Arrays (continued)
• Problem:
− Figures 18-47 and 18-49 have identical values
for queueFront and queueRear
− However, the former represents an empty
queue, whereas the latter shows a full queue
• Solution?
C++ Programming: Program Design Including Data Structures, Fourth Edition
13
Implementation of Queues as
Arrays (continued)
• Solution 1: keep a count
− Incremented when a new element is added to
the queue
− Decremented when an element is removed
− Initially, set to 0
− Very useful if user (of queue) frequently needs
to know the number of elements in the queue
• We will implement this solution
C++ Programming: Program Design Including Data Structures, Fourth Edition
14
Implementation of Queues as
Arrays (continued)
• Solution 2: let queueFront indicate index of
the array position preceding the first element
− queueRear still indicates index of last one
− Queue empty if:
• queueFront == queueRear
− Slot indicated by queueFront is reserved
• Queue can hold 99 (not 100) elements
− Queue full if the next available space is the
reserved slot indicated by queueFront
C++ Programming: Program Design Including Data Structures, Fourth Edition
15
Empty Queue and Full Queue
C++ Programming: Program Design Including Data Structures, Fourth Edition
18
Initialize Queue
C++ Programming: Program Design Including Data Structures, Fourth Edition
19
Front
• Returns the first element of the queue
C++ Programming: Program Design Including Data Structures, Fourth Edition
20
Back
• Returns the last element of the queue
C++ Programming: Program Design Including Data Structures, Fourth Edition
21
addQueue
C++ Programming: Program Design Including Data Structures, Fourth Edition
22
deleteQueue
C++ Programming: Program Design Including Data Structures, Fourth Edition
23
Constructors and Destructors
C++ Programming: Program Design Including Data Structures, Fourth Edition
24
Constructors and Destructors
(continued)
• The array to store the queue elements is
created dynamically
− When the queue object goes out of scope, the
destructor simply deallocates the memory
occupied by the array
C++ Programming: Program Design Including Data Structures, Fourth Edition
25
Linked Implementation of Queues
• Array size is fixed: only a finite number of
queue elements can be stored in it
• The array implementation of the queue
requires array to be treated in a special way
− Together with queueFront and queueRear
• The linked implementation of a queue
simplifies many of the special cases of the
array implementation
− In addition, the queue is never full
C++ Programming: Program Design Including Data Structures, Fourth Edition
26
Linked Implementation of Queues
(continued)
• Elements are added at one end and removed
from the other
− We need to know the front of the queue and
the rear of the queue
• Two pointers: queueFront and queueRear
C++ Programming: Program Design Including Data Structures, Fourth Edition
27
Empty and Full Queue
• The queue is empty if queueFront is NULL
• The queue is never full
C++ Programming: Program Design Including Data Structures, Fourth Edition
30
Initialize Queue
• Initializes queue to an empty state
− Must remove all the elements, if any
C++ Programming: Program Design Including Data Structures, Fourth Edition
31
addQueue
C++ Programming: Program Design Including Data Structures, Fourth Edition
32
front and back Operations
C++ Programming: Program Design Including Data Structures, Fourth Edition
33
deleteQueue
C++ Programming: Program Design Including Data Structures, Fourth Edition
34
Default Constructor
C++ Programming: Program Design Including Data Structures, Fourth Edition
35
Summary
• Stack: items are added/deleted from one end
− Last In First Out (LIFO) data structure
− Operations: push, pop, initialize, destroy,
check for empty/full stack
− Can be implemented as array or linked list
− Middle elements should not be accessed
• Postfix notation: operators are written after
the operands (no parentheses needed)
C++ Programming: Program Design Including Data Structures, Fourth Edition
36
Summary (continued)
• Queue: items are added at one end and
removed from the other end
− First In First Out (FIFO) data structure
− Operations: add, remove, initialize, destroy,
check if queue is empty/full
− Can be implemented as array or linked list
− Middle elements should not be accessed
− Restricted versions of arrays and linked lists
C++ Programming: Program Design Including Data Structures, Fourth Edition
37