数据结构 03 双向队列

双向队列

它是一种混合线性数据结构, 涵盖Stack和Queue的全部能力.

# -.- coding:utf-8 -.-
from __future__ import print_function


def checker(func):

    def wrapper(self, *args, **kwargs):
        if self.empty():
            return self.items
        return func(self, *args, **kwargs)

    return wrapper


class Deque(object):

    """
    Deuque: 双向队列

    它是一种混合线性数据结构, 涵盖Stack和Queue的全部能力.
    """

    def __init__(self):
        self.items = []

    def size(self):
        """获取栈元素总数."""
        return len(self.items)

    def empty(self):
        """栈为空则返回: True ; 栈非空返回: False"""
        return not self.size()

    def append(self, item):
        self.items.append(item)
        return self.items

    def insert(self, item):
        self.items.insert(0, item)
        return self.items

    @checker
    def __leftpop(self):
        return self.items.pop(0)

    @checker
    def __rightpop(self):
        return self.items.pop(-1)

    def get(self):
        return self.__leftpop()

    def rightget(self):
        return self.__rightpop()

    @checker
    def peek(self):
        return self.items[0]

    @checker
    def rightpeek(self):
        return self.items[-1]

    def __iter__(self):
        return self

    def __next__(self):
        if not self.empty():
            return self.get()
        raise StopIteration

    def next(self):
        return self.__next__()

    def __str__(self):
        return "{}".format(self.items)


if __name__ == '__main__':
    deque = Deque()

    # 插入测试数据
    deque.append("a")
    deque.append("b")
    deque.append("c")
    deque.insert("x")
    deque.insert("y")
    deque.insert("z")

    # 测试功能
    print("查看双向队列: ", deque)
    print("获取头元素(不移除元素): ", deque.peek())
    print("查看双向队列: ", deque)
    print("获取头元素(移除元素): ", deque.get())
    print("查看双向队列: ", deque)
    print("获取尾元素(不移除元素): ", deque.rightpeek())
    print("查看双向队列: ", deque)
    print("获取尾元素(移除元素): ", deque.rightget())
    print("查看双向队列: ", deque)

    # 遍历栈对象
    for enum, i in enumerate(deque):
        print("遍历第{}个元素: ".format(enum), i)

    # 输出结果
    # 查看双向队列:  ['z', 'y', 'x', 'a', 'b', 'c']
    # 获取头元素(不移除元素):  z
    # 查看双向队列:  ['z', 'y', 'x', 'a', 'b', 'c']
    # 获取头元素(移除元素):  z
    # 查看双向队列:  ['y', 'x', 'a', 'b', 'c']
    # 获取尾元素(不移除元素):  c
    # 查看双向队列:  ['y', 'x', 'a', 'b', 'c']
    # 获取尾元素(移除元素):  c
    # 查看双向队列:  ['y', 'x', 'a', 'b']
    # 遍历第0个元素:  y
    # 遍历第1个元素:  x
    # 遍历第2个元素:  a
    # 遍历第3个元素:  b