stack
The
stack,
along with the
queue
and
priority_queue,
are classified as
adapters,
which means they are implemented using one of the basic sequence containers:
vector,
list
or
deque.
This, in my opinion, is an unfortunate case of confusing what something does
with the details of its underlying implementation – the fact that these
are called “adapters” is of primary value only to the creator of
the library. When you use them, you generally don’t care that
they’re adapters, but instead that they solve your problem. Admittedly
there are times when it’s useful to know that you can choose an alternate
implementation or build an adapter from an existing container object, but
that’s generally one level removed from the adapter’s behavior. So,
while you may see it emphasized elsewhere that a particular container is an
adapter, I shall only point out that fact when it’s useful. Note that
each type of adapter has a default container that it’s built upon, and
this default is the most sensible implementation, so in most cases you
won’t need to concern yourself with the underlying implementation.
The
following example shows
stack<string>
implemented in the three possible ways: the default (which uses
deque),
with a
vector
and with a
list:
//: C20:Stack1.cpp
// Demonstrates the STL stack
#include "../require.h"
#include <iostream>
#include <fstream>
#include <stack>
#include <list>
#include <vector>
#include <string>
using namespace std;
// Default: deque<string>:
typedef stack<string> Stack1;
// Use a vector<string>:
typedef stack<string, vector<string> > Stack2;
// Use a list<string>:
typedef stack<string, list<string> > Stack3;
int main(int argc, char* argv[]) {
requireArgs(argc, 1); // File name is argument
ifstream in(argv[1]);
assure(in, argv[1]);
Stack1 textlines; // Try the different versions
// Read file and store lines in the stack:
string line;
while(getline(in, line))
textlines.push(line + "\n");
// Print lines from the stack and pop them:
while(!textlines.empty()) {
cout << textlines.top();
textlines.pop();
}The
top( )
and
pop( )
operations will probably seem non-intuitive if you’ve used other
stack
classes. When you call
pop( )
it returns void rather than the top element that you might have expected. If
you want the top element, you get a reference to it with
top( ).
It turns out this is more efficient, since a traditional
pop( )
would have to return a value rather than a reference, and thus invoke the
copy-constructor. When you’re using a
stack
(or a
priority_queue,
described later) you can efficiently refer to
top( )
as many times as you want, then discard the top element explicitly using
pop( )
(perhaps if some other term than the familiar “pop” had been used,
this would have been a bit clearer).
The
stack
template has a very simple interface, essentially the member functions you see
above. It doesn’t have sophisticated forms of initialization or access,
but if you need that you can use the underlying container that the
stack
is implemented upon. 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 kinds of source-code reformatting):
//: C20:Stack2.cpp
// Converting a list to a stack
#include "../require.h"
#include <iostream>
#include <fstream>
#include <stack>
#include <list>
#include <string>
using namespace std;
// Expects a stack:
template<class Stk>
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(int argc, char* argv[]) {
requireArgs(argc, 1); // File name is argument
ifstream in(argv[1]);
assure(in, argv[1]);
list<Line> 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<Line, list<Line> > 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, 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<Line>,
then a
stack
is wrapped around this list so it can be 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( )
methods, and then you have all the additional functionality of the
vector.
Stack1.cpp
can be rewritten to show this:
//: C20:Stack3.cpp
// Using a vector as a stack; modified Stack1.cpp
#include "../require.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
int main(int argc, char* argv[]) {
requireArgs(argc, 1);
ifstream in(argv[1]);
assure(in, argv[1]);
vector<string> textlines;
string line;
while(getline(in, line))
textlines.push_back(line + "\n");
while(!textlines.empty()) {
cout << textlines.back();
textlines.pop_back();
}You’ll
see this produces the same output as
Stack1.cpp,
but you can now perform
vector
operations as well. Of course,
list
has the additional ability to 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).
Contact: webmaster@codeguru.com
CodeGuru - the website for developers.