# Stack - Make Your Table Plates Stackable

## Stack Data Structure

Before we start, let's imagine a stack of 5 new plates on your table. Now, it's your dinner time, so you need one plate for your main dish. How do you pick your first plate. You will pick the topmost plate, right? Now, you have finished your main dish and you need a plate for your dessert. Again, you will pick the topmost plate, right? Now, your dinner is over and you need to put all the plates back to the stack. How do you do that? You will put the plates back on the stack on top of each other. This is how a stack data structure works.

From the above analogy, we observed that we can only access the topmost element of the stack. Like this when we need to put the plates back to the stack, we can only put the plates on top of each other. This method of accessing the data is called Last In First Out (LIFO) method. This is the basic principle of the stack data structure.

## Stack Implementation

Stack can be implemented using array or linked list. Let's see how we can implement stack using linked list. To learn more about linked list, you can read my article on Linked List.

To implement stack using linked list, we need to create two classes - `Node`

and `Stack`

. The `Node`

class will be used to create the nodes of the linked list. The `Stack`

class will be used to create the stack object.

### Node Class

The `Node`

class will have two properties - `data`

and `next`

. The `data`

property will store the data of the node and the `next`

property will store the reference to the next node.

```
class Node {
public:
int data;
Node *next;
Node(int data) {
this->data = data;
this->next = NULL;
}
};
```

### Stack Class

The `Stack`

class will have two properties - `head`

and `size`

. The `head`

property will store the reference to the topmost node of the stack and the `size`

property will store the size of the stack. Optionally, we can also have a `tail`

property to store the reference to the last node of the stack.

```
class Stack {
public:
Node *head;
int size;
Stack() {
this->head = NULL;
this->size = 0;
}
};
```

## Stack Operations

Now, we have the basic structure of a stack. Let's see how we can perform the basic operations on the stack. The basic operations on the stack are:

**Push**: This operation is used to add an element to the top of the stack.**Pop**: This operation is used to remove an element from the top of the stack.**Peek**: This operation is used to get the topmost element of the stack.**isEmpty**: This operation is used to check if the stack is empty or not.**getSize**: This operation is used to get the size of the stack.

### Push Operation

The `push`

operation is used to add an element to the top of the stack.

```
void push(int data) {
Node *newNode = new Node(data);
if (this->head == NULL) {
this->head = newNode;
} else {
newNode->next = this->head;
this->head = newNode;
}
this->size++;
}
```

Here goes the explanation:

- We created a new node with the given data.
- If the stack is empty, we set the
`head`

property of the stack to the new node. - If the stack is not empty, we set the
`next`

property of the new node to the`head`

property of the stack. Then, we set the`head`

property of the stack to the new node. - Finally, we increment the
`size`

property of the stack by 1.

Complexity Analysis:

**Time Complexity**: O(1)**Space Complexity**: O(1)

### Pop Operation

The `pop`

operation is used to remove an element from the top of the stack.

```
int pop() {
if (this->head == NULL) {
return -1;
}
int data = this->head->data;
Node *temp = this->head;
this->head = this->head->next;
delete temp;
this->size--;
return data;
}
```

Here goes the explanation:

- If the stack is empty, we return -1.
- If the stack is not empty, we store the
`head`

property of the stack in a temporary variable. - Then, we set the
`head`

property of the stack to the`next`

property of the`head`

property of the stack. - Then, we store the
`data`

property of the temporary variable in a variable and delete the temporary variable. - Finally, we decrement the
`size`

property of the stack by 1 and return the data.

Complexity Analysis:

**Time Complexity**: O(1)**Space Complexity**: O(1)

### Peek Operation

The `peek`

operation is used to get the topmost element of the stack.

```
int peek() {
if (this->head == NULL) {
return -1;
}
return this->head->data;
}
```

Here goes the explanation:

- If the stack is empty, we return -1.
- If the stack is not empty, we return the
`data`

property of the`head`

property of the stack.

Complexity Analysis:

**Time Complexity**: O(1)**Space Complexity**: O(1)

### isEmpty Operation

The `isEmpty`

operation is used to check if the stack is empty or not.

```
bool isEmpty() {
return this->head == NULL;
}
```

Here goes the explanation:

- We return true if the
`head`

property of the stack is NULL. - We return false if the
`head`

property of the stack is not NULL.

Complexity Analysis:

**Time Complexity**: O(1)**Space Complexity**: O(1)

### getSize Operation

The `getSize`

operation is used to get the size of the stack.

```
int getSize() {
return this->size;
}
```

Here goes the explanation:

- We return the
`size`

property of the stack.

Complexity Analysis:

**Time Complexity**: O(1)**Space Complexity**: O(1)

Now, we have implemented all the basic operations on the stack. Let's see how we can use these operations:

```
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *next;
Node(int data) {
this->data = data;
this->next = NULL;
}
};
class Stack {
public:
Node *head;
int size;
Stack() {
this->head = NULL;
this->size = 0;
}
void push(int data) {
Node *newNode = new Node(data);
if (this->head == NULL) {
this->head = newNode;
} else {
newNode->next = this->head;
this->head = newNode;
}
this->size++;
}
int pop() {
if (this->head == NULL) {
return -1;
}
int data = this->head->data;
Node *temp = this->head;
this->head = this->head->next;
delete temp;
this->size--;
return data;
}
int peek() {
if (this->head == NULL) {
return -1;
}
return this->head->data;
}
bool isEmpty() {
return this->head == NULL;
}
int getSize() {
return this->size;
}
};
int main() {
Stack *stack = new Stack();
stack->push(10);
stack->push(20);
stack->push(30);
cout << stack->peek() << endl;
cout << stack->pop() << endl;
cout << stack->peek() << endl;
cout << stack->getSize() << endl;
cout << stack->isEmpty() << endl;
return 0;
}
```

## Applications of Stack

Stacks are used in many applications. Some of the applications of stacks are:

**Postfix Evaluation**: Stacks are used to evaluate a postfix expression.**Prefix Evaluation**: Stacks are used to evaluate a prefix expression.**Redo-Undo**: Stacks are used to implement the redo-undo feature in text editors.**Back button in web browsers**: Stacks are used to implement the back button in web browsers.**Forward and backward feature in music players**: Stacks are used to implement the forward and backward feature in music players.**Recursive Function Calls**: Stacks are used to store the function calls in the memory.**Memory Management**: Stacks are used to manage the memory in the operating system.

## References

- "Applications, Advantages and Disadvantages of Stack - GeeksforGeeks" Geeksforgeeks, 13 Jun. 2002, https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-stack/.
- "Stack Data Structure and Implementation in Python, Java and C/C++" Programiz, https://www.programiz.com/dsa/stack.