Stacks (sstutor)

Stacks and STL

Introduction:

If you have understood the working concept of a linked list, understanding a stack shouldn’t be difficult. Stack is another kind of data structure in which we store data one on top of the other.

An analogy in real life would be a stack of plates (i.e. a set of plates kept one on top of the other). The main feature in such an arrangement is that the last plate to be kept will be at the top of the stack. So, when you want to remove a plate from the arrangement, the last one will be removed first.

This is termed as ‘last-in-first-out’. What goes last comes out first. Similarly you cannot add a plate in between the stack; you can only keep placing plates at the top. The advantage of this kind of arrangement is that you can ensure that everything flows in a proper order (you cannot randomly remove/insert elements in the middle of a stack). The two operations (of adding an element to a stack and removing an element) are called ‘pop’ and ‘push’.

Popping is the process of removing the topmost element from the stack.
Pushing is the process of adding an element to the top of the stack.

Thus it follows that popping will reduce the size occupied by the stack while pushing will increase the size of the stack.

There is a particular area of memory also which is called the ‘stack’. Whenever you create local variables in your functions, these variables get allocated memory in the stack. And this stack memory also follows the same principle of the stack. When variables are created they are pushed into the stack and when the function terminates, all the corresponding variables are popped out of the stack. This concept is used in recursion.

Implementation:

A stack can be implemented using arrays (dynamically allocating the size of the array) or you can make use of linked lists. In fact if the linked list is slightly modified you will get a stack. You will have two functions to pop and push elements on to the stack. Just like we created our own linked list, you can create a stack implementation as well. This is left as an assignment for you to try out.

The STL has a stack template class available in it. The basic two functions needed are pop ( ) and push ( ). There is another function empty ( ) to check whether the stack is empty. Below is a simple program to illustrate the STL stack.

//Program to illustrate the stack container of STL

#include <iostream>
#include <stack>
using namespace std;

int main( )
{
stack<int> intstack;
int i;

//Adding 5 values to the stack (100 101 102 103 104)
for( i=100; i<105; i++ )
{
intstack.push(i);
}

//Displaying the size of the stack
cout<<endl<<"Number of elements in the stack: "<<intstack.size( );

//Popping the elements of the stack till it becomes empty.
//Before popping we display the value of the element which is
// going to be popped

cout<<endl<<endl<<"Popping the elements one by one"<<endl;

for (i=0; !intstack.empty( ); i++)
{
cout<<endl<<intstack.top( );
intstack.pop( );
cout<<endl<<"Size of stack after popping: "<<intstack.size( );
}

return 0;
}

The output will be:

Number of elements in the stack: 5

Popping the elements one by one

104
Size of stack after popping: 4
103
Size of stack after popping: 3
102
Size of stack after popping: 2
101
Size of stack after popping: 1
100
Size of stack after popping: 0

Notice in the output that 104 is the first element to be popped (it was the last element to be pushed into the stack). The member function

size( )

is used to determine the size of the stack (i.e. the number of elements present in the stack).

The function

top( )

can be used to retrieve the value of the last element pushed into the stack (i.e. you can find out the value of the element lying at the top of the stack).

Beware: If you attempt to pop the stack after the stack has become empty, you will get runtime errors. Use the empty ( ) function to check whether the stack is empty or not.

Next page is about Queues

Go back to Contents page 2.