class LinkStack():
def __init__(self):
self.head = None #链表的头作为栈顶
self.length = 0
def isEmpty(self):
return self.head is None
def size(self):
return self.length
def peek(self):#O(1)
return self.head.getData()
def push(self,item):#O(1)
top = Node(item)
top.setNext(self.head)
self.head = top
self.length += 1
def pop(self):#O(1)
top_item = self.head.getData()
self.head = self.head.getNext()
self.length -= 1
return top_item
class LinkQueue():
def __init__(self):
self.head = None #链表头作为队列的头
self.tail = None #链表尾作为队列的尾
self.length = 0
def isEmpty(self):
return self.head is None
def size(self):
return self.length
def enqueue(self,item):
tail = Node(item)
if self.head is None:
#第一个入队
self.head = self.tail = tail
else :
self.tail.setNext(tail)
self.tail = self.tail.getNext()
self.length += 1
def dequeue(self):#O(1)
top_item = self.head.getData()
if self.head == self.tail:
#唯一一个出队
self.head = self.tail = None
else:
self.head = self.head.getNext()
self.length -= 1
return top_item