Stack in C++

Filed Under: C++
Stack In C Programming

Introduction

A stack is a linear data structure in C++. It serves as a collection of data, arranged serially in a specific order. In a stack in C++, two of the basic stack operations are push and pop. Further, all of the operations on a stack are performed at one end.

Also, a stack follows LIFO(Last In, First Out) fashion. And hence the last data element inserted is deleted or popped out first. So now let us dig deeper into the topic to have a clear understanding of the same.

Working of Stack in C++

One can imagine a stack as if they’re blocks. You place one block on top of another and can continue to remove the top block which is the one you inserted last. Stack also works in a similar pattern. The latest data is stored at the top of the stack and when popping out, returns the top-most element.

Now let us look at the basic operations that can be performed on a stack,

  • push()
  • pop()
  • peek()

We are going to discuss each operation one-by-one below.

1. push() on Stack

Considering our previous example of blocks a push is an operation where we add a new block over the previous set.

In stack, push() inserts a data element on the top of the previously pushed data. Let us have a look at the algorithm for pushing data.

Procedure PUSH(VALUE)
    If TOP==Size_of_Stack
        Write OVERFLOW
    else
        TOP=TOP+1
        STACK[TOP]=VALUE
END of Procedure

2. pop() from Stack

Similarly, considering our previous example, pop() is the operation where the top-most block is removed from the stack of blocks. Hence, pop removes and returns the element present at the top of the given Stack.

Algorithm for pop() function can be given by:

Procedure POP()
    If TOP==-1
        Write UNDERFLOW
    else
        TOP=TOP-1
        RETURN STACK[TOP+1]
END of Procedure

3. peek() from Stack

The peek operation is similar to the pop operation in terms that it returns the topmost element from a stack. But the peek() operation does not delete the element, only returns it.

Hence, the algorithm for peek() function in Stack is given by:

Procedure PEEK()
    If TOP==-1
        Write UNDERFLOW
    else
        Print STACK[TOP]
END of Procedure

Time Complexity For Stack Operations

Noteworthy, in the worst-case scenario, the time complexity of any stack operation is constant and is given by O(1).

Implementing Stack in C++

#include<iostream>
using namespace std;
#define max 10                

int stack[max],top=-1;           //stack declaration

void push(int num)         //push() inserts n element into the Stack
{
	if(top==max)    //checks is Stack if Full
	{
		cout<<"OVERFLOW!";
	}
	else
	{
		top=top+1;             //top is increased
		stack[top]=num;        //element is inserted
	}
} 
int pop()               //pop() pops out the top-most element from the Stack
{
	if(top==-1)      //Checks if Stack is empty
	{
		cout<<"UNDERFLOW!";
	}
	else
	{
		top=top-1;
		return stack[top+1];  //top-most element popped and returned to the main function
	}
}
int peek()
{
	if(top==-1)      //Checks if Stack is empty
	{
		cout<<"UNDERFLOW!";
	}
	else
	{
		return stack[top];     //top-most element is returned to main()
	}
}
void show()
{
	int i=0;
	if(top==-1)    //Check if stack is empty
	{
		cout<<"UNDERFLOW!";
	}
	else if(top==max)     //Check if stack is full
	{
		cout<<"OVERFLOW!";
	}
	else
	{
		while(i<=top)    //printing the current stack elements
		{
			cout<<"\t"<<stack[i];
			i++;
		}
		cout<<endl;
	}
}
int main() 
{ 
    int ch,val;
    cout<<"   :::MENU:::";       //Menu for Stack operations
    cout<<"\n1.Push into the Stack\n2.Pop from Stack\n";
    cout<<"3.Peek from Stack\n4.Show the Stack\n5.Exit";
    while(1)    
    {
        printf("\nEnter the choice:");
        scanf("%d",&ch);
         
        switch(ch)
        {
            case 1: cout<<"Enter the value to be pushed: ";
            		cin>>val;
            		push(val);
                    break;
            case 2: cout<<"The popped element is : "<<pop()<<endl;
                    break;
            case 3: cout<<"The top-most element is : "<<peek()<<endl;
            		break;
            case 4: cout<<"Stack : ";
					show();
                    break;
            case 5: exit(0);
             
            default: printf("\nError! Invalid choice!...");
        }
    }
    return 0;
}

Output:

Stack In C Output
Stack In C++ Output

Understanding the code:

  • At first, we initialize top as ‘-1’ to signify that that stack is empty. An integer array, stack is also declared with a size 20
  • push() – It is the function that is later used to insert or push data into the Stack. A value is passed to this function which needs to be added into the stack at the top position
  • pop() – It is the function which pops out the latest element from the top and returns it where the function was called
  • peek() – It peeks on the top-most element present inside the stack and returns the same at the place of the function call. Remember, peek does not delete the top element from the stack, it just gives us peek of the value
  • show() – This function is created for the sole purpose of displaying the elements of the stack.

Did you notice the repetitive checking for the top?

We do that because the operations on the stack cannot be performed if the stack gets overloaded or even if it doesn’t contain any data, this checking is required.

For example, while applying the pop operation we must check whether the stack has any data stored inside or not to avoid errors. We have handled the error by printing the “UNDERFLOW” error in our code above.

Applications

Ever thought how recursive function calls work? What happens when a function calls itself and halts until the later returns some value? This halting procedure takes place using stacks.

Suppose we have some nested functions given as

f1()
 {
     return f2();
 }
 f2()
 {
     return f3();
 }
 f3()
 {
     return value;
 }

In this case:

  • as soon as f1 is called it is pushed into the stack
  • Similarly, consecutive calls of the functions f2 and f3 also push both one-by-one into the stack
  • When the function f3 returns a value, it gets popped out of the stack and triggers the f2 function
  • And hence, the consecutive popping of functions f2 and f1 take place.

Further Stack finds its application in different programming methods and techniques, some of them are:

  • Tower of Hanoi
  • And Evaluation of prefix, infix and postfix expressions
  • As well as String Reversal, etc

Conclusion

A stack is a very useful data structure with a wide range of applications. Hope this tutorial helps in understanding the concept of stacks in C++. For any questions feel free to ask in the comments.

References

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages