In this article, we’ll be understanding the working and the need for the **Stack Data Structure**.

When programming, we often deal with a huge amount of uneven and raw data. This calls for the need of data structures to store the data and enable the user to operate on the data efficiently.

## Getting started with the Stack Data Structure

A stack is a **linear data structure** that follows a particular order for the insertion and manipulation of data. Stack uses `Last-In-First-Out (LIFO)`

method for input and output of data.

A stack occupies elements of a particular data type in it in a pre-defined order i.e. LIFO.

As seen in the above pictorial representation of stack, the last element is the first to be popped out from the stack.

**The insertion and deletion of data items take place from the same end of the stack**.

Let’s try to relate stacks with real-life scenarios.

Consider a pile of books. If you observe, the last book placed would be the first one to be accessed by us. Moreover, a new book can be placed only at the top of the pile. Thus, depicting the working of Stacks.

## Operations Performed on a Stack

The Stack data structure primarily deals with the following operations on the data:

`push()`

: This function adds data elements to the stack.`pop()`

: It removes the top element from the stack.`top()`

: Returns the topmost element i.e. element at the top position of the stack.`isEmpty()`

: Checks whether the stack is empty or not i.e. Underflow condition.`isFull()`

: Checks whether the stack is full or not i.e. Overflow condition.

## Working of the Stack Data Structure

**Stack data structure **follows the **LIFO **pattern for the insertion and manipulation of elements into it.

**Note:** We have set a **pointer element **called ‘**top**‘ to keep the account of the topmost element in the stack. This would help the insertion and deletion operation to be performed in an efficient manner.

PUSH (insertion) operation:

- Initially, it checks whether the stack is full or not i.e. checks for the
**Overflow condition**. - In case the stack is found to be
**full**, it will exit with an**Overflow message**. - If the stack is found to have space for occupying elements, then the top counter is
**incremented**by**1**and then the data item is added to the stack.

POP (deletion) operation:

- Initially, it checks whether the stack is empty or not, i.e. checks for the
**Underflow condition**. - In case the stack is found to be
**empty**, it will exist with an**Underflow message**. - If the stack is not empty, display the element pointed by the top pointer element and then decrement the top pointer by 1.

## Implementation of the Stack Data Structure

Stack can be implemented using either of the following ways:

**Linked List****Array**

We’ve already written a comprehensive article on Stack in C++. For the demonstration, I’ll create a simple implementation of a stack using an **Array **in **C++** language.

**Example:**

```
# include<iostream>
using namespace std;
class stack_data
{
public:
int top;
int data[5];
stack_data()
{
top = -1;
}
void push_element(int a);
int pop_element();
void isEmpty();
void isFull();
void display();
};
void stack_data::push_element(int a)
{
if(top >= 5)
{
cout << "Overflow\n";
}
else
{
data[++top] = a;
}
}
int stack_data::pop_element()
{
if(top < 0)
{
cout << "Underflow\n";
return 0;
}
else
{
int pop = data[top--];
return pop;
}
}
void stack_data::isEmpty()
{
if(top < 0)
{
cout << "Stack Underflow\n";
}
else
{
cout << "Stack can occupy elements.\n";
}
}
void stack_data::isFull()
{
if(top >= 5)
{
cout << "Overflow\n";
}
else
{
cout << "Stack is not full.\n";
}
}
void stack_data::display()
{
for(int i=0;i<5;i++)
{
cout<<data[i]<<endl;
}
}
int main() {
stack_data obj;
obj.isFull();
obj.push_element(40);
obj.push_element(99);
obj.push_element(66);
obj.push_element(40);
obj.push_element(11);
cout<<"Stack after insertion of elements:\n";
obj.display();
cout<<"Element popped from the stack:\n";
cout<<obj.pop_element()<<endl;
}
```

**Output:**

```
Stack is not full.
Stack after insertion of elements:
40
99
66
40
11
Element popped from the stack:
11
```

## Features of Stack

- Stack follows
`Last-In-First-Out`

fashion to deal with the insertion and deletion of elements. - The insertion and deletion of data items happen only from a
`single end`

. - Stack is considered to be
`dynamic`

in nature i.e. it is a`dynamic data structure`

. - Stacks do not occupy a
`fixed size`

of data items. - The
**size**of the stack keeps**changing**with every`push()`

and`pop()`

operation.

## Applications of Stack

- In programming, Stack can be used to
**reverse**the elements of an array or string. - A stack can be useful in situations where
**Backtracking**is necessary such as**N-queens problem**, etc. - In editors, the
**undo**and**redo**functions can be performed efficiently by Stack. **Infix**/**Prefix**/**Postfix**conversion of Binary Trees.

## Time Complexity of Stack Operations

- Push operation i.e. push():
**O(1)** - Pop operation i.e. pop():
**O(1)**

The time complexities of push() and pop() operations stay O(1) because the insertion and deletion of the data items happen only from **one end **of the stack which is a single step process to be performed.

## Conclusion

Thus, in this article, we have understood the need for and implementation of a Stack data structure in various programming applications.