栈
栈的特点是只允许在一端进行操作，按照后进先出（LIFO, Last In First Out）的原理。它可以用顺序表实现，也可以用链表的方式实现。
栈顶：可以进行数据操作的一端叫做栈顶。
栈底：不能进行数据操作的一段叫做栈底。
入栈：向栈里进行添加数据
出栈：将数据从栈里取出来
栈的结构
栈的主要操作
- stack() 创建一个新的空栈
- push(item) 添加一个新的元素item到栈顶
- pop() 弹出栈顶元素
- peek() 返回栈顶元素
- is_empty() 判断栈是否为空
- size() 返回栈的元素个数
python实现
#_*_coding:utf-8_*_
#栈类
class Stack(object):
def __init__(self):
self.__list = []
def push(self,item):
'''添加一个新的元素item到栈顶
注意这里对python list进行添加元素操作时也可以用insert,
但是考虑到时间复杂度，我们这里用append比较好
因为insert时间复杂度为O(n), append为O(1)
'''
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.pop())
print(s.pop())
print(s.pop())
print(s.pop())
output:
4
3
2
1
