typedef struct {
 PyObject_VAR_HEAD
 /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
 PyObject **ob_item;

 /* ob_item contains space for 'allocated' elements. The number
  * currently in use is ob_size.
  * Invariants:
  *  0 <= ob_size <= allocated
  *  len(list) == ob_size
  *  ob_item == NULL implies ob_size == allocated == 0
  * list.sort() temporarily sets allocated to -1 to detect mutations.
  *
  * Items must normally not be NULL, except during construction when
  * the list is not yet visible outside the function that builds it.
  */
 Py_ssize_t allocated;
} PyListObject;

class my_stack(object):
 def __init__(self, value):
  self.value = value
  # 前驱
  self.before = None
  # 后继
  self.behind = None

 def __str__(self):
  return str(self.value)


def top(stack):
 if isinstance(stack, my_stack):
  if stack.behind is not None:
   return top(stack.behind)
  else:
   return stack


def push(stack, ele):
 push_ele = my_stack(ele)
 if isinstance(stack, my_stack):
  stack_top = top(stack)
  push_ele.before = stack_top
  push_ele.before.behind = push_ele
 else:
  raise Exception('不要乱扔东西进来好么')


def pop(stack):
 if isinstance(stack, my_stack):
  stack_top = top(stack)
  if stack_top.before is not None:
   stack_top.before.behind = None
   stack_top.behind = None
   return stack_top
  else:
   print('已经是栈顶了')

class MyQueue():
 def __init__(self, value=None):
  self.value = value
  # 前驱
  # self.before = None
  # 后继
  self.behind = None

 def __str__(self):
  if self.value is not None:
   return str(self.value)
  else:
   return 'None'


def create_queue():
 """仅有队头"""
 return MyQueue()


def last(queue):
 if isinstance(queue, MyQueue):
  if queue.behind is not None:
   return last(queue.behind)
  else:
   return queue


def push(queue, ele):
 if isinstance(queue, MyQueue):
  last_queue = last(queue)
  new_queue = MyQueue(ele)
  last_queue.behind = new_queue


def pop(queue):
 if queue.behind is not None:
  get_queue = queue.behind
  queue.behind = queue.behind.behind
  return get_queue
 else:
  print('队列里已经没有元素了')

def print_queue(queue):
 print(queue)
 if queue.behind is not None:
  print_queue(queue.behind)

class LinkedList():
 def __init__(self, value=None):
  self.value = value
  # 前驱
  self.before = None
  # 后继
  self.behind = None

 def __str__(self):
  if self.value is not None:
   return str(self.value)
  else:
   return 'None'


def init():
 return LinkedList('HEAD')


def delete(linked_list):
 if isinstance(linked_list, LinkedList):
  if linked_list.behind is not None:
   delete(linked_list.behind)
   linked_list.behind = None
   linked_list.before = None
  linked_list.value = None