## Introduction

A stack is a linear data structure in which the insertion and deletion operations can be performed at one end called *top* of the stack. A stack is also called a **L**ast **I**n **F**irst **O**ut (LIFO) data structure. Remember Array and Linked list where we can add or remove the data from both the end (front or back). Unlike these data structures, stack allows the user to access only one end. Figure 1 visualizes a stack with 5 items.

As we can see in Figure 1, we can not access item 1. The bottom is closed. Top of the stack is the *only* place where we have access to. We can only access item 5 which is at the top of the stack. In order to get to the item 4, we need to remove 5, to get to item 3, we need to remove 4 and 5 and so on. In all the operations we do in the stack, we manipulate the top of the stack in some way. Based on how we use the top, there are three operations we can do on the stack.

**Push**: We insert a new item at the top of the stack.**Pop**: We remove the item from the top of the stack.**Top**: We read the value of the item at the top of the stack.

Now I am going to explain all these operations in detail.

## Operations on stack

### Push

A new item can be pushed into a stack using the following steps.

- Check if the stack is full. If it is, then you can not insert the item. Raise “Stack Overflow” error.
- If the stack is not full, insert the item at the top of the stack.
- Make this item a new top of the stack.

### Pop

An item on the top of the stack can be removed (popped) using following steps.

- Check if the stack is empty. If it is, then you can not remove the item. Raise “Stack Underflow” error.
- If the stack is not empty, remove the item at the top of the stack.
- Update the top of the stack.

### Top (or peek)

The top operation returns the item at the top of the stack. Don’t be confused this operation with the `pop`

operation. The `pop`

operation *removes* the top item whereas the `top`

operation *only reads* the value of the top item. As in the pop operation, we need to check if the stack is empty before reading the value.

## Complexities

The complexities of all the operations are tabulated below.

Operation | Complexity |
---|---|

Push | O(1) |

Pop | O(1) |

Top (Peek) | O(1) |

## Applications of a stack

A stack is widely used in many areas of computer science. Some of the applications are listed below.

- Many algorithms like Depth First Search, Graham Scan, Monotone Triangulation, etc.
- Expressions evaluation and syntax parsing.
- Series of functions are stored in a stack by a compiler.
- Backtracking
- Undo features, back and forth features etc.

## Implementation

A stack can be implemented using arrays as well as linked lists.

### Implementation using array

Implementation of the stack using an array in C, C++, and Java is given below.

1 | // C implementation of stack using arrays |

1 | // C++ implementation of Stack using array |

1 | // Java implementation of Stack using array |

### Implementation using linked list

Implementation of the stack using a linked list in C, C++, Java, and Python is given below.

1 | // C implementation of stack using linked list |

1 | // C++ implementation of stack using linked list |

1 | // Java implementation of stack using linked list |

1 | # Python implementation of stack using linked list |