Stacks
A "stack" is a data structure which stores items in sequence, providing access at only one end. That is, we add items at the top of the stack, and we remove items from the top of the stack. The items are thus available in reverse order. Stacks are sometimes referred to as a "Last In, First out" (LIFO) or "First In, Last out" (FILO) structure.
The data stored in a stack may be of various kinds: integers, floating-point numbers, etc., or pointers to items stored elsewhere.
It is possible to create a stack class as a "template class" in which we pass in the name of the type of data to be stored. (See the note on "template classes".)
Stack operations
Suppose we have a stack of integers. The operations normally provided for a stack are the following:
Initialize: create a new stack
Dispose: get rid of a stack
Push: insert an int at the top of the stack
Pop: remove an int from the top of the stack
Peek: look at the int at the top of the stack
Empty: returns true if the stack is empty
Full: returns true if the stack is full
Normally, the user will check the Empty function before attempting to use the Pop operation, and likewise check the Full function before attempting to use the Push operation. (If we pop an empty stack or push an item onto a full stack, this is an error.) The user does not need to know how the stack in implemented; he or she simply uses the stack operations.
Optionally, we may also have a counter of the number of items in the stack; the counter would be incremented and decremented as needed by the Push and Pop operations.
A stack may be implemented in various ways: a fixed-size array, a dynamically-sized array, or a linked list. Depending on the choice, some operations may be slower or faster, or may use more or less memory. If we implement the stack as a class, the Initialize and Dispose operations may correspond to the constructor and destructor. If we use a linked list or a dynamically-sized array, the Full function may simply always return false, as we can always enlarge the stack.
Example: A stack of int implemented with a fixed-size array. In this example, the value of Top serves as a counter of the number of items stored in the stack.
Class IntStack
{
private:
static const int SIZE = 100;
int S[SIZE];
int Top;
public:
void Initialize();
void Dispose();
void Push(const int & NewItem);
int Pop();
int Peek() const;
bool Empty() const;
bool Full() const;
};
void IntStack::Initialize()
{
Top = -1;
}
void IntStack::Dispose()
{
Top = -1;
}
void IntStack::Push(const int & NewItem)
{
Top++;
S[Top] = NewItem;
}
int IntStack::Pop()
{
int Temp = S[Top];
Top--;
return Temp;
}
int IntStack::Peek() const
{
return S[Top];
}
bool IntStack::Empty() const
{
return (Top == -1);
}
bool IntStack::Full() const
{
return (Top == 99);
}