Stack Class and Applications

The Stack ADT

A stack can be defined as a data structure which only permits operations at one end of the storage container, which we'll call the top. Think of this like a can of those terribly delicious Pringles® potato chips such that, short of destroying the can, we can only access (eat) the top chip in the container; access to each subsequent chip requires the removal of the chip preceding it. We can easily imagine how the chips were inserted into the can, starting with the first chip (the one at the bottom) and continually adding chips until the can is full. It turns out that the last chip to be added to the can is actually the first chip to be removed (eaten).

In this way, a Pringles can (our veritable stack) is a Last-in/First-Out (LIFO) data structure, more formally defined as a data structure where elements are removed in the reverse order of their addition.

Basic Stack operations

A traditional stack supports three operations: push (adds an item to the top), pop (removes an item from the top), and isEmpty (checks to see if the data structure contains any items). There exists a more modern variation of the traditional stack that adds a size method (which returns the number of items in the stack) and splits the pop operation into two parts. We show the differences further down the page.

In the end, either the traditional or modern version will serve your needs and either is acceptable to use.

Solving problems with stacks: Reversing input

You use a stack to solve a problem when storing data last-in/first-out is what you need. Once you've made the decision to use a stack (i.e. to use last-in/first-out) it simplifies problem solving, because you simply think push to store and pop to retrieve ... there are no other decisions to make.

Consider the problem of reading in a line of characters characters and printing them in reverse order. "Reverse order" means that the last character read in is the first character you print out. So when you read a character you'll store it, when you're ready to write, you'll retrieve a character and write it, and this should happen in LIFO order. That means we can abstract the issue of storing and retrieving data to a stack for this problem. Here's our simple pseudocode:

While there are characters left to read
  Read a character
  Push the character onto the stack
While there are characters left on the stack
  Pop a character from the stack
  Print the character to the screen

So, for example, suppose we followed this procedure with the input HOT. The figure below illustrates what would happen with the stack, and hopefully shows you why the word ends up getting reversed.

READ-IN:           H              O              T

                   |              |              |       T
                   |              |      O       |       O             O
                   v      H       v      H       v       H             H             H
STACK:    ---    push    ---    push    ---    push     ---    pop    ---    pop    ---    pop    ---
           S              S              S               S      |      S      |      S      |      S
                                                                |             |             |
                                                                v             v             v

WRITE-OUT:                                                      T             O             H
 

Now, realizing this in C++ requires a bit more understanding. What kind of object is the stack? How do we push and pop and check whether the stack is empty?

A stack class you can use

Provided below is a generic class Stack to use. By 'generic', I mean that it's not known in advance what kind of objects you're going to store in your stack. In the previous example it was characters. In lab it'll be doubles. In other contexts it'll be strings, or points, or who knows what. To deal with this, the below example is a special kind of class that is independent of the type of objects it contains. When you declare a variable of type Stack, you'll put the type being stored in the stack, in angle brackets, immediately following the word Stack. For example, to declare a stack named S for storing chars, you'd type:

Stack<char> S;

To declare a stack named G for storing string objects you'd write

Stack<string> G;

instead. So, we have one class for any and every kind of stack, rather than needing a separate class for each type you want to store in a stack. Don't worry for now about how this feature is implemented, we'll see later in the course! The links below give you the .h files that contain both the interface and implementation for this special stack class. There are two different flavors, one that is more modern, and one that's more traditional. In addition to the .h files, shown below are the public member functions of the class and a simple program (a solution to the reversing problem from above) using the class.

  Stack();
  ~Stack();
  bool isEmpty() const;
  int size() const;
  void push(const DataType &newItem);
  void pop();
  DataType getTop() const;

  Stack();
  ~Stack();
  bool isEmpty() const;
  void push(const DataType &newItem);
  DataType pop();      

#include "Stack.h"
#include <iostream>
using namespace std;

int main() {
  // Read and store characters
  Stack<char> S;
  for(char c = cin.get(); c != '\n' ; c = cin.get())
    S.push(c);

  // Print out characters in stack
  while(!S.isEmpty())  {
    cout << S.getTop();
    S.pop();
  }
  cout << endl;

  return 0;
}

#include "TradStack.h"
#include <iostream>
using namespace std;

int main() {
  // Read and store characters
  Stack<char> S;
  for(char c = cin.get(); c != '\n' ; c = cin.get())
    S.push(c);

  // Print out characters in stack
  while(!S.isEmpty())
    cout << S.pop();
  cout << endl;

  return 0;
}

Checking for balanced ( )'s

