In this section we look into two other basic data structures that are useful. These two data structures are Stacks and Queues. Both of these data structures are build on top of the Linked-List data structure that we have seen in the  previous section.

Let’s start with the Stack data structure, it keeps data in a linear order (one after the other) but it has access only to the top element.  It supports two basic operations; push and pop. Push adds an element to the collection and pop removes the most recently added element that was not yet removed.  Additionally, a peek operation may give access to the top without modifying the stack. Because of having access only to the last inserted element in the stack an alternative name is used for this data structure, LIFO (last in, first out). When I was learning this data structure it reminded me of the Pez candy dispenser, similarly we have access only to the top “candy”, in order to have the second candy we have to pop out the first one before. We can implement the Stack data-structure by using Linked-Lists:

 
class Stack(object): 
    def __init__(self, stack=None): 
        self.stack = stack

    def push(self, element):
        if self.stack.head is not None:
            self.stack.head = Node(element, self.stack.head)
        else:
            self.stack.head = Node(element, None)

    def pop(self):
        if self.stack.head is not None:
            temp_element = self.stack.head.value
            self.stack.head = self.stack.head.next_node
            return temp_element
        return None

    def peek(self):
        if self.stack.head is not None:
            return self.stack.head.value
        return None

Note that there is no limitations on the number of elements that a stack can have. Additionally, the supported operations for stacks -push, pop, and peek- are very fast, more precisely in \(O(1)\) time. In other words, using for example a list to implement the Stack data-structure would not be advised. A list would have a limit on the number of elements and it would also have worse time complexity for the above operations.

A Queue also keeps data in a linear order, but the difference with the stack is that the next element to be popped is the first element that we put in the data structure, also called first-in, first-out (FIFO). We can also see this motive of organization in everyday life, just think of any line that you have to wait at a bank, at a grocery store or anywhere else.  At any of these places, the person who came first is being taken care first. There are two basic operations that a Queue should support; one is to add an element in the data structure which is called enqueue, the other one is to remove an element from the data structure which is called dequeue. Similarly as before the implementation of a Queue is build on top of a linked list and for similar reasons using a list instead is not recommended.

 
class Stack(object): 
    def __init__(self): 
        self.first = None
        self.last = None

    def enqueue(self, element):
        if self.first is None:
            self.last = Node(element, None)
            self.first = self.last
        else:
            self.last.next_node = Node(element, None)
            self.last = self.last.next_node

    def dequeue(self):
        if self.first is not None:
            temp_element = self.first.value
            self.first = self.first.next_node
            return temp_element
        return None