## STACK IMPLEMENTATION (simple list implementation)
## Stack.py
class Stack:
    
    def __init__(self):
        self._data = []  # first item is bottom; last item is top
        
    def is_empty(self):
    # returns True for an empty stack False otherwise
        return len(self._data) == 0
    
    def size(self):
    # returns size of the stack; i.e. number of elements in stack
        return len(self._data)
        
    def push(self,e):
    # add item e to top of stack
    # no error check for FULL stack because we are assuming
    # "unlimited" Python list
        self._data.append(e)
        
    def pop(self):
    # remove AND return the top item on stack
        if not self.empty():
            x = self._data[-1]
            self._data = self._data[0:len(self._data)-1]
            return x
        else:
            return None
        
    def top(self):
    # return the top item on stack
        if not self.empty():
            return self._data[-1]
        else:
            return None

    def __str__(self):
        #result = "BOTTOM "
        #for x in self._data:
        #    result = result + str(x) + " "
        #result = result + "TOP"
        #return result
        result = ""
        for i in range(-1,-len(self._data)-1,-1):
            result = result + str(self._data[i]) + "\n"
        result = result + "-BOTTOM-\n"
        return result

s1 = Stack()
print(s1)
s1.push(10)
print(s1)
s1.push(20)
print(s1)
s1.push(30)
print(s1)
#x = s1.pop()
#print(x,s1)
s2 = Stack()
s2.push("John")
s2.push("Alice")
print(s2)
print(s1.size())
print(s2.size())
str(s1)

-BOTTOM-

10
-BOTTOM-

20
10
-BOTTOM-

30
20
10
-BOTTOM-

Alice
John
-BOTTOM-

3
2

'30\n20\n10\n-BOTTOM-\n'

xs = [1,2,3,4,5,6]
xs[0:len(xs)-1]
str(xs)

'[1, 2, 3, 4, 5, 6]'

str({'a':10,'b':20})

"{'a': 10, 'b': 20}"

print(30)

BOTTOM 10 20 30 TOP

30
20
10
-BOTTOM-

x = [1,2,3]
x.reverse()
x

[3, 2, 1]

xs = [1,2,3,4]
for x in range(-1,-len(xs)-1,-1):
    print(x)

-1
-2
-3
-4

xs[-4]

1

# Circular List Implementation of a Queue
class Queue:
    
    CAPACITY = 10
    
    def __init__(self):
        self._data = [None]*Queue.CAPACITY
        self._front = 0
        self._size = 0
    
    def is_empty(self):
        return self._size == 0
    
    def first(self):
        if self.is_empty():
            return None
        else:
            return self._data[self._front]
    
    def size(self):
        return self._size
    
    def dequeue(self):
    # returns AND removes item from front of queue
        if self.is_empty():
            return None
        else:
            x = self._data[self._front]
            self._data[self._front] = None
            self._front = (self._front + 1)%len(self._data)
            self._size = self._size - 1
            return x
    
    def enqueue(self,e):
        # adds e to end of queue
        if self._size == len(self._data):
            self.resizeUp(2*len(self._data))
        # back = front + size %
        back = (self._front + self._size)%len(self._data)
        self._data[back] = e
        self._size = self._size + 1
        
    def resizeUp(self,cap):
        #Step 1 Create a new bigger list of None
        temp = [None]*cap
        #Step 2: Transfer all items from self._data into temp
        i = self._front
        j = 0
        for x in range(self._size):
            temp[j] = self._data[i]
            i = (i+1)%len(self._data)
            j = (j+1)%len(temp)
        self._data = temp
        self._front = 0
    
    def __str__(self):
        return str(self._data)

[None]*10

[None, None, None, None, None, None, None, None, None, None]

q1 = Queue()
q1.enqueue(10)
q1.enqueue(20)
q1.enqueue(30)
print(q1)

[10, 20, 30, None, None, None, None, None, None, None]

q1.dequeue()
print(q1)

[None, 20, 30, None, None, None, None, None, None, None]

q1._front

1