队列和栈的实现

本节讲解的队列与栈，如果你对之前的线性和链式结构顺利掌握了，那么下边的队列和栈就小菜一碟了。因为我们会用前两节讲到的东西来实现队列和栈。 之所以放到一起讲是因为这两个东西很类似，队列是先进先出结构(FIFO, first in first out)， 栈是后进先出结构(LIFO, last in first out)。

一，队列

队列（Queue）是计算机科学中一种基础的数据结构，它遵循先进先出（First In First Out, FIFO）的原则，即最早进入队列的元素也将是最先离开队列的元素。这个概念类似于现实生活中的排队场景，比如在超市结账，先到达收银台的顾客会先完成结账离开。

1.线式队列

线式队列就是线性表+队列性质组成的数据结构

代码实现

class Array():
    def __init__(self,size):
        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, index):
        return self.__item[index]

    def __len__(self):
        return self.__length

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

class Linear_Queue():
    def __init__(self,size=4):
        self.size = size
        self.items = Array(size)
        self.head = 0
        self.end = 0
    def push(self,value):
        self.items[self.head % self.size] = value
        self.head += 1
    def pop(self):
        temp = self.items[self.end % self.size]
        self.end += 1
        return temp

if __name__ == '__main__':
    lq = Linear_Queue()
    lq.push(11)
    lq.push(12)
    lq.push(13)
    lq.push(14)
    print(lq.pop())
    print(lq.pop())
    print(lq.pop())
    print(lq.pop())

2.链式队列

链式队列就是链表+队列性质组成的数据结构

代码实现

class Node():
    def __init__(self,value=None,prev=None,next=None):
        self.value = value
        self.next = next
        self.prev = prev
    def __str__(self):
        return "Node:{}".format(self.value)

class DoubleLinkedList():
    def __init__(self):
        self.size = 0
        self.root = Node()
        self.end = None

    def append(self,value):
        node = Node(value=value)
        #无节点
        if not self.end:
            self.root.next = node  # root节点指向新节点
            node.prev = self.root#新节点指向根节点
            self.end = node#末节点指针指向新节点


        #有节点
        else:
            self.end.next = node#末节点指向新节点
            node.prev = self.end  # 新节点指向末节点
            self.end = node#末节点移动到新节点
        self.size += 1

    def append_first(self,value):
        node = Node(value=value)
        #无节点
        if not self.end:
            self.root.next = node  # root节点指向新节点
            node.prev = self.root  # 新节点指向根节点
            self.end = node  # 末节点指针指向新节点
        else:
            node.prev = self.root#新节点指向根节点
            temp = self.root.next#保存原来的第一个节点
            self.root.next = node#将新节点替换为第一个节点
            node.next = temp#让新节点的下一个节点为原来的第一个节点
            temp.prev = node#将原来的第一个节点的上一个节点设置为新节点
        self.size += 1


    def __iter__(self):
        current = self.root.next
        if current:
            while current is not self.end:
                yield current
                current = current.next
            return current
        else:
            print("LinkedList is empty")

    #逆向迭代
    def inverse_iter(self):
        current = self.end
        if current:
            while current is not self.root:
                yield current
                current = current.prev
        else:
            print("LinkedList is empty")

    def find(self,value):
        pass

    def find_count(self,value):
        pass

    def remove_first(self):
        if self.end:
            temp = self.root.next
            self.root.next = temp.next
            if temp.next:
                temp.next.prev = self.root
            return temp


    def remove_all(self,value):
        pass

class Queue():
    def __init__(self,size=4):
        self.items = DoubleLinkedList()
        self.size = size
        self.length = 0

    def push(self,value):
        self.items.append(value)
        self.size += 1

    def pop(self):
        if self.length <= 0:
            return
        self.length -= 1
        return self.items.remove_first()

    def empty(self):
        pass

二，栈 

1.双端队列

from collections import deque

# 初始化队列
queue = deque()

# 入队操作
queue.append(1)
queue.append(2)
queue.append(3)

print("初始队列:", queue)

# 出队操作
print("出队元素:", queue.popleft())  # 输出并移除队首元素
print("出队后队列:", queue)

# 再次入队
queue.append(4)

# 查看队列状态
print("当前队列:", queue)
print("队列长度:", len(queue))

根据双端队列的性质可以模仿出栈的效果（先进后出），其实就是 

from collections import deque
d = deque([1,2,3,4])
    print(d.pop())
    print(d.pop())
    print(d.pop())
    print(d.pop())

输出结果： 4 3 2 1

这就类似栈的性质，但是这里只是用双端了队列模拟的。