## Table of contents

- What is Stack?
- Stack Operations
- Create Stack using List without size limit
- NEW __str__ Method
- Operations on Stack using List(push, pop, peek, isEmpty, Delete)
- Create Stack with limit(pop, push, peek, isFull, isEmpty, delete)
- Linked List for Stack
- Operations on Stack using Linked List(push, pop, peek, isEmpty, Delete)
- When to use/avoid Stack

*What is Stack?*

We can think of stack as a pile of vertically stacked objects. Insertion or removal of a stack follows the **LIFO**(Last-in First-Out) method. **What's LIFO?** Imagine you have a pile of books. Now if you want to take out one book from the pile, you have to take the last book first. Because, it's not possible to take out the first book (which is at the very bottom of the pile) as there are more books in top. If you take out the first book, you will scatter the whole pile. Moral, **whichever book come last, it has to be taken first.**

**Stack is a data structure that store items in a LIFO manner**. Why we need Stack? The basic example is the back button of browser pages. Back button follows the principle of the Stack.

Visualization:

So, whichever data comes last will be extracted first.

*Stack Operations*

To understand stack operations, keep two things in mind:

To create a Stack, we need to initialize an empty list or linked list inside a class.

In stack, we mean

**insert**by saying**push**. And, when we say**pop**, we mean**remove**any element from the stack.

**push() method :**

When we pushed `2`

, it went over top of `1`

. So each time we insert an element to a stack, the element will take place on top of the recent added element, or the previous element.

**pop() method :**

In stack, instead of remove we use pop here.

After using pop(), it removed the last element from the stack. If we write `customStack.pop(3)`

, it will remove `3`

.

NB: pop() can't perform on an empty stack.

**peek() method**

This method will return the last element , but it will not remove the element from the stack. No matter how many time we perform `peek()`

, it will always run the same element unless we use `pop()`

on the stack. Only then it will return the latest last element. **Peek method always returns the top element from the stack data structure.**

**isEmpty() method :**

This method is used to check elements inside a stack. If there is no element in the stack, it will return `True.`

If it return `True`

, that means there's no need to perform pop(), push() or peek().

**isFull() method :**

If we create a stack with limited size, this method helps to check if there are any space to push.

**delete() method:** Deletion of the entire stack.

*Create Stack using List without size limit*

There are two ways to create a stack using python.

Stack using List:

Easy to implement

Speed problem while it grows

Stack using Linked List:

Fast performance

Implementation is not easy

Code: Stack, using python list without size limit

```
class Stack:
def __init__(self):
self.list = []
```

Time and Space complexity : O(1)

*NEW __str__ Method*

```
class Stack:
def __init__(self):
self.list = []
def __str__(self):
values = [str(x) for x in reversed(self.list)]
return '\n'.join(values)
```

`values = [str(x) for x in reversed(self.list)]`

this is not going to reverse the original list, it will just **return the reversed version of the original list**. This is looping through the reversed version of the list and placing the elements inside `values`

.

*Operations on Stack using List(push, pop, peek, isEmpty, Delete)*

**isEmpty() :**

```
def isEmpty(self):
if self.list == []:
return True
return False
# Time and Space complexity : O(1)
```

**push() :**

```
def push(self, value):
self.list.append(value)
return "Element successfully pushed"
# Time complexity : O(n), Space complexity : O(1)
```

**pop() :**

```
def pop(self):
if self.isEmpty():
return "There is not any element"
return self.list.pop()
```

**peek() :**

```
def peek(self):
if self.isEmpty():
return "There is not any element"
return self.list(len(self.list)-1)
# Time and Space complexity : O(1)
```

**delete() :**

```
def delete(self):
self.list = None
# Time and Space complexity : O(1)
```

*Create Stack with limit(pop, push, peek, isFull, isEmpty, delete)*

Now we will work with limited size stack. Let's start with creating a stack class. An extra `maxSize`

param is going to add here.

