3.12. Using a Queue in C++

Now that we have clearly defined the queue as an abstract data type, similarly to the how we’ve previously used the Stack, we will turn our attention to using a queue with the help of the Standard Template Library (STL) in C++. Recall that when we give an abstract data type a physical implementation we refer to the implementation as a data structure.

As we described in Chapter 1, in C++, as in any object-oriented programming language, the implementation of choice for an abstract data type such as a queue is the creation of a new class. The queue operations are implemented as methods. However, the STL already has a well written implementation of the Queue class.

The following queue implementation (ActiveCode 1) assumes that the end of the list will hold the rear element of the queue. As the queue grows (as push operations occur), new items will be added on the end of the list. pop operations will manipulate the opposite side, the front end.

Self Check

    Q-1: Suppose you have the following series of queue operations.

    queue<int> intQueue;
    q.push(10);
    q.push(20);
    q.push(30);
    q.pop();
    q = Queue()
    q.push('hello')
    q.push('dog')
    q.push(3)
    q.pop()
    

    What items are left on the queue?

  • 10, 20
  • Remember the first thing added to the queue is the first thing removed. FIFO
  • 20, 30
  • Yes, first in first out means that 10 is gone
  • 10, 30
  • Queues, and Stacks are both data structures where you can only access the first and the last thing.
  • 10, 20, 30
  • Ooops, maybe you missed the pop call at the end?
Next Section - 3.13. Simulation: Hot Potato