# In computer science what is a dictionary?
# It's a dynamic set that only supports:
# 1. insertion
# 2. deletion
# 3. membership test.

# There are other types of Dynamic sets. Some of the operations that other dynamic sets may support are:
# 1. Search(S, k):     A query that, given a set S and a key value k, returns a pointer x to an element
#                      in S such that x.key= k, or NIL if no such element belongs to S.
# 2. Insert(S,x)
# 3. Deletion
# 4. Minimum(S):       A query on a totally ordered set S that returns a pointer to the element of S with the smallest key.
# 5. Maximum(S):       opposite of Minimum(S)
# 6. Successor(S,x):   A query that, given an element x whose key is from a totally ordered set S,
#                      returns a pointer to the next larger element in S, or NIL if x is the maximum element.
# 7. PREDECESSOR(S,x): opposite of Successor(S,x)


# Stack implements LIFO policy.
class Stack:
    d: list = []

    def empty(self):
        """
        Returns whether the stack is empty – Time Complexity : O(1)
        """
        if self.top() == 0:
            return True
        return False

    def top(self):
        """
        This is the index of the most recently added element – Time Complexity : O(1)
        """
        return len(self.d)

    def size(self):
        """Returns the size of the stack – Time Complexity : O(1)"""
        return len(self.d)

    def push(self, x):
        """Adds the element ‘g' at the top of the stack – Time Complexity : O(1)"""
        self.d.append(x)

    def pop(self):
        """Deletes the top most element of the stack – Time Complexity : O(1)"""
        return self.d.pop()


s = Stack()
if s.top() != 0:
    raise Exception(
        """The `stack` algo didnt work.
        \ngot = {}. \nexpected = {}.""".format(
            s.top(), 0
        )
    )
if s.empty() is not True:
    raise Exception(
        """The `stack` algo didnt work.
        \ngot = {}. \nexpected = {}.""".format(
            s.empty(), True
        )
    )

s.push(34)
s.push(1)
s.push(54)
s.push(358_763_524)
if s.top() != 4:
    raise Exception(
        """The `stack` algo didnt work.
        \ngot = {}. \nexpected = {}.""".format(
            s.top(), 4
        )
    )

if s.pop() != 358_763_524:
    raise Exception(
        """The `stack` algo didnt work.
        \ngot = {}. \nexpected = {}.""".format(
            s.pop(), 358_763_524
        )
    )


# Queue implements FIFO policy.
class Queue:
    d: list = []

    def enqueue(self, x):
        self.d.append(x)

    def dequeue(self):
        return self.pop(0)