Stack

You know what a stack is in real world. We store elements in a stack one on top of another. So, the element on the top, the last one we put on the stack, is directly accessible (First In First Out or FIFO). To take the elements in the middle, we have to take the top elements out first. The stack data structure also has the same functionality.

Stacks are very useful in various applications. The function calling mechanism of a computer program is implemented using a stack. Compilers use a stack to check the correctness of using brackets. Some algorithms such as depth first search in graphs are implemented using stacks.

Stack has 3 major operations, Push, Pop and Peak.

• Push - put an element to the stack.
• Pop - get the topmost element out from the stack.
• Peak - see the value of the top element without removing it from the stack.

Its not hard to implement a stack. We have two options, use an array or use a linked structure to implement a stack. When we use an array for implement the stack, the size of our stack is limited. So, we will implement our stack as a linked structure.

Here is our class for stack.

struct node
{
int value;
node *next;};

class Stack
{
int height;
node *first;
public:
Stack();

//copy constructor
Stack(Stack &lst);

virtual ~Stack();

void Push(int val);

int Pop();

int Peak();

int GetHeight();};

Here is the implementation of the constructor.

Stack::Stack()
{
first=NULL;
height=0;}

We just initialize the variables in the constructor. We store the current height of the stack because then it is easy to identify whether the stack is empty and also, the user of the stack can find out the number of elements in the stack.

In the destructor, we clean up the stack. Because we created our nodes in the heap, we have to free the memory we used.

Stack::~Stack()
{
Empty();}

We just call the method Empty(). Empty method removes all the elements on the stack, freeing the memory allocated for the nodes.

Lets take a look at the function Push().

void Stack::Push(int val)
{
node *tmp=new node;
tmp->value=val;
tmp->next=first;
first=tmp;
height++;}

We create a new node in the heap and put the value we need to push into the stack to the 'value' field of the node. Then, we assign the value of our 'first' (the address of the top element in the stack) to 'next' pointer of our new node so the new node points to the current top element of the stack. Then, we assign the address of the new node to the first pointer, so the new node becomes the top element in the stack.

Here is the Pop function.

int Stack::Pop()
{
int r;
if(height==0)
return -1;
node *tmp;
tmp=first;
r=tmp->value;
first=first->next;
delete tmp;
height--;
return r;
}

First, we check whether the stack is empty because we can't pop element from empty stack. If the stack is empty, the height is zero. We return -1 to indicate the error, but it is not that suitable because the user of the class do not know whether it indicates an error or -1 was the value on the stack. In java, we could throw an exception. In C, we could take a pointer to to the function like Pop(int *error), so we can put some error code to that pointer if stack is empty, without having to indicate the error in return value.

In the function, we use the node pointer 'tmp' and assign the value of the first pointer to it so it also points to the top node of the stack. Then we assign the value of the next pointer of the top node to 'first' pointer. So the first pointer points to the node beneath the top node, so that node become the new top node. We still have the address of the previous top node in 'tmp', so we can delete that node because we do not need that anymore. Before deleting, we store the value stored in that node in a variable, so we can return it.

Peak function is very easy. We just return the value of the node pointed by 'first' pointer.

int Stack::Peak()
{
if(height==0)
return -1;
return first->value;}

In function Empty(), we pop all the elements out of the stack. Because Pop releases the memory assigned for node it pops, when we pop out the whole stack, all the memory assigned for the stack is also released.

void Stack::Empty()
{
for(int i=height; i>0; i--)
Pop();}

It is not mandatory to write a copy constructor, but for completeness, we have written a copy constructor too. The task of the copy constructor is when a stack is passed as an argument to a function, make a copy of the stack to be used in the function. Otherwise, when that function returns, it might destroy the passed stack so the passer cannot use it anymore.

Here is our copy constructor. The signature of a copy constructor of a class is same as the constructor, but it expects a variable in the same class for reference.

Stack::Stack(Stack &lst)
{
first=NULL;
height=0;
int height=lst.GetHeight();
for(int i=0; i
Push(lst.Peak());}

Copy constructor just copies the given stack to a new stack.

Download source code of stack.