04-顺序

顺序反映数据的进出问题，分为先进先出（队列），后进先出（栈），以及能控制进出的双端队列。

1. 什么是顺序

数据的顺序关乎数据的提取方式，分为先进后出（队列问题）、后进先出（栈）、控制进出（双端队列）。可结合排队购物（队列）、玩具枪弹夹（栈）进行理解。

2. 优缺点

根据具体的业务情况，选择不同的顺序方式，有利于提高数据提取速度。

3. 代码

3.1 队列

class Array():
   def __init__(self, size=4):
       self.__size = size  # 记录容器大小
       self.__item = [None] * size  # 分配空间
       self.__length = 0

   def __setitem__(self, key, value):
       self.__item[key] = value
       self.__length += 1

   def __getitem__(self, key):
       return self.__item[key]

   def __len__(self):
       return self.__length

   def __iter__(self):
       for value in self.__item:
           yield value


class Queue():
   def __init__(self, size=4):
       self.item = Array(size)
       self.size = size
       # 先进先出
       self.head = 0
       self.end = 0

   def put(self, value):
       self.item[self.head % self.size] = value
       self.head += 1

   def pop(self):
       temp = self.item[self.end % self.size]
       self.end += 1
       return temp

3.2 栈

class Array():
    def __init__(self, size=4):
        self.__size = size  # 记录容器大小
        self.__item = [None] * size  # 分配空间
        self.__length = 0

    def __setitem__(self, key, value):
        self.__item[key] = value
        self.__length += 1

    def __getitem__(self, key):
        return self.__item[key]

    def __len__(self):
        return self.__length

    def __iter__(self):
        for value in self.__item:
            yield value


class Stack():
    def __init__(self, size=4):
        self.item = Array(size)
        self.size = size
        self.head = 0

    def put(self, value):
        self.item[self.head % self.size] = value
        self.head += 1

    def pop(self):
        self.head -= 1
        temp = self.item[self.head % self.size]
        return temp

3.3 双端队列

from collections import deque


class Stack():
    def __init__(self):
        self.item = deque()

    def put(self, value):
        self.item.append(value)

    def pop(self):
        return self.item.pop()

    def pop_reverse(self):
        return self.item.popleft()