什么是栈和队列

什么是栈

栈是一种线性数据结构，栈中的元素只能先入后出，最早进入的元素存放的位置叫做栈底，最后进入的元素存放的位置叫做栈顶。

栈的基本操作-入栈、出栈

入栈：入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶
出栈：出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶

什么是队列

队列是一种线性数据结构，队中的元素只能先入先出（FIFO），队列的出口端叫作队头，队列的入口端叫作队尾

队列的基本操作-入队、出队

入队：就是把新元素放入队中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾

出队：就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头

实现队列入队出队功能

class MyQueue:
    def __init__(self, capacity):
        self.list = [None] * capacity
        self.front = 0
        self.rear = 0
    def enqueue(self, element):
        """入队"""
        # (队尾下标+1)%数组长度 = 队头下标
        if (self.rear + 1) % len(self.list) == self.front:
            raise Exception("队列已满！！")
        self.list[self.rear] = element
        self.rear = (self.rear + 1) % len(self.list)
    def dequeue(self):
        """出队"""
        if self.rear == self.front:
            raise Exception("队列已满！！")
        dequeue_element = self.list[self.front]
        self.front = (self.front + 1) % len(self.list)
        return dequeue_element
    def output(self):
        i = self.front
        while i != self.rear:
            print(self.list[i])
            i = (i+1) % len(self.list)
if __name__ == '__main__':
    myQueue = MyQueue(6)
    myQueue.enqueue(3)
    myQueue.enqueue(4)
    myQueue.enqueue(5)
    myQueue.dequeue()
    myQueue.output()

栈和队列的应用

双端队列 ：双端队列，综合了栈和队列的优点，从队头一端可以入队或出队，从队尾一端也可以入队或出队
优先队列：谁优先级最高，谁先出队