```
class Stack:
def __init__(sefl, maxSize):
self.maxSize = maxSize
self.list = []
def __str__(self):
values = [str(x) for x in reversed(self.list)]
return '\n'.join(values)
```

It will take O(1) time complexity because we are just initializing the list. And the space complexity is O(1)

**isEmpty() :**

```
def isEmpty(self):
if self.list == []:
return True
return False
# Time and Space complexity : O(1)
```

**isFull() :**

```
def isFull(self):
if len(self.list) == self.maxSize: return True
else : return False
```

Time complexity is O(1) because here we are just comparing two variables and returning True/False. Space complexity is O(1), no additional memory is required.

**push() :**

```
def push(self, value):
if self.isFull():
return "The stack is full"
self.list.append(value)
return "Element successfully pushed"
```

Here, time complexity is amortized constant, cause if we set the maximum size, a bigger number and appending this list might take amortized time complexity - means it could reach to O(N) time, even O(n^2) as memory reallocation might occur. Space complexity for appending one element takes O(1).

**pop() :**

```
def pop(self):
if self.isEmpty():
return "There is not any element"
return self.list.pop()
```

**peek() :**

```
def peek(self):
if self.isEmpty():
return "There is not any element"
return self.list(len(self.list)-1)
```

Time complexity is O(1) because here we are just accessing an element and accessing takes O(1) time complexity. Space complexity is O(1).

**delete() :**

```
def delete(self):
self.list = None
```

Time and space : O(1), cause we are setting a list to `None`

*Linked List for Stack*

This code defines a basic implementation of a singly linked list using two classes: `Node`

and `LinkedList`

.

```
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def __iter__(self):
curNode = self.head
while curNode:
yield curNode
curNone = curNode.next
```

`def __iter__(self):`

- This line defines the`__iter__`

method for the`LinkedList`

class. The`__iter__`

method is a special method in Python that returns an iterator for an object. It allows the linked list to be iterated over using a for loop.`curNode = self.head`

- The method starts by setting a local variable`curNode`

to the`head`

of the list, which is the starting point for the iteration.`while curNode:`

- This line starts a`while`

loop that continues as long as`curNode`

is not`None`

. The loop iterates through each node in the list.`yield curNode`

- The`yield`

statement is used to return the current`curNode`

from the iterator. It allows the code iterating over the list to receive the current node and pauses the execution of the`__iter__`

method until the next item is requested.`curNode = curNode.next`

- This line moves`curNode`

to the next node in

*Operations on Stack using Linked List(push, pop, peek, isEmpty, Delete)*

```
class Node:
def __init__(self,value = None):
self.value = value
self.next = next
class LinkedList:
def __init__(self):
self.head = None
class Stack:
def __init__(self):
self.LinkedList = LinkedList()
```

creating stack will take O(1) time complexity because creating/initializing anything takes O(1) times complexity and the space complexity is O(1).

```
def isEmpty(self):
if self.LinkedList.head == None:
return True
return False
customStack = Stack()
print(customStack.isEmpty())
```

The time complexity here is O(1) because we are checking a value if it's `None`

or not. And the space complexity is O(1)

```
def push(self,value):
node = Node(value)
node.next = self.LinkedList.head
self.LinkedList.head = node
customStack = Stack()
customStack.push(3)
print(customStack)
```

Creating, assigning takes O(1) time complexity. Space complexity is O(1)

```
def pop(self):
if self.isEmpty:
return "Empty stack"
else:
nodeValue = self.LinkedList.head.next
self.LinkedList.head = self.LinkedList.head.next
return nodeValue
```

Stacks in Data Structures

Time complexity is O(1) because deleting an element takes O(1) time complexity. Space complexity is O(1).

```
def peep(self):
if self.isEmpty:
return "Empty stack"
else:
nodeValue = self.LinkedList.head.next
return nodeValue
```

```
def delete(self):
self.LinkedList.head = None
```

Time and space complexity : O(1)

*When to use/avoid Stack*

Use :

Apply LIFO functionality

The chance of data corruption is minimum

Not ideal:

- Random access is not possible