Stack Explained: A Beginner's Guide to Data Structures

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

5. 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.

6. 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.

7. 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.

8. 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.

9. 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