Transcript PPT

CS-362: Data Structures
Week 8
Dr. Jesús Borrego
1
scis.regis.edu ● [email protected]
Topics
• Stacks
• Queues
• Final Exam
• Pointers = Punteros
2
Key Terms
• Stack – Pilas
▫ Push – Insertar
▫ Pop - Quitar
• Queue – Colas
▫ Enque – Insertar
▫ Dequeue - Eliminar
3
Stacks
4
Stack with Arrays
• Element 1 can go in first array position, the
second in the second position, etc.
• The top of the stack is the index of the last
element added to the stack
• Stack elements are stored in an array
• Stack element is accessed only through top
• To keep track of the
• top position, use a variable called Top
5
Stack using an Array
6
Stacks
• If Top = 0, the stack is empty
• If Top = MAX, stack is full
• Store the newItem in the array component
indicated by Top
• Increment Top
• Must avoid an overflow (or underflow)
7
Queue
• Queue: list 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
8
Queue Operations
▫
▫
▫
▫
▫
▫
▫
9
initializeQueue
isEmptyQueue
isFullQueue
front
back
addQueue
deleteQueue
Queue implementation
• You need at least four 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
10
Adding elements
• 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
11
Deleting Elements
• To delete an element from the queue:
▫ Retrieve element pointed to by queueFront
▫ Advance queueFront to next queue element
12
Implementation of Queues as Arrays
(cont'd.)
• 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...
Implementation of Queues as Arrays
(cont'd.)
• The sequence AAADADADADADADADA... would
eventually set queueRear to point to the last
array position
▫ Giving the impression that the queue is full
Implementation of Queues as Arrays
(cont'd.)
• 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
Implementation of Queues as Arrays
(cont'd.)
• To advance the index in a (logically) circular
array:
Implementation of Queues as Arrays
(cont'd.)
17
Implementation of Queues as Arrays
(cont'd.)
• Case 1:
Implementation of Queues as Arrays
(cont'd.)
• Case 2:
Implementation of Queues as Arrays
(cont'd.)
• Problem:
▫ Figures 19-32b and 19-33b have identical
values for queueFront and queueRear
▫ However, the former represents an empty
queue, whereas the latter shows a full queue
• Solution?
Implementation of Queues as Arrays
(cont'd.)
• 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
Implementation of Queues as Arrays
(cont'd.)
• 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
Implementation of Queues as Arrays
(cont'd.)
23
Summary
• Stacks and Queues are important data
structures
• Can be implemented as arrays or linked lists
• We will see in OOP that we can create
Abstract Data Types to protect the integrity of
the data
24
Final Exam
• 8 questions from material covered since the
mid term
• Answer all 8 questions; equal weight
• Submit to WorldClass week 8
• Due by Monday midnight (12/16/13)
• Must have all late submissions by Sunday
midnight to get credit
25