Class stack (from header <stack>) enables insertions into and deletions from the underlying container at one end called the top, so a stack is commonly referred to as a last-in, first-out data structure. We introduced stacks in our discussion of the function-call stack in Section 6.11. A stack
can be implemented with vector
, list
or deque
. This example creates three integer stacks, using vector
, list
and deque
as the underlying data structure to represent the stack
. By default, a stack
is implemented with a deque
. The stack
operations are push
to insert an element at the top of the stack
(implemented by calling function push_back
of the underlying container), pop
to remove the top element of the stack
(implemented by calling function pop_back
of the underlying container), top to get a reference to the top element of the stack
(implemented by calling function back
of the underlying container), empty
to determine whether the stack
is empty (implemented by calling function empty
of the underlying container) and size
to get the number of elements in the stack
(implemented by calling function size
of the underlying container).
Figure 15.19 demonstrates the stack
adapter class. Lines 18, 21 and 24 instantiate three integer stacks. Line 18 specifies a stack
of integers that uses the default deque
container as its underlying data structure. Line 21 specifies a stack
of integers that uses a vector
of integers as its underlying data structure. Line 24 specifies a stack
of integers that uses a list
of integers as its underlying data structure.
1 // Fig. 15.19: fig15_19.cpp
2 // Standard Library stack adapter class.
3 #include <iostream>
4 #include <stack> // stack adapter definition
5 #include <vector> // vector class-template definition
6 #include <list> // list class-template definition
7 using namespace std;
8
9 // pushElements function-template prototype
10 template< typename T > void pushElements( T &stackRef );
11
12 // popElements function-template prototype
13 template< typename T > void popElements( T &stackRef );
14
15 int main()
16 {
17 // stack with default underlying deque
18 stack< int > intDequeStack;
19
20 // stack with underlying vector
21 stack< int, vector< int > > intVectorStack;
22
23 // stack with underlying list
24 stack< int, list< int > > intListStack;
25
26 // push the values 0-9 onto each stack
27 cout << "Pushing onto intDequeStack: ";
28 pushElements( intDequeStack );
29 cout << "
Pushing onto intVectorStack: ";
30 pushElements( intVectorStack );
31 cout << "
Pushing onto intListStack: ";
32 pushElements( intListStack );
33 cout << endl << endl;
34
35 // display and remove elements from each stack
36 cout << "Popping from intDequeStack: ";
37 popElements( intDequeStack );
38 cout << "
Popping from intVectorStack: ";
39 popElements( intVectorStack );
40 cout << "
Popping from intListStack: ";
41 popElements( intListStack );
42 cout << endl;
43 } // end main
44
45 // push elements onto stack object to which stackRef refers
46 template< typename T > void pushElements( T &stackRef )
47 {
48 for ( int i = 0; i < 10; ++i )
49 {
50 stackRef.push( i ); // push element onto stack
51 cout << stackRef.top() << ' '; // view (and display) top element
52 } // end for
53 } // end function pushElements
54
55 // pop elements from stack object to which stackRef refers
56 template< typename T > void popElements( T &stackRef )
57 {
58 while ( !stackRef.empty() )
59 {
60 cout << stackRef.top() << ' '; // view (and display) top element
61 stackRef.pop(); // remove top element
62 } // end while
63 } // end function popElements
Pushing onto intDequeStack: 0 1 2 3 4 5 6 7 8 9
Pushing onto intVectorStack: 0 1 2 3 4 5 6 7 8 9
Pushing onto intListStack: 0 1 2 3 4 5 6 7 8 9
Popping from intDequeStack: 9 8 7 6 5 4 3 2 1 0
Popping from intVectorStack: 9 8 7 6 5 4 3 2 1 0
Popping from intListStack: 9 8 7 6 5 4 3 2 1 0
Function pushElements
(lines 46–53) pushes the elements onto each stack
. Line 50 uses function push
(available in each adapter class) to place an integer on top of the stack
. Line 51 uses stack
function top
to retrieve the top element of the stack
for output. Function top does not remove the top element.
Function popElements
(lines 56–63) pops the elements off each stack
. Line 60 uses stack
function top
to retrieve the top element of the stack
for output. Line 61 uses function pop
(available in each adapter class) to remove the top element of the stack
. Function pop
does not return a value.
3.145.86.183