DEV Community

Cover image for Interpreted Python: Linear Data Structures
Tito
Tito

Posted on • Updated on

Interpreted Python: Linear Data Structures

Introduction

Welcome back to this exciting data structures series. This is a continuation of Built-in Data Structures in python.If you are new to python, I would highly recommend you to read my previous post .
User-defined data structures are data structures created by user primitively while keeping in mind the built-in data structure.
Additionally they can be classified into :
1. Linear:
a. Stack b. Queue c. Linked List
2. Non-linear:
a. Tree b. Graph c. HashMap

Demo and Explanation
a.Stack
Stacks Store items on the basis of First-In/Last-Out (FILO) or Last-In/First-Out (LIFO). To add and remove item from a stack, you will use push and pop respectively. Other functions related to Stack are empty(), size() and top().

Stacks can be implemented using modules and data structures from the Python library – list, collections.deque, and queue.LifoQueue.

Stack data-structure
Implementation
As stated earlier , stacks can be implemented in 3 ways, namely

  • List
  • collections.deque
  • queue.LifoQueue

And We shall cover them in the simplest form

Implementing Stack Using list

car_stack = []
car_stack.append('Audi')
car_stack.append('Subaru')
car_stack.append('BMW')
car_stack.append('Chevrolet')
car_stack

Output:
['Audi', 'Subaru', 'BMW', 'Chevrolet']
#note the order of appending.
car_stack.pop()
'Chevrolet'
Enter fullscreen mode Exit fullscreen mode

Note

  • Creating stacks using List might be easier due to it's familiarity, however list has some drawbacks. You will realize, as a list grow, speed will become a challenge.
  • Additionally,Inserting item to your stack at a position other than the end, it can take much longer. This is not normally something you would do to a stack, however.

Implementing stacks Using collections.deque

deque is pronounced “deck” and stands for “double-ended queue.”
You can use the same methods on deque as you saw above for list, .append(), and .pop()

from collections import deque

town_stack = deque()
town_stack.append('kilifi')
town_stack.append('mumbai')
town_stack.append('kansas')
town_stack

Output:
deque(['kilifi', 'mumbai', 'kansas'])

town_stack.pop()
Output:
kansas
Enter fullscreen mode Exit fullscreen mode

NOTE

  • From the brief explanation on deque, you will realize deque and list serve the same operations. However , you will realize deque and list have a difference in the why they store data.

List store elements in blocks of adjacent memory which might take time to append() a stack especially when the stack is full.
Deque store elements in its own memory block and has a reference to the next entry in the list.This facilitate easy update of nodes

Implementing stacks Using queue.LifoQueue

There are various functions available in this module:

Method Description
maxsize Number of items allowed in the queue.
empty() Return True if the queue is empty, False otherwise.
full() Return True if there are maxsize items in the queue. If the queue was initialized with maxsize=0 (the default), then full() never returns True.
get() Remove and return an item from the queue. If the queue is empty, wait until an item is available.
get_nowait() Return an item if one is immediately available, else raise QueueEmpty.
put(item) Put an item into the queue. If the queue is full, wait until a free slot is available before adding the item.
put_nowait(item) Put an item into the queue without blocking.
qsize() Return the number of items in the queue. If no free slot is immediately available, raise QueueFull.
from queue import LifoQueue

# Initializing a stack
mystack = LifoQueue(maxsize = 6)

# qsize() show the number of elements
# in the stack
print(mystack.qsize())

# put() function to push
# element in the stack
mystack.put('ub40')
mystack.put('Lucky dube')
mystack.put('Charlie Chaplin')
mystack.put('Sinach')
mystack.put('Davido')
mystack.put('Hillsong')

print("Full: ", mystack.full()) 
print("Size: ", mystack.qsize()) 

# get() fucntion to pop
# element from stack in 
# LIFO order
print('\nElements poped from the stack')
print(mystack.get())
print(mystack.get())
print(mystack.get())

print("\nEmpty: ", mystack.empty())

Output:
0
Full:  True
Size:  6

Elements popped from the stack
Hillsong
Davido
Sinach

Empty:  False
Enter fullscreen mode Exit fullscreen mode

b.Queue
A queue is a useful data structure in programming, so far we have discussed the LIFO operation in stack. For queue it follows FIFO operation(First In First Out or in simple term first come first Served).Therefore , the item that goes in first goes out first.

In programming terms, putting items in the queue is called enqueue, and removing items from the queue is called dequeue.

Queue implementation in Python

Basic Queue Operations

Operation Description
Enqueue Add an element to the end of the queue
Dequeue Remove an element from the front of the queue
IsEmpty Check if the queue is empty
IsFull Check if the queue is full
Peek Get the value of the front of the queue without removing it

#implementing queue
class Queue:
  def __init__(self):
    self.queue = list()

  #adding elements
  def enqueue(self,item):
    self.queue.append(item)

  #remove item from queue
  def dequeue(self,item):
    if len(self.queue)< 1:
      return None
    return self.queue.pop(0)

  #Display queue
  def display(self):
    print(self.queue)

  #queue size
  def size(self):
    return len(self.queue)

q = Queue()
q.enqueue(18)
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)
q.dequeue(0)
q.display()
Enter fullscreen mode Exit fullscreen mode

c. Linked list

A linked list is a sequence of data elements, which are connected together via links. This is implemented using the concept of nodes.Each data element contains a connection to another data element in form of a pointer.Each node contains a value and a pointer to the next node in the chain.
Linked list can be implemented in various form:

  • Singly Linked list
  • Circularly Linked Lists
  • Doubly Linked Lists

However in this post we will majorly look into singly linked list.Which is the simplest and a building block for the rest of the lists.
Terminologies:

  • Head:This is the first node of a linked list
  • Tail: This is the last node of a linked list and can be identified as having a None value as its next reference.
  • link or pointer : It is simply the identifier to the next node
  • Traversing(link hopping or pointer hopping): It is the process of moving from the head through each node following each node’s next reference, and finally to the tail of the linked list

Linked list implementation in python

Basic Implementation of Linked List

class Node:
    # Creating a node
    def __init__(self, item):
        self.item = item
        self.next = None
class LinkedList:
  def __init__(self):
    self.head = None


if __name__ == '__main__':

    linked_list = LinkedList()
    linked_list.head = Node(1)
    second = Node(2)
    third = Node(3)
    linked_list.head.next = second
    second.next = third
    while linked_list.head != None:
        print(linked_list.head.item, end=" ")
        linked_list.head = linked_list.head.next

Enter fullscreen mode Exit fullscreen mode

In this post , I have basically define the structure and definition of linear data structures.In my upcoming posts I will be going into details especially for linked List.
Follow me for more post

Top comments (0)