## Stack and its basic Operations

**What is stack?**

First, let us see the properties of data structures that we already do know and build-up our concepts towards the stack.

**Array:**Its a*random-access*container, meaning any element of this container can be accessed instantly**Linked List:**It's a*sequential-access*container, meaning that elements of this data structure can only be accessed sequentially

→ Following a similar definition, a **stack **is a container where only the top element can be accessed or operated upon.

AStackis a data structure following the LIFO(Last In, First Out) principle.

If you have trouble visualizing stacks, just assume a stack of books.

- In a stack of books, you can only see the top book
- If you want to access any other book, you would first need to remove the books on top of it
- The bottom-most book in the stack was put first and can only be removed at the last after all books on top of it have been removed.

PUSHOperation

Push operation refers to inserting an element in the stack. Since there’s only one position at which the new element can be inserted — Top of the stack, the new element is inserted at the top of the stack.

POPOperation

Pop operation refers to the removal of an element. Again, since we only have access to the element at the top of the stack, there’s only one element that we can remove. We just remove the top of the stack. **Note: **We can also choose to return the value of the popped element back, its completely at the choice of the programmer to implement this.

PEEKOperation

Peek operation allows the user to see the element on the top of the stack. The stack is not modified in any manner in this operation.

isEmpty: Check if stack is empty or not

To prevent performing operations on an empty stack, the programmer is required to internally maintain the size of the stack which will be updated during push and pop operations accordingly. isEmpty() conventionally returns a boolean value: True if size is 0, else False.

#### Stack Implementation

As we’ve learned before, Stack is a very useful concept that a good programmer could use to his/her benefit. But can you implement it in your code yet? It's not that difficult once you think about it, let’s walk through its properties and implement them in code.

You should remember one very important thing though →

All operations in the stack must be ofO(1)time complexity

We shall be implementing stack in two different ways by changing the underlying container: **Array** and **Linked List.**

#### 1. Array Implementation

An array is one of the simplest containers offering random access to users based on indexes. But can we access any element of the stack at any given time? **No**. That’s why we need to set an index as **top** and then access only the element at index **top.**

```
int stack[10]
int top = -1
```

Here, 10 is a pre-defined capacity of the stack. We can throw a stack overflow error if a user tries to exceed this capacity.

★ The default value for the **top** is -1, denoting that the stack is empty.

Do we need to store any other parameter for the stack? current size, perhaps? **No. **We may need to store the **capacity** of the stack but we don’t need to store the current size. We can know the current size of stack by looking at the value of the **top. (How?)**

Let us wrap this group of data members in a **class**

```
class Stack{
int arr[]
int capacity
int top
}
```

Let us also create a constructor which initializes **capacity** and **top**

```
Stack(int cap)
{
capacity = cap
top = -1
}
```

★ You are also required to allocate memory to **arr **according to the language you use to implement it.

→Now, we need to implement the operations that we generally perform on stacks.

PUSH Operation

What changes are made to the stack when a new element is pushed?

- A new element is inserted on top
- The value of top increases by 1

▹ What if the stack is filled to its capacity?

We shall check if the stack if full before inserting a new element and throw an error if it is.

Now, let us implement this simply

```
void push(int item)
{
if ( top == capacity - 1 )
print( "Stack overflow!" )
else
{
arr[top+1] = item
top = top + 1
}
}
```

POP Operation

Let’s try one more: Pop().

What changes are made to the stack internally for a pop operation?

- The top element is removed
- The value of
**top**is decreased by 1

▹ Can you think of an exception in this case like the one above of stack being full? Ans: The stack can be empty when the pop operation is called

Let’s try implementing it now

```
void pop()
{
if ( isEmpty() == True )
print( "Stack is empty!" )
else
top = top - 1
}
```

★ Is decreasing the value of **top **same as deleting the top element? (**Think!**)

Peek and isEmpty Operation

Peek and isEmpty are quite simple to implement. We need to steer clear of exceptions though.

