栈
栈Stack
是一种线性的数据结构,FILO
(先进后出)的操作,可以用顺序表实现,也可以用链表来实现。
操作
栈的基本操作包含:⬇️
- stack():创建空的栈
- push():入栈
- pop():出栈
- peek():返回栈顶元素
- is_empty():判断是否为空栈
- size():返回栈的元素个数
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
|
class (object): """Stack""" def __init__(self): self.__list = [] def push(self, item): self.__list.append(item) def pop(self): return self.__list.pop() def peek(self): if self.__list: return self.__list[-1] else: return None def size(self): return len(self.__list) def is_empty(self): return self.__list == [] if __name__ == "__main__": s = Stack() s.push(1) s.push(2) s.push(3) s.push(4) s.push(5) print(s.pop()) print(s.pop()) print(s.pop()) print(s.pop()) print(s.pop())
|
5
4
3
2
1
队列
概念
队列queue
也是一种线性结构,方式是先进先出FIFO
, 想象成一支队伍。
- 允许插入数据的一端:队尾
- 允许删除的一端:队头
假设队列$q=(a_1, a_2 ,…, a_n)$,则$a_1$是队头元素,$a_n$是队尾元素。删除从$a_1$开始,添加从$a_n$开始
操作
几个重要的操作
- enqueue():插入元素
- dequeue():删除元素
- is_empty():判断是否为空
- size():返回元素个数
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
|
class Queue(object): def __init__(self): self.__list = [] def enqueue(self, item): self.__list.append(item) def dequeue(self): return self.__list.pop(0) def is_empty(self): return self._list == [] def size(self): return len(self.__list) if __name__ == "__main__": q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) print(q.dequeue()) print(q.dequeue()) print(q.dequeue()) print(q.dequeue()) print(q.dequeue())
|
1
2
3
4
5
双端队列
概念
能够在队头和队尾同时进行插入和删除操作的队列
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
|
class Dueue(object): def __init__(self): self.__list = [] def add_front(self, item): self.__list.insert(0, item) def add_rear(self, item): self.__list.append(item) def pop_front(self): return self.__list.pop(0) def pop_rear(self): return self.__list.pop() def is_empty(self): return self._list == [] def size(self): return len(self.__list) if __name__ == "__main__": q = Dueue() q.add_front(1) q.add_front(2) q.add_front(3) q.add_rear(4) q.add_rear(5) q.add_rear(6) print(q.pop_front()) print(q.pop_front()) print(q.pop_front()) print(q.pop_rear()) print(q.pop_rear()) print(q.pop_rear())
|
3
2
1
6
5
4
Stay Foolish Stay Hungry
近期评论