栈
栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。
栈结构实现
栈可以用顺序表实现，也可以用链表实现。
栈的操作
- Stack() 创建一个新的空栈
- push(item) 添加一个新的元素item到栈顶
- pop() 弹出栈顶元素
- peek() 返回栈顶元素
- is_empty() 判断栈是否为空
- size() 返回栈的元素个数
线性表都可以用来实现栈，栈只是一个容器，这里我们就用简单的顺序表来实现栈，python中的顺序表有哪几种呢，我们直接用list来实现吧。
class Stack(object):
'''栈'''
def __init__(self):
self.__list = []#首先建立这个容器
def push(self,item):
#添加一个新的元素item到栈顶，也就是压栈
return 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 is_empty(self):
#判断栈是否为空
return self.__list == []
def size(self):
return len(self.__list)
if __name__ == '__main__':
s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.push(4)
print(s.size())
print(s.peek())
print(s.pop())
print(s.pop())
print(s.pop())
print(s.pop())
为什么我们使用从尾部取元素和压栈呢，因为尾部的时间复杂度为O(1)，而如果是从头部进行取元素和压栈，所需要的时间复杂度就是O(n)。
输出如下：
4
4
4
3
2
1
说完了这个，说一下队列的问题。
队列
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列的实现
同栈一样，队列也可以用顺序表或者链表实现。
操作
- Queue() 创建一个空的队列
- enqueue(item) 往队列中添加一个item元素
- dequeue() 从队列头部删除一个元素
- is_empty() 判断一个队列是否为空
- size() 返回队列的大小
class Queue(object):
'''队列'''
def __init__(self):
self.__list = []
def enqueue(self,item):
'''往队列中添加一个item元素'''
return self.__list.append(item)
#return self.__list.insert(0,item)
def dequeue(self):
'''从队列头部删除一个元素'''
return self.__list.pop(0)
#return self.__list.pop() pop()没参数默认是队尾
def is_empty(self):
'''判断一个队列是否为空'''
return self.__list == []
def size(self):
'''返回队列的大小'''
return len(self.__list)
if __name__ == '__main__':
s = Queue()
s.enqueue(1)
s.enqueue(2)
s.enqueue(3)
s.enqueue(4)
print('*'*20)
print(s.dequeue())
print(s.dequeue())
print(s.dequeue())
print(s.dequeue())
因为涉及到两个通道，一头压栈，一头出栈，所以总会有一头的时间复杂度是O(n)，一个是O(1)。
输出结果如下：
********************
1
2
3
4
双端队列
双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。
网友评论