python常用的数据结构3-双端队列

2019-03-11
本博客所有文章采用的授权方式为 自由转载-非商用-非衍生-保持署名 ，转载请务必注明出处，谢谢。

声明： 本博客欢迎转发，但请保留原作者信息!
github地址：atanx
新浪微博：@蜀山掌门V
QQ：365039667
博客地址：江斌的博客
内容仅供学习参考，如有不当引用，请告知博主。

什么是双端队列

队列是一种先进先出(FIFO)的数据结构。

双端队列的抽象数据类型

  1. Q.add_first(e) # 向双端队列前面添加一个元素e
  2. Q.add_last(e) # 向双端队列后面添加一个元素e
  3. Q.delete_first() # 头部移除并返回一个元素，若为空触发一个错误
  4. Q.delete_last() # 尾部移除并返回一个元素，若为空触发一个错误
  5. D.first()
  6. D.last()
  7. D.is_empty() # 判断双端队列是否为空
  8. len(Q) # 返回队列长度

双端队列的Python实现

#!/usr/bin/env python
# coding=utf-8
#
# Copyright 2019, Bin Jiang
#
# 实现队列数据结构

from pyds.error import EmptyError
from collections import deque


class Deque(object):
	def __init__(self):
		self._deque = deque()

	def add_first(self, e):
		""" 头部添加一个元素 """
		self._deque.appendleft(e)

	def add_last(self, e):
		""" 尾部添加一个元素 """
		self._deque.append(e)

	def delete_first(self):
		""" 头部移除一个元素 """
		if self.is_empty():
			raise EmptyError('deque is empty')
		return self._deque.popleft()

	def delete_last(self):
		""" 尾部移除一个元素 """
		if self.is_empty():
			raise EmptyError('deque is empty')
		return self._deque.pop()

	def first(self):
		""" 访问第一个元素 """
		return self._deque[0]

	def last(self):
		""" 访问最后一个元素 """
		return self._deque[-1]

	def __len__(self):
		return len(self._deque)

	def is_empty(self):
		""" 判断双端队列是否为空 """
		return len(self._deque) == 0

章节列表