3.5. Using a Stack in C++ΒΆ

Now that we have clearly defined the stack as an abstract data type we will turn our attention to using a stack 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 stack is the creation of a new class. The stack operations are implemented as methods. However, the STL already has a well written implementation of the Stack class.

The following stack implementation (ActiveCode 1) assumes that the end of the list will hold the top element of the stack. As the stack grows (as push operations occur), new items will be added on the end of the list. pop operations will manipulate that same end.

Self Check

    Q-1: Given the following sequence of stack operations, what is the top item on the stack when the sequence is complete?

    stack<int> m;
    m.push(5);
    m.push(12);
    m.pop();
    m.push(27);
    cout << m.top();
    
  • 5
  • Remember that a stack is built from the bottom up.
  • 12
  • Remember that a stack is built from the bottom up.
  • 27
  • Good job.
  • The stack is empty
  • Remember that a stack is built from the bottom up.

    Q-2: Given the following sequence of stack operations, what is the top item on the stack when the sequence is complete?

    stack<int> m;
    m.push(37);
    m.push(56);
    m.push(4);
    while (!m.empty()){
        m.pop();
        m.pop();
    }
    
  • 37
  • You may want to check out the docs for
  • the stack is empty
  • There is an odd number of things on the stack but each time through the loop 2 things are popped.
  • an error will occur
  • Good Job.
  • 4
  • You may want to check out the docs for isEmpty
Next Section - 3.6. Simple Balanced Parentheses