DEV Community

BHARATH KUMAR DAMARLA
BHARATH KUMAR DAMARLA

Posted on

stack in python using LinkedList or List

Alt Text

  1. Stack is a type of data structure. They are preferred over arrays or lists due to their fast insert and delete operations.

  2. Stack works on the last in first out (LIFO)
    principle i.e insertion and deletion happens at only one end.

3.stack has an O(1) time complexity for pop or push operation.

look at the code below to understand how to implement stack on our own and how to use it.

Note: We can implement a stack using LinkedList or lists in python. Both implementations work fine and have the same time complexities for all the operations but I prefer implementing them using a list because it's much easier.

Stack using list

class stack:
    def __init__(self):
        self.data = []

    def push(self,elem):
        self.data.append(elem)

    def pop(self):
     try:
        popped_item = self.data.pop()
        return popped_item
     except IndexError:
        print('Stack Underflow')

    def peek(self):
     try:
        print(self.data[len(self.data)-1])
     except IndexError:
        print('No elements in stack')

    def size(self):
      return len(self.data)

my_stack = stack()
my_stack.push('1')
my_stack.push('2')
my_stack.push('3')
print("data:", my_stack.data, "size:", my_stack.size())
Enter fullscreen mode Exit fullscreen mode

Output

data: ['1','2','3'] size: 3
Enter fullscreen mode Exit fullscreen mode

Stack using linkedlist

class node:
  def __init__(self,val):
    self.val = val
    self.next = None

class linkedListStack:

  def __init__(self):
    self.head = None

  def push(self,val):
    if (self.head == None):
      self.head = node(val)
    else:
      new_node = node(val)
      new_node.next = self.head
      self.head = new_node

  def pop(self):
    if (self.head == None):
      print('Stack underflow')
    else:
      popped_val = self.head.val
      self.head = self.head.next
      return popped_val

  def peek(self):
    if (self.head==None):
      print(None)
    else:
      print(self.head.val)

  def display_stack(self):
    dummy = self.head
    while(dummy):
      print(dummy.val,end=" <- ")
      dummy = dummy.next

lls = linkedListStack() 
lls.push(1)
lls.push(2)
lls.push(3)
lls.push(4)
lls.pop()
lls.peek()
lls.display_stack()
Enter fullscreen mode Exit fullscreen mode

Output

3
3 <- 2 <- 1 <-
Enter fullscreen mode Exit fullscreen mode

Discussion (0)