作者:whisper
链接:http://proprogrammar.com:443/article/571
声明:请尊重原作者的劳动,如需转载请注明出处
前几天说了java中的LinkedList作为栈和队列(双端队列)使用的情况:说说java中的LinkedList及其在算法中的应用
今天来说说python中的list和deque实现栈和队列(双端队列)的功能。
Python 是由 Guido van Rossum 在八十年代末和九十年代初,在荷兰国家数学和计算机科学研究所设计出来的。
Python 本身也是由诸多其他语言发展而来的,这包括 ABC、Modula-3、C、C++、Algol-68、SmallTalk、Unix shell 和其他的脚本语言等等。
像 Perl 语言一样,Python 源代码同样遵循 GPL(GNU General Public License)协议。
现在 Python 是由一个核心开发团队在维护,Guido van Rossum 仍然占据着至关重要的作用,指导其进展。
Python 2.0 于 2000 年 10 月 16 日发布,增加了实现完整的垃圾回收,并且支持 Unicode。
Python 3.0 于 2008 年 12 月 3 日发布,此版不完全兼容之前的 Python 源代码。不过,很多新特性后来也被移植到旧的Python 2.6/2.7版本。
Python 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。
Python 2.7 被确定为最后一个 Python 2.x 版本,它除了支持 Python 2.x 语法外,还支持部分 Python 3.1 语法。
python实现栈的功能非常简单,直接使用list.append,list.pop函数就可以完成入栈、出栈的功能,再使用len(list)可以对栈进行判空,确定栈大小,使用list[len(list)-1]可以查看栈顶元素,这样就简单的实现了一个栈的基本功能。
stack = [] #[]
stack.append(1) #[1]
stack.append(2) #[1,2]
stack.pop() #[1]
print("length: " + len(stack)) #length: 1
if(len(stack) == 0):
print("empty")
else:
print("not empty")
print("top: " + stack[len(stack) - 1])
# not empty
# top: 1
python能通过deque(list)将一个列表转化为双端队列,当然也可以直接定义deque而不使用list,双端队列也可以作为栈、队列使用,作为栈使用只要从双端队列的一端入、出即可,作为队列使用只要从双端队列的一端入,另一端出即可。
获取了一个deque,可以使用deque.popleft,deque.appendleft从队列的左边出队,入队,使用deque.pop,deque.append从队列的右边出队,入队,使用len(deque)获取队列大小及判空,使用deque[0],deque[len(deque) - 1]查看队列两端的元素
deque = deque([1,2]) #deque()
#实现栈
deque.append(3) #[1,2,3]
deque.pop() #[1,2]
#实现队列
deque.appendleft(4) #[4,1,2]
deque.pop() #[4,1]
'''
deque.append(3) #[4,1,3]
deque.popleft() #[1,3]
'''
#实现双端队列
deque.append(3) #[1,3,3]
deque.appendleft(4) #[4,1,3,3]
deque.pop() #[4,1,3]
deque.popleft() #[1,3]
print(len(deque)) #2
if(len(deque) == 0):
print("empty")
else:
print("not empty") #not empty
print("left: " + deque[0]) #left: 1
print("right: " + deque[len(deque) - 1]) #right: 3
亲爱的读者:有时间可以点赞评论一下
全部评论