#Stack Implementation
class Stack:
  def __init__(self):
    self.data = []
  def __len__(self):
    return len(self.data)
  def is_empty(self):
    return len(self.data) == 0
  def push(self, val):
    self.data.append(val)
  def top(self):
    if self.is_empty():
      print("Stack is empty")
     else:
      return self.data[-1]
  def pop(self):
    if self.is_empty():
      print("Stack is empty")
    else:
      return self.data.pop()
  def display(self):
    print(self.data)

S = Stack()
print(S.is_empty())
S.push(5)
S.display()
S.push(3)
S.display()
S.push(6)
S.display()
print(S.is_empty())
print(len(S))
print(S.top())
S.pop()
S.display()
print(S.top())
S.pop()
S.display()

#Queue Implementation
class Queue:
  def __init__(self):
    self.data = []
  def __len__(self):
    return len(self.data)
  def is_empty(self):
    return len(self.data) == 0
  def enqueue(self, val):
    self.data.append(val)
  def first(self):
    if self.is_empty():
      print("Queue is empty")
    else:
      return self.data[0]
  def dequeue(self):
    if self.is_empty():
      print("Queue is empty")
    else:
      return self.data.pop(0)
  def display(self):
    print(self.data)
Q = Queue()
print(Q.is_empty())
Q.enqueue(5)
Q.display()
Q.enqueue(3)
Q.display()
Q.enqueue(6)
Q.display()
print(Q.is_empty())
print(len(Q))
print(Q.first())
Q.dequeue()
Q.display()
print(Q.first())
Q.dequeue()
Q.display()

#Stack Using Two Queues
class Queue:
  def __init__(self):
    self.data = []
  def __len__(self):
    return len(self.data)
  def is_empty(self):
    return len(self.data) == 0
  def enqueue(self, val):
    self.data.append(val)
  def first(self):
    if self.is_empty():
      print("Queue is empty")
    else:
      return self.data[0]
  def dequeue(self):
    if self.is_empty():
      print("Queue is empty")
    else:
      return self.data.pop(0)
  def display(self):
    print(self.data)

class StackUsingQueues:
  def __init__(self):
    self.Q1 = Queue()
    self.Q2 = Queue()

  def __len__(self):
    return len(self.Q1)

  def is_empty(self):
    return self.Q1.is_empty()

  def push(self, val):
    self.Q2.enqueue(val)
    while not self.Q1.is_empty():
      self.Q2.enqueue(self.Q1.dequeue())
    self.Q1, self.Q2 = self.Q2, self.Q1
  def pop(self):
    return self.Q1.dequeue()
  def top(self):
    return self.Q1.first()
  def display(self):
    self.Q1.display()
S = StackUsingQueues()
print(S.is_empty())
S.push(5)
S.display()
S.push(3)
S.display()
S.push(6)
S.display()
print(S.is_empty())
print(len(S))
print(S.top())
S.pop()
S.display()
print(S.top())
S.pop()
S.display()

#Balanced Parenthesis Using Stack
class Stack:
  def __init__(self):
    self.data = []
  def is_empty(self):
    return len(self.data) == 0
  def push(self, val):
    self.data.append(val)
  def pop(self):
    if self.is_empty():
      print("Stack is empty")
    else:
      return self.data.pop()
expr = "{(5+x)-[y+z]}"
left = "([{"
right = ")]}"
S = Stack()
f = 1
for c in expr:
  if c in left:
    S.push(c)
  elif c in right:
    if S.is_empty() or right.index(c) != left.index(S.pop()):
      f = 0
      break
if f == 1 and S.is_empty():
  print("Balanced Parenthesis")
else:
  print("Unbalanced Parenthesis")