Stacks

A stack is a ADT that is very useful in many applications.  Besides constructors and destructors it normally has the operations(methods) push, pop, top and empty.  You can think of a stack as a collection of plates stacked in a restaurants spring loaded plate holder.  An image of one is shown below.  You can repeated place new plates on the stack(push) or remove them from the top (pop).  Note that you cannot extract the 10 plate from the stack since it is down in the structure hidden from view.  Of course you can just look at the top plate and not remove it (top).  One of the main features of a stack is that it is LIFO (last in first out).  That is , if you pop the stack you will obtain the most recent plate that was placed on the stack.   You can use a stack by writing your own or by using one that is in the Standard Template Library.   Lets look that the STL stack and operate on it. Here is a very simple output.  What does it output?  I haven’t talked about template types.  For now just assume that stack<int> is a stack of int’s and stack<float> is a stack of float’s etc.  In fact you can have a stack<anytype>.  The nice thing about the STL stack is that it can grow very large without worrying about a size limit.

#include <iostream>
#include <stack>
using namespace std;
int main()
{
 int x;
 stack<int> S;
 for (int i = 0; i < 10; i++)
 S.push(i);// push a new int on top of the stack.
while (!S.empty()) {
 x = S.top();//Returns the top of the stack, leaving it there.
S.pop(); // Removes top element and throws it away.
cout << x << " ";
}
cout << endl
 return 0
}

OK, now we know how to use a stack of integers lets build one, ie create a class Stack of integers only (not using templates).  We first need to thing about how we should implement this.  Should we store it in an array, a linked list or some other structure.

ARRAY implementation (has a size limit)

Link_List implementation(has no size limit)

Comments are closed.