Suppose we want to read a line of characters that contains ( )'s, and we want to determine whether the ( )'s are balanced, i.e. each ( is closed of by exactly one ), and each ) closes off exactly one (. We can do this easily by keeping a stack of unmatched ('s. Whenever we encounter a ), we pop the top off the stack, because that ( has been matched. Here's the procedure in pseudocode:

Pseudocode:

Create a stack of characters
Create a flag fail and set it to false
While fail is false and there's input left to read
  Read a character c
  If c is a (, push it onto the stack
  Else if c is a ) and stack is empty, set fail to true
  Else if c is a ), pop one element off the stack
If fail is true, or the stack isn't empty, print "unbalanced"
Else, print "balanced"

C++ implementation:

#include "Stack.h"
#include <iostream>
using namespace std;

int main() {
  // Read line
  Stack<char> S;
  bool fail = false;
  for(char c = cin.get(); !fail && c != '\n' ; c = cin.get())
    if (c == '(')
      S.push(c);
    else if (c == ')' && S.isEmpty())
      fail = true;
    else if (c == ')')
      S.pop();

  // Print result
  if (fail || !S.isEmpty())
    cout << "unbalanced" << endl;
  else
    cout << "balanced" << endl;

  return 0;
}

#include "TradStack.h"
#include <iostream>
using namespace std;

int main() {
  // Read line
  Stack<char> S;
  bool fail = false;
  for(char c = cin.get(); !fail && c != '\n' ; c = cin.get())
    if (c == '(')
      S.push(c);
    else if (c == ')' && S.isEmpty())
      fail = true;
    else if (c == ')')
      S.pop();

  // Print result
  if (fail || !S.isEmpty())
    cout << "unbalanced" << endl;
  else
    cout << "balanced" << endl;

  return 0;
}

Note that the source code for this example is identical in each case. This is not by coincidence! It is proof that for this problem (and indeed all problems) utilizing a stack, the three basic operations (push, pop, isEmpty) will suffice. Other operations are nice to have and may result in faster run times in some situations, but often simple is best!

Checking for balanced ( )'s, [ ]'s and { }'s

One might object that a simple counter can be used in place of the stack in the previous example. This is true, but what if we allow different kinds of open/close pairs, like ( )'s, [ ]'s and { }'s, and we insist that the open and closing pairs need to match. So while

[ [ { } ] ( ) { [ ] } ]

is okay,

[ { } ( } ]

is not. Now the problem is more interesting. A simple counter won't suffice. However, it's easy to modify the above procedure using stacks to solve this more difficult problem!

Pseudocode:

Create a stack of characters
Create a flag fail and set it to false
While fail is false and there's input left to read
  Read a character c
  If c is a (, { or [ push it onto the stack
  Else if c is a ), } or ] and stack is empty, set fail to true
  Else
    Pop one element off the stack
    Set fail to true if the closing character you popped off doesn't match c
If fail is true, or the stack isn't empty, print "unbalanced"
Else, print "balanced"

C++ implementation:

#include "Stack.h"
#include <iostream>
using namespace std;

int main() {
  // Read line
  Stack<char> S;
  bool fail = false;
  for(char c = cin.get(); !fail && c != '\n' ; c = cin.get()) {
    if (c == '(' || c == '{' || c == '[')
      S.push(c);
    else if (c == ')' || c == '}' || c == ']') {
      if (S.isEmpty())
        fail = true;
      else {
        char t = S.getTop();
        S.pop();
        fail =
          t == '(' && c != ')' ||
          t == '[' && c != ']' ||
          t == '{' && c != '}';
      }
    }
  }
  // Print result
  if (fail || !S.isEmpty())
    cout << "unbalanced" << endl;
  else
    cout << "balanced" << endl;

  return 0;
}

#include "TradStack.h"
#include <iostream>
using namespace std;

int main() {
  // Read line
  Stack<char> S;
  bool fail = false;
  for(char c = cin.get(); !fail && c != '\n' ; c = cin.get()) {
    if (c == '(' || c == '{' || c == '[')
      S.push(c);
    else if (c == ')' || c == '}' || c == ']') {
      if (S.isEmpty())
        fail = true;
      else {
        char t = S.pop();
        fail =
          t == '(' && c != ')' ||
          t == '[' && c != ']' ||
          t == '{' && c != '}';
      }
    }
  }
  // Print result
  if (fail || !S.isEmpty())
    cout << "unbalanced" << endl;
  else
    cout << "balanced" << endl;

  return 0;
}

Again, outside of the split of the pop operation in Stack.h, the above codes are identical. This week's lab will give you some hands-on experience working with stacks.