Data Structures - Stacks (Part 2/3)

Dec 15, 2016 |

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

Definition

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.

Terminology

push : insert an element
pop : remove an element

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

LIFO: Last In First Out

Implimentation:

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

Quizz

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None
        
class LinkedList(object):
    def __init__(self, head=None):
        self.head = head
        
    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

    def insert_first(self, new_element):
        new_element.next = 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 = self.head.next
            deleted_elt = None # good practice to delete 
            return deleted_elt
        else:
            return None

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

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

    def push(self, new_element):
        self.ll.insert_first(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
stack.push(e2)
stack.push(e3)
print stack.pop().value
print stack.pop().value
print stack.pop().value
print stack.pop()
stack.push(e4)
print stack.pop().value