CP1300 Stacks and Queues

Content

• An Abstract Data Type (ADT) consists of a set of values, a defined set of properties of these values, and a set of operations for processing the values.

• Stack ADT (p.605)
  • Values: Ordered list of items
  • Properties: Zero or more items. Items are added and removed from one designated end called the top.
  • Operations
    • Initialise - Sets the stack to empty.
    • Push - Adds an item onto the stack.
    • Pop - Removes the top item and returns it.
    • Empty - Determines whether or not there are any items on the stack.
    • Top of stack - Returns the top item on the stack, but does not remove it.
  • Trying to pop an element off an empty stack is called underflow.
  • Whilst a stack is conceptually unbounded, in implementation the maximum number of elements on a stack may be fixed - thus eventually successive Pushs (without matching Pops) will cause the stack to overflow.

• Examples
  • Geoff's dive bag
  • Cars in a non-circular driveway
  • Nested function calls (p.607)
  • Code formatting and expression syntax (p.613)
  • Evaluation of arithmetic expressions (p.616)

• Stack class
  • stackclass.h
  • stackclass.cpp

• Application - Evaluation of arithmetic expressions (p.616)
  • Compilers convert the infix expressions used in programming to postfix expressions, and generate machine code to evaluate them at run time.
  • Postfix notation
    • In infix the operator is written between the operands. E.g.,
      A * B + (C - D / E)
    • In postfix the operator is written after the operands. E.g.,
      AB*CDE/-+
    • In postfix no ()s are needed, i.e., the evaluation is unambiguous and does not rely on operator precedence.
  • Converting infix to postfix (p.618)
    • By hand, add ()s to all subsexpressions, then move the operators to the position of the corresponding ), and delete the (s. E.g.,

           A * B  + (C -  D / E)
         ((A * B) + (C - (D / E)))
         ((A   B*   (C   (D   E/-+
           A   B*    C    D   E/-+
                     

    • By a program

         Initialise stack
         Read symbol ch
         While not end of expression
             If ch is an operand
                 Append it to the postfix
             If ch is (
                 Push ch
             If ch is )
                 Pop stack
                 While popped value is not (
                     Append popped value to postfix
                     Pop stack
             If ch is an operator
                 While stack not empty, and
                       top of stack != (, and
                       priority of top of stack >= priority of ch
                     Pop stack
                     Append popped value to postfix
                 Push ch
             Read symbol ch
         While stack not empty
              Pop stack
              Append popped value to postfix
                     

    • Infix	Stack	Postfix
      A * B + (C - D / E)	Empty
      * B + (C - D / E)	Empty	A
      B + (C - D / E)	*	A
      + (C - D / E)	*	AB
      (C - D / E)	+	AB*
      C - D / E)	(+	AB*
      - D / E)	(+	AB*C
      D / E)	-(+	AB*C
      / E)	-(+	AB*CD
      E)	/-(+	AB*CD
      )	/-(+	AB*CDE
      	+	AB*CDE/-
      		AB*CDE/-+

  • Evaluating postfix (p.622)

    •    Read symbol ch
         While not end of expression
             If ch is an operand
                 Push ch
             Else Pop RHS
                  Pop LHS
                  Compute LHS ch RHS
                  Push result
             Read symbol ch
         Pop stack and print result
                     

    • Example, with A = 5, B = 3, C = 6, D = 8, E = 2

      Postfix	Stack
      AB*CDE/-+	Empty
      B*CDE/-+	A
      *CDE/-+	BA
      CDE/-+	15
      DE/-+	C 15
      E/-+	DC 15
      /-+	EDC 15
      -+	4 C 15
      +	2 15
      	17

      And the answer is 17.

• Queue ADT (p.627)
  • Values: Ordered list of items
  • Properties: Zero or more items. Items are added to from one designated end called the rear (or tail). Items are removed from the other end, called the front (or head).
  • Operations
    • Initialise - Sets the queue to empty.
    • Enqueue - Adds an item onto the rear.
    • Dequeue - Removes an item from the front, and returns it.
    • Empty - Determines whether or not there are any items in the queue.
    • Front of queue - Returns the item at the front of the queue, but does not remove it.
  • Trying to dequeue an item off an empty queue is called underflow.
  • Whilst a queue is conceptually unbounded, in implementation the maximum number of elements on a queue may be fixed - thus eventually successive Enqueues (without matching Dequeues) will cause the stack to overflow.

• Examples
  • Simluation (p.628)
  • Job scheduling in the operating system
  • Cars in a circular driveway

• Queue class
  • Naive array implementation (p.633)
    • An array stores the items
    • A front index points to the item at the front of the queue; initially front = 0.
    • A rear index point to the last item on the queue; initially rear = -1.
    • When rear + 1 == front, the queue is empty.
    • When items are enqueued, the rear index is incremented.
    • When items are dequeued, the front index is incremented.
    • When rear + 1 == QUEUE_SIZE, the queue is full.
    • What to do when the rear index reaches the last array index?
      • Shift everything down to the bottom of the array.
      • Move the rear index round to the bottom of the array.
  • Circular array implementation (p.638 (is weak))
    • An array stores the items
    • A front index points to the item at the front of the queue; initially front = 0.
    • A rear index point to the last item on the queue; initially rear = -1.
    • When (rear + 1) % QUEUE_SIZE == front, the queue is empty.
    • When items are enqueued, the rear index is incremented modulo QUEUE_SIZE.
    • When items are dequeued, the front index is incremented modulo QUEUE_SIZE.
    • If the rear pointer wraps round to one behind the front pointer, it looks like the queue is empty.
    • When (rear + 2) % QUEUE_SIZE = front, the queue is full. One array position is unused.
  • queueclass.h
  • queueclass.cpp

• Application - Simulation (p.628)
  • Octopus.cpp - Octopus car wash simulation.

• Stacks
• Queues

Tutorial Questions

• Postfix by Hand
• Converting Infix to Postfix

Exam style questions

1. Name and briefly describe the basic operations that are performed on stacks.
2. Convert the following infix expressions to postfix
   • A + B * (C - D) * C - D
   • A - (A - A) + A * A
   • etc etc
3. Show the sequence of stack contents for the evaluation of the following postfix expression, using the values A=3, B=5, C=6, D=-4.
   • ABCD-*C*+D-
4. Three basic operations that are performed on stacks are:
   • Initialise - sets the stack to be empty
   • Push - adds an item to the top of the stack, if possible
   • Pop- removes an item from the top of the stack, if possible
   Write the header file for a C++ class of stacks, for up to 100 integers, with these operations and a default constructor. The stack data must be stored in an array. The push and pop operations must return a Boolean value indicating their success (you may use the boolean type defined in boolean.h).
5. Three basic operations that are performed on queues are:
   • Initialise - sets the queue to be empty
   • Enqueue - adds an item to the rear of the queue, if possible
   • Dequeue- removes an item from the front of the queue, if possible
   Following is a header file for a C++ class of queues, for up to 100 integers, with these operations and a default constructor. Write the implementation for the Initialise and Enqueue member functions, using the "wrap-around" implementation of queues with an array.

   #include "boolean.h"
   
   const int MAX_QUEUE = 100;
   typedef int queue_type[MAX_QUEUE];
   //--------------------------------------------------------------
   class queue {
   
   public:
   
   queue(void);
   void Initialize(void);
   boolean Enqueue(int Item);
   boolean Dequeue(int& Item);
   
   private:
   
   queue_type TheQueue;
   int Front,Rear;
   };