Topical Information

The purpose of this quiz is to give you a chance to focus your knowledge of simple stacks and queues in C++.

Quiz Information

Questions

1. A stack data structure is known as a last in-first out (LIFO) structure. Queues, on the other hand, are known as a first in-first out (FIFO) data structure.

2. Assuming that you are working with a stack, show the order of data in the stack (head to tail) after the following operations are performed: push A, push B, push C, pop, push D, push E, pop, pop, pop, push F, push G, pop, push H, pop, pop, push I, push J, pop, push K, push L, pop, pop, push M.

   
       Let's start at the beginning with push A:
   
       |   |
       +---+
       | A |
       +---+
   
       Then we push B:
   
       |   |
       +---+
       | B |
       +---+
       | A |
       +---+
   
       And so forth:
   
       |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   | |   |
       +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
       | C | | B | | D | | E | | D | | B | | A | | F | | G | | F | | H | | F | | A | | I | | J | | I | | K | | L | | K | | I | | M |
       +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
       | B | | A | | B | | D | | B | | A |       | A | | F | | A | | F | | A |       | A | | I | | A | | I | | K | | I | | A | | I |
       +---+ +---+ +---+ +---+ +---+ +---+       +---+ +---+ +---+ +---+ +---+       +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
       | A |       | A | | B | | A |                   | A |       | A |                   | A |       | A | | I | | A |       | A |
       +---+       +---+ +---+ +---+                   +---+       +---+                   +---+       +---+ +---+ +---+       +---+
                         | A |                                                                               | A |                  
                         +---+                                                                               +---+                  
        pC     p    pD    pE     p     p     p    pF    pG     p    pH     p     p    pI    pJ     p    pK    pL     p     p    pM
   
       Thus the result at the end is MIA from top to bottom.
   
   

3. "A queue isn't just a single letter -- it's followed by four more waiting patiently in line." This Internet wisdom explains much of the data structure's approach. What is left out are its methods. Amongst these we find:

   1. push NO
   2. enqueue YES
   3. size YES
   4. pop NO
   5. dequeue YES

4. If items enter a queue at 3 every 5 minutes but leave at a rate of 2 every 10 minutes, how many items will be in the queue after 20 minutes?

   
       In 20 minutes, there would be 4 arrival groups -- 3*4=12
       -- and two departure groups -- 2*2=4.  Thus there would be
       8 items in the queue at the end of 20 minutes.
   
   

   If items cease entering the queue after 1 hour, how much longer will it take to empty the queue?

   
       Since we are gaining 8 items every 20 minutes, there'd be
       three sets of these by the end of the 1 hour period --
       3*8=24.  If 2 can be processed every 10 minutes, it'll take
       24/2=12 and then 12*10=120 minutes or 2 hours for the queue
       to empty.
   
   

5. Stacks ____.

   1. are FIFO structures NO
   2. have constant time insertion YES
   3. have linear time searching NO
   4. can be stored in array or linked form YES
   5. must be circular if stored in an array NO

6. Queues ____.

   1. are FIFO structures YES
   2. have constant time insertion YES
   3. have linear time searching NO
   4. can be stored in array or linked form YES
   5. must be circular if stored in an array YES

7. To avoid recursion run amok, we can use a loop and what auxiliary data structure? Briefly explain its use.

   
       A stack can provide the back-tracking memory store that would
       normally be provided by the function call stack.  As you loop
       'forward', push old items onto the stack.  As you loop 'backward',
       pop new items for processing off the stack.
   
   

8. Explain the use of inheritance to derive a stack or queue from a general linked list.

   
       We inherit with a private inheritance mode from the linked
       list and implement the new ADT in our public area to call
       through to our [now] private linked list routines.