Data Structures: Stacks
Tags: beginners, computerscience, algorithms, python
Published: 2021-03-14 05:35:35

This week in our data structure series.

We are tackling the **stack**.

## Table of Contents

- [What is a stack?](#1)
- [Implementation](#2)
- [Complexity](#3)
- [Real Life Use-Cases](#4)
- [Conclusion](#5)

## What is a stack? <a name="1"></a>

A stack is a linear data structure that stores items in Last-In/First-Out (LIFO) manner. In a stack, insertion, and deletion happen at the same end called "top of the stack". 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cui8ac83331qq5998vzq.png)

It's similar to a pile of plates or a deck of cards. For example, in a pile of plates you can:

1. Put a new plate on the top
2. Remove the top plate

If you want to remove the plate at the bottom, then your gonna have to remove all the plates on the top. Hence why it's called **Last-In/First-Out**.

### Methods

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g8roo7u06brbjx7a9x9u.png)

At the end of the day, a stack is an **abstract data type**, meaning that it can be implemented in many different ways but they all must comply with the same common functionality.

1. **Push**: add an item to the stack
2. **Pop**: remove the top-most item in the stack
3. **isEmpty**: checks if the stack is empty
4. **isFull**: checks if the stack is full
5. **Peek**: gets the top-most element without removing it

## Implementation <a name="2"></a>

As we said above, stacks can be implemented mainly in two ways:

1. Array
2. Linked-List

But keep in mind that a stack implemented using arrays are fixed stacks. Meaning they have a fixed size, however, because linked-list is not sequential, this gives them the advantage of being able to make a dynamic or limitless stack.

*PS. You can bypass the array restriction by using a dynamic array.*

We will now go through both implementations.

### Array

For the sake of simplicity, we will use a fixed-sized array.

```python
class Stack: 
    items = [];

    def __init__(self):
        self.items = []

    def  push(self, element): 
        self.items.append(element) 

    def  pop(self): 
        if len(self.items) == 0:
            print('Can not pop form an empty list')
        self.items.pop();
        print('Last item has been poped from the list')

    def isEmpty(self):
        print(len(self.items) == 0)

    def peek(self):
        if len(self.items) == 0:
            print('Stack is Empty')
        print(self.items[len(self.items) - 1]) ;
```

### Linked List

```python
class Node:
	
	# Class to create nodes of linked list
	# constructor initializes node automatically
	def __init__(self,data):
		self.data = data
		self.next = None
	
class Stack:
	
	# head is default NULL
	def __init__(self):
		self.head = None
	
	# Checks if stack is empty
	def isempty(self):
		if self.head == None:
			return True
		else:
			return False
	
	# Method to add data to the stack
	# adds to the start of the stack
	def push(self,data):
		
		if self.head == None:
			self.head=Node(data)
			
		else:
			newnode = Node(data)
			newnode.next = self.head
			self.head = newnode
	
	# Remove element that is the current head (start of the stack)
	def pop(self):
		
		if self.isempty():
			return None
			
		else:
			# Removes the head node and makes 
			#the preceeding one the new head
			poppednode = self.head
			self.head = self.head.next
			poppednode.next = None
			return poppednode.data
	
	# Returns the head node data
	def peek(self):
		
		if self.isempty():
			return None
			
		else:
			return self.head.data
```

## Complexity <a name="3"></a>

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kbszvptisfuuaex7gfkj.png)

**Push**

Because we have direct access to the beginning of our array or linked-list, we can directly append to the list. Making it a time complexity of `O(1)`

**Pop**

The same thing with the push, we simply remove from the top-most item, which we have direct access to the top of the stack. Making it a time complexity of `O(1)`

**Peek**

We have access to the top of the stack, so it's also `O(1)`

**Search**

To search we are gonna have to go through each item sequentially, making it a `O(n)` 

## Real Life Use-Cases <a name="4"></a>

### 1. Back/Forward Button In Web Browsers

A stack is used in back and forward buttons of web-browsers.

- As we move from one page to another those pages are placed on a stack
- URL's of a website get stored on a stack
- Current page is placed on the top of the stack
- When we press the back button that the elements start popping up and display the result in reverse order.
- In this way stack is used in the forward and backward button of a web browser

PS. This is method is also used in tech editors for the undo/redo mechanism.

### 2. In compilers

Compilers use the stack to calculate the value of expressions like `2 + 4 / 5 * (7 - 9)` by converting the expression to prefix or postfix form.

### 3. To reverse a word

Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.

## Conclusion <a name="5"></a>

In summary:

1. A stack is a linear data structure that stores items in Last-In/First-Out (LIFO) manner.
2. In a stack, insertion, and deletion happen at the same end called "top of the stack". 
3. The three main functions of the stack are `push`, `pull`, and `peek`.

I hope you got something out of this post, and if you have any questions feel free to leave them down below.