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.

Table of Contents

## 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.