S1: Linear Data Structures: Stacks, Queues, Priority Qs
- Goals
- Learn 3 basic data structures
- Motivation
- Functional Specification - ADT Interfaces
- Invariant Properties (e.g. FIFO, LIFO, ...)
- Learn how to use these linear data structures
- Comparison - simulate one using the other
- Applications - select natural DS for problems
- Exercises
- Reading: Ch#5 (Textbook)
- Recommended Ex. 5.1, 5.3, 5.5-6, 5.8, 5.12-18
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S2: 3 Simple Data Structures (Stacks, Queues, Priority Qs )
- Motivation
- Simple and basic organization of collections
- Almost all programs use one of these
- A STACK is always implicit in your programs
- QUEUE is a fundamental type in Simulation languages.
- Specifying the Data Structures
- Functional Specs
- What can be called a Stack/Queue?
- What operations are available?
- Constraints / Invariants
- What can one assume to reason about Queues/Stacks?
- Performance - (not in 3321)
- Let us use abstract data type notation
- Use C++ class for now. Use class template later (Ch#7)
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S3: Functional Specs for Linear Data Structures
- Stack - member functions
int StackEmpty()
DataType Peek( ) // return the element on top
void Push( const DataType & X) // add X on top
DataType Pop( ) // remove the top element
- Queue - member functions
int QEmpty()
DataType QFront( ) // return element in front
void QInsert( const DataType & X) // add X to rear
DataType QDelete( ) // remove the element in front
- Priority Queue - member functions
int PQEmpty()
DataType PQFront( ) // return highest priority element
void PQInsert( const DataType & X) // add X to rear
DataType PQDelete( ) // remove highest priority element
- Properties:
- Stack: LIFO - last in first out
- Queue: FIFO - first in first out
- PQueue: out in order of priority
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S4: Exercises
- Which data-structure is natural for following?
- 1. organize numbers to Find the minimum element.
- 2. organize students to Find the student who arrived first
- 3. organize copies of daily newspaper to Find latest one
- 4. organize items to be Bought in a grocery store
- Ex.: Write a program to reverse the characters in a word.
- Example: Evaluating postfix expressions using a stack
- 1. create an empty stack of integers
- 2. While not(end of expression) do
- 2.1 Get next character
- 2.2 If char is a digit then
- 2.2.1 read_integer() and push on stack
- 2.3 else if char is an operator
- 2.3.1 pop the top 2 operands and evaluate operation
- 2.3.2 push result on stack
- 3. Display the result
- Ex.: Test the algorithm with following :
- 5 6 * 1 +, 5 6 1 * + and 5 6 1 + *
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S5: 5.4 Queues
- Linear Collection
- Stores a list of elements
- Insert at rear
- Delete from front
- First-In-First-Out (FIFO)
- Applications
- How many servers? (e.g. bank tellers, hospital (doctors)
- Scheduling Policy
- Fair, Priority (Minimize wait or Maximize server utilization)
- Ex.
- Freeway Ramp Queues
- C.P.U. scheduling
- Elevator scheduling
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S6: QUEUE ADT
- Data : int front, rear, count; DataType list[max];
- Invariant Property: list[ ] has items in order of arrival
- count, front and rear are related by an equation
- Operations
Queue (void);
void QInsert (const DataType & item);
DataType QDelete (void);
void ClearQueue (void);
DataType QFront (void) const;
int QLength (void) const;
int QEmpty (void) const;
int QFull (void) const;
- Comparison with Stack ADT
- Q? Stack implementation use only count and list[max].
- Why do we need front and rear besides count?
- Why do we need count besides front and rear?
- Q? Why do we need Queue::QLength(), i.e.
- Q? Why don't we have Stack::SLength()
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S7: USING QUEUES
- Ex. Consider the following Radix Sort (pp 216-9) algorithm
Input: set of 2 digit numbers
Output: sorted set...
Data: Queue Q, dQs[10]
1) read and insert numbers into Queue Q;
2) while(!Q.QEmpty){ n=Q.QDelete(); dQs[n%10].QInsert(n);}
3) for (i=0; i < 10; i++)
while(!dQs[i].QEmpty){n=dQs[i].QDelete(); Q.QInsert(n);}
4) while (!Q.QEmpty){n=Q.Delete();dQs[n/10].QInsert(n);}
5) Repeat step 3
6) Print Elements of Q
- Exercise - Trace the states of all 11 Queues after each step
- (i) Step 1 inputs = 91, 46, 85, 15
- (ii) Step 1 inputs = 91, 46, 85, 15, 92, 35, 31, 22
- Hint: See Figure (pp 217) for a trace.
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S8: IMPLEMENTATION
- Invariant: Keep elements in order of arrival
- Front points to the element arrived first
- Rear points to the element arrived last
- No holes
- Option 1: (like stack and list)
- To avoid hole, Shift array element in QDelete ()
- Option 2: Circular Model - view array as a circular list
- NO shifting needed, Instead move front and rear pointers
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S9: IMPLEMENTATION
- Lessons from the execution trace
- Q. Why do we need front and rear ?
- Q. If rear = front, What is count?
- Q. Why do we need count besides front and rear?
- Q. Write a function f, s.t. rear = f ( front, count ).
- Q? Is circular list implementation correct (FIFO)?
- Three integers - count, front, rear
- Zero or N (from property), i.e. empty or full!
- Property: rear = (front + count) mod N
void Queue:: QInsert( .... item)
{if (!QFull()) {
count++;
qlist[rear] = item;
rear = (rear+1) % N; // modulo N arithmetic
}
- Queue::QDelete (... );
{if (!QEmpty()) {
count--;
front=(front+1) % N; // modulo N arithmetic
return(... );
}
- Determine the minimum and maximum values for count, front, rear?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S10: 5.6 PRIORITY QUEUES
- Application to Computer - Jobs
- Consider following jobs
- Compute Average Waiting Time
- (i) Determine Order of Service
- (ii) Compute start time and wait
- (ii) Compute average
- For following policies
- (i) FCFS
- (ii) Shortest job first
- Priority scheduler algorithm used in operating systems
While (!pq.PQEmpty()) { nextjob = pq.PQDelete(); serve(nextjob); }
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S11: PRIORITY QUEUE ADT
- Idea - similar to Queue, except
- Data items have priority
- Access highest priority item
- Data Members
- int count; //
- DataType pqlist[max];
- Operations
void PQInsert (DataType & Item);
DataType PQDelete (void);
int PQEmpty(void) const;
int PQFull(void) const;
- Q? Where is the "priority" information about elements ?
- Q? Can FCFS Queue be implemented using a priority Queue? How?
- Q? Can a stack be implemented using a priority Queue? How?
- Q? Which is closer to Priority Queue?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S12: IMPLEMENTATION
- Properties:
pqlist[0]... pqlist [count-1] have data
Ordering of data is irrelevant in pqlist[]
Operator ' < ' compares items
- Void PQueue::PQInsert (DataType & Item)
{ if (!PQFull()) {
pqlist [count] = Item;
count++;
}
- PQDelete : Issue of Remove Holes
- Options 1: Shift elements
- Options 2: Put last element in place of deleted element.
- Q? Is option 1 ever interesting? (See Ex. 5.18)
- Q? Is option 2 relevant for Queues? stacks ? lists?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S13: IMPLEMENTATION -2
- DataType PQueue::PQDelete (void)
{ DataType min;
int i; min_index;
if (!PQEmpty())
{
//FIND MINIMUM
min = pqlist[0];
for (i=1; i < count; i++) {min = pqlist[i]; min_index = i;}
//DELETE & REMOVE HOLE
pqlist[min_index] = pqlist[count-1]
count--;
}
- Q? If two items have the same priority, we would like to
- use FIFO to break the tie. Will this implementation do so?
- Q? What if shifting is used to remove the hole?
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S14: EXERCISES
- Implement a queue using a set of stacks.
- Do not use additional arrays or linked lists.
- Implement a stack using a set of queues.
- Do not use additional arrays or linked lists.
- Ex. 5.15 (pp 247-8) What is the action of the following:
Stack S; int elt;
While (!Q.QEmpty()) {elt = Q.QDelete(); S.Push(elt);}
While (!S.StackEmpty()) {elt = S.Pop();Q.QInsert(elt);}
Copyright: S. Shekhar, C. S. Dept.,
University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)