Section 5 - STL Stacks and Queues

7B.5.1 A Review of our Custom Stack

Previously, we used inheritance to create re-usable stacks by using ordinary class inheritance and deriving classes from a generic Node class and List class. In one case, we created a FloatStack class in this manner.  There is nothing wrong with this approach - it produces a very robust and predictable design approach that is extensible to many data types.  However, we want to see how we could use the STL templates to circumvent much of our development and get right into the client application. 

First, let's review our earlier client (which assumes that we have laid the groundwork by defining the Node, Stack, FloatNode and FloatStack classes):

// main method ---------------------------------------
int main()
{
  FloatStack fstk;
  float f;

  fstk.push(1.1);
  fstk.push(2.2);
  fstk.push(3.3);
  fstk.push(4.4);

  for (int k = 0; k < 5; k++)
    if (fstk.pop(f))
      cout << f << " ";
    else
      cout << "(empty stack) ";
    cout << endl;

  return 0;
}

/* ----------------- Program Run -------------------

4.4 3.3 2.2 1.1 (empty stack)
Press any key to continue . . .

-------------------------------------------------- */

We will see how we can get the same result without any of the pre-development by exploiting the existing STL stack template.

7B.5.2 STL Stacks

As we saw, a stack is a LIFO data structure.  In C++ the container that behaves like a stack is called, not surprisingly, "stack".  Here is a simple instantiation of a float stack:

stack<float> fstk(100);

Once defined, you can use fstk much like we did using our older schema, through member methods push() and pop().  However, the syntax and meaning of these methods is not exactly the same as before. The method size() works as it did with the vector template.  push() also works the same as before, but pop() merely removes the top of the stack without returning it;  top() is the method used to return the value on the top of the stack.  This means we normally use top() and pop() in concert to pop an item off the stack..

Here is a simple example of the use of stack.  Notice that you have to #include <stack> at the top of your file to gain access to these tools.  You'll also see that because of the nature of what a stack is, we don't need the stack iterator in order to write useful code for a stack:  push(), pop() and top() provide enough functionality to do what we need.

// Demo of STL stack of floats (compare with our custom FloatStack)
#include <iostream>
#include <stack>
using namespace std;

// main method ---------------------------------------
int main()
{
  stack<float> fstk;
  float f;

  fstk.push(1.1);
  fstk.push(2.2);
  fstk.push(3.3);
  fstk.push(4.4);

  for (int k = 0; k < 5; k++)
    if ( !fstk.empty() )
    {
      f = fstk.top();
      fstk.pop();
      cout << f << " ";
    }
    else
      cout << "(empty stack) ";
  cout << endl;

  return 0;
}

/* ----------------- Program Run -------------------

4.4 3.3 2.2 1.1 (empty stack)
Press any key to continue . . .

-------------------------------------------------- */

As you can see, you can save a lot of time by using the STL stack if it has enough functionality to meet your needs.

 The same warning that I gave you about using vectors applies to stacks:  Research and experiment with destructor and constructor calls when creating stack of objects of user-defined classes.

7B.5.3 STL Queues

There is a queue template that also has push(), pop() and back(), however it is a FIFO data structure that causes push() and pop() to happen at the opposite ends of the vector.  In other words push() places elements onto the back of the underlying vector while  pop() removes them from the front.  As with stacks, we need a method that shows us the element that is about to be popped, and for this queue adds the front() method.  A queue template can be instantiated on any class or primitive type and behaves otherwise just like a stack template, with the difference being FIFO rather than LIFO.  You can use the previous example to construct your own queue program.

On a personal note, I don't like the use of the names push() or pop() in reference to queues.  They describe a stack visually and physically, and do not reflect, linguistically, a FIFO data structure.  I prefer add() and remove() or enqueue() and dequeue().  However, those whose job it was to name these methods chose push() and pop(), and unless you want to encapsulate this template in a wrapper of your own, you'll have to use those method names.

7B.5.4 STL Deques

In a sense, the STL vector can do what the STL queue or stack can do and a whole lot more.   For instance, you can use vector's  back(), push_back() and pop_back() as compared with queue's top(), push() and pop(). In addition, you get random access using brackets, [], and at(), you get clear(), you get front() and many others.  However, sometimes we want restricted access to the data in order to preserve the intended data structure.  After all, if the client could remove items from the middle of a stack or queue, it wouldn't be a stack or a queue!

With this in mind, we find that there is utility in data structures that have various extensions and/or restrictions when compared with vectors, stacks or queues.  One popular rest stop on the STL freeway is the deque.  The deque template is a "double-ended queue."  It has most of the functionality of a vector (including random access using [] and at()) with the addition of two methods:  push_front() and pop_front().  When combined with push_back() and pop_back(), this gives us the ability to add items to either the beginning or the end of the vector, making it an alternative when you want to implement a stack or queue but need a little more control that those two templates afford.  Ideally you would not use deque when a stack or queue will do: limited functionality is often better than the expanded power because it will reveal errors at compile time.

Ignoring this advice, we can use a deque to implement the above stack by applying the appropriate methods in place of top(), push() and pop().

// Demo of STL deque that acts like a stack (compare with our STL stack)
#include <iostream>
#include <deque>
using namespace std;

// main method ---------------------------------------
int main()
{
  deque<float> fstk;
  float f;

  fstk.push_back(1.1);
  fstk.push_back(2.2);
  fstk.push_back(3.3);
  fstk.push_back(4.4);

  for (int k = 0; k < 5; k++)
  if ( !fstk.empty() )
  {
    f = fstk.back();
    fstk.pop_back();
    cout << f << " ";
  }
  else
    cout << "(empty stack) ";
  cout << endl;

  return 0;
}

As a novelty, you can change all instances of "back" to "front" in the above code and you have the same stack.  But what is more to the point, you can change some (but not all) of the "back"s to "front"s and you will have changed the stack to a queue.  Can you see how to do that?  As a consequence, some programmers like to use deque for stacks, queues and everything in-between because they only have to memorize the one template.