Return
to Course Outline
Chapter Seven
Stacks
-
Click here to see an example of push
and pop in a stack
-
The behavior of a stack
-
a list of items that are accessible
at only one end of the list.
-
items are added (PUSH)
or deletd (POP) from the list only
at the top of the stack.
-
last in first out (LIFO)
-
The STL stack container is an adapter
class, because it uses either
a vector, deque,
or list to implement the behavior of
a stack.
-
Since we do not use a stack to insert or delete any item
at any position other than top,
there is little benifit using a list to store the stack's
elements.
-
The deque manages memory more efficiently than a vector.
-
Write your own stack class and click
here to see the description.
-
class miniStack
-
Use a vector object maintains
the stack items and size.
-
Be able to push an item to the
top, pop the item from the top,
reference the top element,
check it empty or not and maintain the size
of the stack.
-
miniStack();
// constructor. create an empty stack
-
void push(const
T& item);
-
void pop();
-
T& top();
-
const T& top()
const;
-
bool empty()
const;
-
int size()
const;
-
Call vector's operators to define stack's operators. (back
<--->
top)
For example,
template <typename
T>
void miniStack<T>::push(const
T& item)
{
stackVector.push_back(item);
}
-
Click here to see the code of class
miniStack.
-
Infix and Postfix Notations for Expression
Evaluation
-
Example of evaluating a postfix
expression
- Example of converting infix to
postfix
- Example of stack
-
Applications for stacks in a computer program: