Thinking In C++. Volume 2: Practical Programming

The stack template has a simple interface—essentially the member functions you saw earlier. Since it only makes sense to access a stack at its top, no iterators are available for traversing it. Nor are there sophisticated forms of initialization, but if you need that, you can use the underlying container upon which the stack is implemented. For example, suppose you have a function that expects a stack interface, but in the rest of your program you need the objects stored in a list. The following program stores each line of a file along with the leading number of spaces in that line. (You might imagine it as a starting point for performing some kind of source-code reformatting.)

//: C07:Stack2.cpp

// Converting a list to a stack

#include

#include

#include

#include

#include

using namespace std;

// Expects a stack:

template

void stackOut(Stk& s, ostream& os = cout) {

  while(!s.empty()) {

    os << s.top() << "\n";

    s.pop();

  }

}

class Line {

  string line; // Without leading spaces

  int lspaces; // Number of leading spaces

public:

  Line(string s) : line(s) {

    lspaces = line.find_first_not_of(' ');

    if(lspaces == string::npos)

      lspaces = 0;

    line = line.substr(lspaces);

  }

  friend ostream&

  operator<<(ostream& os, const Line& l) {

    for(int i = 0; i < l.lspaces; i++)

      os << ' ';

    return os << l.line;

  }

  // Other functions here...

};

int main() {

  ifstream in("Stack2.cpp");

  list lines;

  // Read file and store lines in the list:

  string s;

  while(getline(in, s))

    lines.push_front(s);

  // Turn the list into a stack for printing:

  stack > stk(lines);

  stackOut(stk);

} ///:~

The function that requires the stack interface just sends each top( ) object to an ostream and then removes it by calling pop( ). The Line class determines the number of leading spaces and then stores the contents of the line without the leading spaces. The ostream operator<< re-inserts the leading spaces so the line prints properly, but you can easily change the number of spaces by changing the value of lspaces. (The member functions to do this are not shown here.)

In main( ), the input file is read into a list, and then each line in the list is copied into a stack that is sent to stackOut( ).

You cannot iterate through a stack; this emphasizes that you only want to perform stack operations when you create a stack. You can get equivalent "stack" functionality using a vector and its back( ), push_back( ), and pop_back( ) member functions, and then you have all the additional functionality of the vector. Stack1.cpp can be rewritten to show this:

//: C07:Stack3.cpp

// Using a vector as a stack; modified Stack1.cpp

#include

#include

#include

#include

using namespace std;

int main() {

  ifstream in("Stack3.cpp");

  vector textlines;

  string line;

  while(getline(in, line))

    textlines.push_back(line + "\n");

  while(!textlines.empty()) {

    cout << textlines.back();

    textlines.pop_back();

  }

} ///:~

This produces the same output as Stack1.cpp, but you can now perform vector operations as well. Of course, list can also push things at the front, but it’s generally less efficient than using push_back( ) with vector. (In addition, deque is usually more efficient than list for pushing things at the front.)

queue

The queue is a restricted form of a deque—you can only enter elements at one end and pull them off the other end. Functionally, you could use a deque anywhere you need a queue, and you would then also have the additional functionality of the deque. The only reason you need to use a queue rather than a deque, then, is if you want to emphasize that you will only be performing queue-like behavior.

The queue is an adapter class like stack, in that it is built on top of another sequence container. As you might guess, the ideal implementation for a queue is a deque, and that is the default template argument for the queue; you’ll rarely need a different implementation.

Queues are often used when modeling systems in which some elements of the system are waiting to be served by other elements in the system. A classic example of this is the "bank-teller problem": customers arrive at random intervals, get into a line, and then are served by a set of tellers. Since the customers arrive randomly and each takes a random amount of time to be served, there’s no way to deterministically know how long the line will be at any time. However, it’s possible to simulate the situation and see what happens.

In a realistic simulation each customer and teller should be run by a separate thread. What we’d like is a multithreaded environment so that each customer or teller would have their own thread. However, Standard C++ has no model for multithreading, so there is no standard solution to this problem. On the other hand, with a little adjustment to the code, it’s possible to simulate enough multithreading to provide a satisfactory solution.[99]