栈和队列
一、栈
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 == -1if __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 = Noneclass 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 -= 1if __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 = elemclass 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 Listif __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())