```
int peek()
{
if ( isEmpty() == True )
{
print( "Stack is empty!" )
return -1
}
else
return arr[top]
}
```

```
bool isEmpty()
{
if ( top == -1 )
return True
else
return False
}
```

#### 2. Linked List Implementation

Before implementing stack with a linked list, let us first try to visualize a stack as a linked list. There are two ends of a linked list: **head** and **tail.**

Which end do you think should represent the top of the stack? (**Think!**)

The top of the stack should be represented byheadbecause otherwise, we would not be able to implement the operations of the stack in O(1) time complexity.

Let us assume that we have used class for linked list

```
class ListNode{
int val
ListNode next
}
```

What should an empty stack look like if implemented with a linked list? **Ans: **Its head will point to NULL

`ListNode head = NULL`

Is there any benefit to implementing a stack as linked list compared to arrays? **Ans: **We do not need to mention the size of the stack beforehand.

→ Although, if you want to implement a limit to prevent excess use, you may need to encapsulate the **class ListNode **inside some other class along with a data member **capacity**.

```
class Stack{
int capacity
class ListNode{
int val
ListNode next
}
}
```

We shall be using just using **class ListNode **below for simplicity.

→Let us move towards stack operations

PUSH Operation

The same properties hold as above with an added benefit that we need not worry about the stack being full

```
void push(int item)
{
ListNode temp = ListNode(item)
temp.next = head
head = temp
}
```

POP Operation

Properties of linked list relaxed us from checking if the stack is full in push operation. Do they provide any relaxation for exceptions in pop operation? **No.** We still need to check if the stack is empty.

Since the top is represented by the **head **in this implementation. How do we delete the first element in a linked list?

Simple, we make the second element as the head.

```
void pop()
{
if ( head == NULL )
print ( "Stack is empty!" )
else
head = head.next
}
```

★ You may be required to deallocate the popped node to avoid memory leak according to your programming language's conventions.

Peek and isEmpty Operation

The implementation of these two operations is pretty simple and straight-forward in the linked list too.

```
int peek()
{
if ( head == NULL )
{
print ( "Stack is empty!" )
return -1
}
else
return head.val
}
```

```
bool isEmpty()
{
if ( head == NULL )
return True
else
return False
}
```

#### Augmentations in Stack

You can augment the stack data structure according to your needs. You can implement some extra operations like:-

- isFull(): tells you if the stack if filled to its capacity
- The pop operation could return the element being deleted

★ A quite interesting augmentation that has been asked in many interviews asks you to implement a **MinStack** which holds all properties of a regular stack but also returns the minimum value in the stack. Since all stack operations are expected to be executed in constant time, you need to return the minimum element in the stack in O(1) time complexity.

**Applications of Stack Data Structure **

- An "undo" mechanism in text editors
- Forward and backward feature in web browsers
- Check for balanced parentheses in an expression
- Expression evaluation and syntax parsing
**Backtracking**. This is a process when you need to access the most recent data element in a series of elements. Think of a maze - how do you find a way from an entrance to an exit? Once you reach a dead end, you must backtrack. But backtrack to where? to the previous choice point. Therefore, at each choice point, you store on a stack all possible choices. Then backtracking simply means popping a next choice from the stack.- We use a stack for the Iterative implementation of several recursive programs like tree traversals, DFS traversal in a graph, etc.
- For solving several problems in algorithms, we use a stack as the principle data structure with which they organize their information.
- Memory management: Any modern computer environment uses a stack as the primary memory management model for a running program.

#### Suggested Problems to solve

- Find next greater element in an array
- Min Stack Problem
- Check for balanced parentheses in an expression
- Largest Rectangle in a Histogram
- Trapping Rainwater
- Reverse a stack using recursion
- Validate Stack Sequences
- Merge overlapping intervals
- Sort a stack using another stack
- Check if a string is a palindrome using stacks

**Happy Coding! Enjoy Algorithms!**