栈和队列
一、栈
1.栈的定义
栈又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
实现栈的顺序存储结构(常用)
#栈的顺序存储结构
class SeqStack(object):
def __init__(self,size):
self.data = list(None for _ in range(size))
self.max_size = size
self.top = -1
def get_length(self):
return self.top + 1
def push(self,elem):
#进栈
if self.top + 1 == self.max_size:
raise IndexError('Stack is full')
else:
self.top += 1
self.data[self.top] = elem
def pop(self):
#出栈
if self.top == -1:
raise IndexError('Stack is empty')
else:
self.top -= 1
return self.data[self.top + 1]
def get_top(self):
if self.top == -1:
raise IndexError("Stack is empty")
else:
return self.data[self.top]
def show_stack(self):
j = self.top
while j >= 0:
print(self.data[j])
j -= 1
def is_empty_stack(self):
return self.top == -1
if __name__ == '__main__':
s = SeqStack(10)
s.push(11)
s.push(22)
s.push(33)
s.show_stack()
print('===========')
print(s.get_top())
print(s.get_length())
实现栈的链式存储结构
#栈的链式存储结构
class Node(object):
def __init__(self,data=None):
self.data = data
self.next = None
class LKStack(object):
def __init__(self):
self.top = Node(None)
self.count = 0
def get_length(self):
return self.count
def get_top(self):
return self.top.data
def is_empty(self):
return self.count == 0
def push(self,elem):
tmp = Node(elem)
if self.is_empty():
self.top = tmp
else:
tmp.next = self.top
self.top = tmp
self.count += 1
def pop(self):
if self.is_empty():
raise IndexError('Stack is empty')
else:
self.count -= 1
elem = self.top.data
self.top = self.top.next
return elem
def show_stack(self):
if self.is_empty():
raise IndexError('Satck is empty')
else:
j = self.count
tmp = self.top
while j > 0 and tmp:
print(tmp.data)
tmp = tmp.next
j -= 1
if __name__ == '__main__':
s = LKStack()
s.push(11)
s.push(22)
s.push(33)
s.push(44)
s.show_stack()
print('================')
print(s.get_length())
s.pop()
print(s.get_top())
二、队列
定义:队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
链表实现队列:头部删除和查看O(1),尾部删除O(1)
#链表实现队列 class Node(object): def __init__(self,elem=None): self.next = None self.elem = elem class Queue(object): def __init__(self): self.head = None self.rear = None def isEmpty(self): return self.head is None def peek(self): if self.isEmpty(): return None return self.head.elem def enqueue(self,elem): n = Node(elem) if self.head == None: self.head = n self.rear = self.head else: self.rear.next = n self.rear = n def dequeue(self): if self.head == None: return None else: tmp = self.head.elem self.head = self.head.next return tmp def allDequeue(self): List = [] while self.head != None: List.append(self.head.elem) self.head = self.head.next return List if __name__ == '__main__': q = Queue() q.enqueue(11) q.enqueue(13) q.enqueue(14) q.enqueue(15) print(q.peek()) print(q.dequeue()) print(q.allDequeue())