Forem: BHARATH KUMAR DAMARLA

stack in python using LinkedList or List

BHARATH KUMAR DAMARLA — Sat, 25 Sep 2021 14:14:11 +0000

Stack is a type of data structure. They are preferred over arrays or lists due to their fast insert and delete operations.
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())

Output

data: ['1','2','3'] size: 3

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()

Output

3
3 <- 2 <- 1 <-

Implementation of Queue in python

BHARATH KUMAR DAMARLA — Sat, 25 Sep 2021 14:13:37 +0000

1.Queue is a type of data structure.Queue is based on the principle first in first out (FIFO) i.e first inserted element will be deleted first.

2.In queue Insertion of elements is done at one end i.e rear and deleting of elements is done at other end
i.e front.

3.Queue works similar to queue at a ticket counter the first person in the queue is the front and the last person is the rear.

Now let us look at some example to implement a queue using a LinkedList

Example:

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

class queue:
    def __init__(self):
        self.front = None
        self.rear = None

# push element on rear side
    def push(self,val):
        if (self.rear == None):
            self.front = node(val)
            self.rear = self.front
        else:
            new_node = node(val)
            self.rear.next = new_node
            self.rear = self.rear.next

# pop deletes the first inserted element in queue in front side
    def pop(self):
        if (self.front == None):
            print('No elements to pop in Queue')

        else:
            self.front = self.front.next

# To show where front is currently at
    def show_front(self):
        print('front: ',self.front.val)

# To show where rear is currently at
    def show_rear(self):
        print('rear: ', self.rear.val)

    def display_queue(self):
# To display the whole queue we have to traverse the linkedList
# Using a dummy node starting from head
        q = []
        dummy = self.front
        while(dummy):
            q.append(dummy.val)
            dummy = dummy.next
# Reverse 'q' to avoid confusion
        q.reverse()
        print('Queue data: ', q)

Input

x = queue() # instantiates a queue object named 'x' 
x.push(1)
x.push(2)
x.push(3)
x.push(4)
x.push(5)
x.push(6)
x.push(7)

x.display_queue(), x.show_front(), x.show_rear()
x.pop()
# front is changed after pop operation
x.display_queue(), x.show_front(), x.show_rear()

Output

Queue data:  [7, 6, 5, 4, 3, 2, 1]
front:  1
rear:  7
# after pop operation
Queue data:  [7, 6, 5, 4, 3, 2]
front:  2
rear:  7

Arrays(Lists) in python

BHARATH KUMAR DAMARLA — Sat, 18 Sep 2021 09:17:26 +0000

Python does not have a built in array type, but you can use lists for all of the same tasks. An array is a collection of values of the same type saved under the same name.

Each value in the array is called an “element” and indexing that represents its position. You can access specific elements by calling the array name with the desired element’s index. You can also get the length of an array using the len() method.

Unlike programming languages like Java that have static arrays after declaration, Python’s arrays automatically scale up or down when elements are added/subtracted.

For example, we could use the append() method to add an additional element on the end of an existing array instead of declaring a new array.

Arrays(List)

1.cars = ["Toyota", "Tesla", "Hyundai"]
2.print(len(cars))
3.cars.append("Honda")
4.cars.pop(1)
5.for x in cars:
6.  print(x)

Output

3
Toyota
Hyundai
Honda