Data Structures - Stacks (Part 2/3)

welcome to the 2nd part of the series of post on Data Structures. Topic is Stacks.

  1. Linked Lists
  2. Stacks
  3. Queues


Stacks are a list-based data Structure. The idea is that we can keep putting elements on the top and they are easy to access. However, it is more difficult to acces the elements at the bottom.

Stacks are useful when you care more about the recent elements or the order in which you see and save elements.


  1. push : insert an element
  2. pop : remove an element

Both, push and pop are constant time O(1).

  1. LIFO: Last In First Out


A stack can be implemented with a linked list:

One can use built-in functions to turn a python list into a stack: pop() and append()


  • Add a few methods to the LinkedList class (check Quizz in Part I), and use that to implement a Stack. There are 4 functions below to fill in: insert_first() , delete_first() , push(), and pop(). *
class Element(object):
    def __init__(self, value):
        self.value = value = None
class LinkedList(object):
    def __init__(self, head=None):
        self.head = head
    def append(self, new_element):
        current = self.head
        if self.head:
                current =
   = new_element
            self.head = new_element

    def insert_first(self, new_element): = self.head
        self.head = new_element

    def delete_first(self):
        "Delete the first (head) element in the LinkedList and return it"
        if self.head:
            deleted_elt = self.head
            self.head =
            deleted_elt = None # good practice to delete 
            return deleted_elt
            return None

    def insert_first(self, new_element): = self.head
        self.head = new_element

class Stack(object):
    def __init__(self,top=None):
        self.ll = LinkedList(top)

    def push(self, new_element):

    def pop(self):
        "Pop (remove) the first element off the top of the stack and return it"
        return self.ll.delete_first()
# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)

# Start setting up a Stack
stack = Stack(e1)

# Test stack functionality
print stack.pop().value
print stack.pop().value
print stack.pop().value
print stack.pop()
print stack.pop().value