Stack.h

Classes

Stack -- A Last-In-First-Out (LIFO) data structure. (full description)

template<class elem> class Stack

Interface

Public Members

Stack() : topOfStack(0)

Stack(const Stack<elem> &other)

Stack<elem> &operator=(const Stack<elem> &other)

~Stack()

void push(const elem &e)

void pop()

elem popVal()

elem &top()

const elem &top() const

Bool empty() const

Description

This class, Stack, defines an implementation of a stack using the doubly linked list primitive, Link. It has the standard push and pop operations.

Review Status

Reviewed By:

Gareth Hunt

Date Reviewed:

94Jan06

Programs:

Tests:

tQueue

Synopsis

A Stack as implemented here is a simple container which can grow with time, and which returns its elements (only) in the inverse order which they are inserted. That is, the fundamental operations are to push (add) an element onto the top of the stack and to pop (remove) an element from the top of the stack. As a result, the last element placed on the stack will be the first element removed.

Example

     Stack<int> one,two;
     int count = 0;
     one.push(1);                       // add
     one.push(2);                       // add
     one.push(3);                       // add
     one.push(4);                       // add
     while ( !one.empty() ) {
         cout << one.top() << " ";      // top element
         two.push(one.top());           // push = add
         one.pop();                     // remove top element
     }
     cout << endl;
     while ( !two.empty() ) {
         one.push(two.top());
         cout << two.popVal() << " ";   // remove and return top
     }
     while ( !one.empty() )
         count += one.popVal();
     cout << endl << count << endl;;

This results in the following output:

         4 3 2 1 
         1 2 3 4 
         10

Example

Presently, this implementation is rather simple. It is built directly upon the Link class.

Motivation

A simple stack was needed for the (now deprecated) CanDelete class.

To Do

It is conceivable that an iterator might be useful for this class.
If this class is ever heavily used, a more space efficient implementation may be necessary.

Member Description

Stack() : topOfStack(0)

This creates an empty stack.

Stack(const Stack<elem> &other)

Create a stack by making a copy of other.

Stack<elem> &operator=(const Stack<elem> &other)

Create a stack which is a copy of other.

~Stack()

void push(const elem &e)

Add an element to the top of the stack.

void pop()

Remove the top element from the top of the stack.

elem popVal()

Remove the top element from the top of the stack, and return it

elem &top()
const elem &top() const

Retreive the top element on the stack.

Bool empty() const

Check to see if the stack is empty.