20. Stacks¶
20.1. Abstract data types¶
The data types we have looked at so far are all concrete, in the sense that we
have completely specified how they are implemented. For example, the Card
class represents a card using two integers. As we discussed in the
Card objects section, there are alternative implementations, one of
which we explored in Enumerated types.
An abstract data type, or ADT, specifies a set of operations (or functions) and the semantics of the operations (what they do), but it does not specify the implementations of the operations.
Why is that useful?
It simplifies the task of specifying an algorithm if you can denote the operations you need without having to think at the same time about how the operations are performed.
Since there are usually many ways to implement an ADT, it might be useful to write an algorithm that can be used with any of the possible implementations.
Well-known ADTs, like the Stack ADT in this chapter, are often implemented in standard libriaries so they can be written once and used by many programmers.
The operations on ADTs provide a common high-level language for specifying and talking about algorithms.
When we talk about ADTs, we often distinguish the code that uses the ADT, called the client code, from the code that implements the ADT, called provider code because it provides a standard set of services. The collection of classes and functions through which the client code accesses the provider codes is called the application programming interface (API).
20.2. The Stack ADT¶
In this chapter we will look at one common ADT, the stack. A stack is a collection. Other collections we have seen include vectors and lists.
An ADT is defined by the operations you can perform on it. Stacks can perform only the following operations:
- new
Create a new, empty stack.
- push
Add a new item to the stack.
- pop
Remove and return an item from the stack. The item that is returned is always the last one that was added.
- top
Return the value at the top of the stack without removing it.
- empty
Check whether the stack is empty.
A stack is sometimes called a “last in, first out,” or LIFO data structure, because the last item added is the first to be removed.
Stacks have numerous uses in computer science, including in the run-time stack used by operating systems to manage function calls.
20.3. Implemeting stacks with linked lists¶
We will look at a few different implementations of the stack ADT, beginning with one that we have already written, without even knowing it.
Take a look back at the LinkedList class we wrote in the previous chapter,
then look at the operations defined for the stack ADT. If it occurs to you
that the push operation looks a lot like what the insert_at_front function
does, and pop similarly looks like remove_from_front, then you are doing
well. In fact, with just a little tweaking, our LinkedList class could
perform all the functions want from stacks.
How should we do this “tweaking”? We could just write a new Stack class,
burrowing most of the logic we used to create LinkLists and rewriting it,
but this would violate the DRY principle that we introduced in
Wrappers, helpers, and function pointers. So instead, we’ll make take advantage of
another core feature of object-oriented programming languages: inheritance.
20.4. Inheritance¶
Inheritance is the ability to define a new class that is a modified version of a previously defined class (including a built-in class). The primary advantage of this feature is that you can add new functions or instance variables to an existing class without modifying the existing class. It allows you to reuse of the code in the existing class without having to repeat it. This is particularly useful for built-in classes, since you can’t modify them even if you want to.
The reason inheritance is called “inheritance” is that the new class inherits all the instance variables and functions of the exisiting class. Extending this metaphor, the exisiting class is sometimes called the parent class and the derived class called the child class.
Note
Another common pair of terms for the classes in the inheritance relationship is superclass and subclass.
Our desire to implement the stack ADT utilizing our existing LinkedList
class provides a nice opportunity to use inheritance. Here is the entire
source code for a stack class that inherits from LinkedList residing
in a file named Stack.h:
#include <iostream>
#define MAX_SIZE 128
using namespace std;
template <class T>
class Stack
{
int top_item;
T items[MAX_SIZE];
public:
// constructors
Stack() {
top_item = -1;
}
// modifiers
void push(T item) {
items[top_item++] = item;
}
T pop() {
if (top_item == -1)
throw runtime_error("Can't pop from empty stack!");
return items[top_item--];
}
bool empty() const {
return top_item == -1;
}
T top() {
if (top_item == -1)
throw runtime_error("Can't return top item of empty stack!");
return items[top_item];
}
};
To use it, you need to have the LinkedList.h file provided in
Appendix A: Code Source in the same location as Stack.h.
The two lines:
template <class T>
class Stack : public LinkedList<T>
specify that we are creating a templated class named Stack that is a
child class of LinkedList<T>. The keyword public specifies that
our derived class will have access to all the instance variables and
member functions of its parent class.
Note
We have been making all our classes public. Be forewarned that you may
be told by more experienced C++ programmers that this is unsafe and a bad
practice. C++ supports access specifiers to provide controlled
access from one part of the code to another. Implementing access control is
cumbersome and would have greatly complicated both our code examples and
their explainations. Since our goal is to present “big ideas” here as
assessibly as possible, we intentionally avoided getting stuck “in the
weeds” with this topic. If your intention is to become a C++ programer,
you will definitely need to learn all about it.
Stack() = default;
gives us a default constructor for our Stack class. Calling this
constructor will also call the default constructor of its parent class,
creating a list with instance variables num_nodes and head.
Modifier member functions push and pop just call insert_at_front
and remove_from_front respectively, giving their already implemented
functionality our new stack API.
The LinkedList class doesn’t have an exact equivalent of a Boolean
empty function, but it does have the accessor function length. A stack
is empty when the length of its list of items is 0.
Here is a small program in a file named test_stack.cpp that we can use to
test our Stack implementation:
#include <iostream>
#include "Stack.h"
using namespace std;
int main()
{
Stack<int>* stack = new Stack<int>();
cout << "Calling stack->empty() gives: " << stack->empty() << endl;
for (int i = 1; i <= 5; i++) {
cout << "Pushing " << i * i << "..." << endl;
stack->push(i * i);
}
cout << "Calling stack->empty() now gives: " << stack->empty() << endl;
cout << "The top of the stack contains: " << stack->top() << endl;
while (stack->empty() == false) {
cout << "Popping " << stack->pop() << "..." << endl;
}
cout << "Calling stack->empty() after while loop gives: ";
cout << stack->empty() << endl;
return 0;
}
20.5. Exceptions¶
The last of our stack API functions, top, presents us with a problem similar
to the one we saw in Preconditions. This function should only be called
on a non-empty stack. In fact, non-emptiness could be considered a
precondition for top. So what should happen when we try to call top
on an empty stack?
The top function is defined to return a value of type T. It’s not at
all clear what top should do with an empty stack, and if we don’t do
anything to handle the problem, trying to access the cargo attribute of
a NULL pointer to a Node will result in a runtime error. As we
mentioned way back in Runtime errors, these are also called
exceptions, and C++ has
a standard way of handling them.
The three keywords C++ uses to handle exceptions are try, catch, and
throw. The way to handle code which could cause an exception to occur is
to put the code in a try-block and then to write exception-handlers which
are declared with the keyword catch.
To do this for our top function, we would write something like this:
T top() {
try {
if (LinkedList<T>::head == NULL)
throw runtime_error("Can't return top item of empty stack!");
return LinkedList<T>::head->cargo;
}
catch (exception& e) {
// Do something sensible here to handle the exception
}
}
Since catch would have to return a value of type T, and since it is not
at all clear how to do that, we will instead keep our previous verstion of
top that calls throw after checking if head is NULL. Calling
top on an empty stack will still cause the program to crash, but at least
it will report the helpful measage, “Can’t return top item of empty stack!”, as
it crashes.
20.6. Postfix expressions¶
In most programming languages, mathematical expressions are written with the operator between the two operands, as in \(1 + 2\). This format is called infix. An alternative format used by some scientific calculators is called postfix. In postfix, the operator follows the operands, as in \(1\;2\;+\).
One advantage of postfix over infix is that it eliminates the need for parenthesis in expressions like \((4 + 5) * 3\), since the postfix expression for this is unambiguously written as \(4\;5 + 3\;*\).
Another advantage of postfix for programmers (and calculator designers) is that there is a natural way to evaluate a postfix expression using a stack.
Starting at the beginning of the expression, get one term (operator or operand) at a time.
If the term is an operand, push it on the stack.
If the term is an operator, pop two operands off the stack, perform the operation on them, and push the result back on the stack.
When we get to the end of the expression, there should be exactly one operand on the stack. That operand is the result.
20.7. Parsing¶
In order to implement the algorithm from the previous section, we need to be able to traverse a string and break it into operands and operators. This process is an example of parsing.
20.8. Implementing APIs¶
One of the fundamental goals of an API is to separate the interests of the provider, who writes the code that implements the API, and the client, who uses the API. The provider only has to worry about whether the implementation is correct – that calls made using the API will do what they are supposed to do – not about how it will be used.
Conversely, the client assumes that the implementation works as specified and doesn’t worry about the details. When you use C++’s standard library, you have the luxury of thinking exclusively as a client.
When you implement an API, on the other hand, you also have to write the client code to test it. In that case, you sometimes have to think carefully about which role you are playing at a given time.
In the next few sections we will switch gears and look at another way of implementing the Stack ADT using a vector.
20.9. Array implementation of the Stack ADT¶
Our stack data for this implementation will be stored in the simple C style array which we were introduced to in the Arrays section of the Pointers and arrays chapter.
#include <iostream>
#define MAX_SIZE 128
using namespace std;
template <class T>
class Stack
{
int top_item;
T items[MAX_SIZE];
public:
// constructors
Stack() {
top_item = -1;
}
// modifiers
void push(T item) {
items[top_item++] = item;
}
T pop() {
if (top_item == -1)
throw runtime_error("Can't pop from empty stack!");
return items[top_item--];
}
bool empty() const {
return top_item == -1;
}
T top() {
if (top_item == -1)
throw runtime_error("Can't return top item of empty stack!");
return items[top_item];
}
};
The second line uses the preprocessor directive #define to define a
constant value (128 in this case) named MAX_SIZE. The preprocessor will
replace all occurances of MAX_SIZE with the literal value 128 before
the code is compiled.
20.10. The stack in the standard template library¶
A standard library is a collection of programming resources (pre-defined constants, functions, classes, etc.) that can be treated by programmers as part of the language, since they come “standard” with it.
We have been using the C++ standard library since the first chapter of this
book, since every time we write #include <iostream> and use cout we
are using the standard library.
20.11. Glossary¶
- abstract data type (ADT)¶
A data type (usually a collection of objects) that is defined by a set of operations, but that can be implemented in a variety of ways.
- client¶
A program that uses an ADT (or the person who wrote the program).
- provider¶
The code that implements an ADT (or the person who wrote it).
- application programming interface (API)¶
The classes and functions through which an interface is provided from one piece of software, the provider, to another piece of software, the client.
- infix¶
A way of writing mathematical expressions with the operators between the operands.
- postfix¶
A way of writing mathematical expressions with the operators after the operands.
- delimiter¶
A character that is used to separate tokens, like the punctuation in a natural language.