Table of Contents

## 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:**

**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

- https://stackoverflow.com/questions/14801015/stacks-implementation
- https://stackoverflow.com/questions/8578501/what-are-stacks-used-for-why-are-they-in-c
- https://stackoverflow.com/questions/10272725/c-stacks-with-multiple-values