class Stack():  # LIFO

    # constructor
    def __init__(self):
        self.data = []

    def empty(self):
        return len(self.data) == 0

    def push(self,x):
        self.data.append(x)

    def pop(self):
        if self.empty():
            return None
        else:
            temp = self.data[len(self.data)-1]
            self.data = self.data[0:len(self.data)-1]
            # self.data.remove(len(self.data)-1)
            return temp
    
    def __str__(self):
        return "BOTTOM " + str(self.data) + " TOP"

s1 = Stack()
s1.push(10)
s1.push(20)
print(s1)
x = s1.pop()
print(x)
print(s1)

BOTTOM [10, 20] TOP
20
BOTTOM [10] TOP

s2 = Stack()
s2.push("John")
s2.push("Alice")
print(s2)

BOTTOM ['John', 'Alice'] TOP

s3 = Stack()
for i in range(10):
    s3.push(i)
print(s3)

while True:
    if s3.empty():
        break
    x = s3.pop()
    print(x)

BOTTOM [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] TOP
9
8
7
6
5
4
3
2
1
0

xs = [10,20,(30,40)]

[1]*10

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

# Circular Queue Implementation
class Queue():
    INITIAL_CAPACITY = 10
    
    def __init__(self):
        self.data = [None]*Queue.INITIAL_CAPACITY
        self.front = 0
        self.size = 0

    def empty(self):
        return self.size == 0

    def dequeue(self):
        if self.empty():
            return None
        else:
            temp = self.data[self.front]
            self.data[self.front] = None
            self.size = self.size - 1
            self.front = (self.front + 1)%len(self.data)
            return temp
    
    def resizeUp(self,cap):  # assume cap is bigger than len(self.data)
        temp = [None]*cap
        i = self.front
        j = 0
        for x in range(len(self.data)):
            temp[j] = self.data[i]
            j = j + 1
            i = (i + 1)%len(self.data)
        self.data = temp
        self.front = 0

    def enqueue(self,x):
        if self.size == len(self.data):
            self.resizeUp(2*len(self.data))
        else:
            back = (self.front + self.size)%len(self.data)  # back points to empty space AFTER last item
            self.data[back] = x
            self.size = self.size + 1

    def __str__(self):
        return str(self.data) + " front = " + str(self.front) + " size = " + str(self.size)

q1 = Queue()
for i in range(8):
    q1.enqueue(i)
print(q1)
for i in range(8,15):
    q1.enqueue(i)
print(q1)

[0, 1, 2, 3, 4, 5, 6, 7, None, None] front = 0 size = 8
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, None, None, None, None, None, None] front = 0 size = 14

class Node():
    
    def __init__(self,n,p,a,x):
        self.name = n
        self.phone = p
        self.address = a
        self.next = x
    
    def __str__(self):
        return "(" + self.name + "," + self.phone + "," + self.address + ")"

# unsorted linked list (name serves as KEY)
class ContactsLL():

    def __init__(self):
        self.head = Node("","","",None)
        self.size = 0
    
    # find an entry for a name
    # return pointer to previous node where you find name; else return None
    # nice pattern of code; commonly used
    def find(self,n):
        p = self.head
        found = False
        while (p.next != None) and not found:
            if p.next.name == n:
                found = True
            else:
                p = p.next
        if found:
            return p
        else:
            return None
     
    # insert new entry; return True if success else False
    def insert(self,n,p,a):
        position = self.find(n)
        if position == None:
            node = Node(n,p,a,self.head.next)
            self.head.next = node
            self.size = self.size + 1
            return True
        else:
            return False

    # delete entry for name
    def delete(self,n):
        position = self.find(n)
        if position != None:
            position.next = position.next.next
            self.size = self.size - 1
            return True
        else:
            return False
        
    # update phone and/or address
    def update(self,n,p,a):
        position = self.find(n)
        if position != None:
            position.next.phone = p
            position.next.address = a
            return True
        else:
            return False
    
    def __str__(self):
        result = "**********\n"
        p = self.head
        for i in range(self.size):
            result = result + str(p.next) + "\n"
            p = p.next
        return result + "**********\n"

contacts = ContactsLL()
contacts.insert("John","111","123 main street")
print(contacts)
contacts.insert("Alice","112","124 main street")
print(contacts)
contacts.insert("Beth","113","125 main street")
print(contacts)

**********
(John,111,123 main street)
**********

**********
(Alice,112,124 main street)
(John,111,123 main street)
**********

**********
(Beth,113,125 main street)
(Alice,112,124 main street)
(John,111,123 main street)
**********