S1: Linear Data Structures: Stacks, Queues, Priority Qs
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?
    • Queue
    • List
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)