面试中算法（使用栈实现队列）

亦凉 2024-05-28 10:22 77阅读 0赞

### 使用栈来模拟一个队列，要求实现队列的两个基本操作:入队、出队。 ###

> **栈的特点：先入后出，出入元素都是在同一端（栈顶）。**

![f9be6d91775f4334859c0f0bbdcabf45.png][]

![ee89a4e11e5d4cde8866a3e7db58bdc3.png][]

> **队列的特点：先入先出，出入元素是在两端（队头和队尾)。**

![0aec36d343ee456fbcb30359410b4447.png][]

> 分析：我们需要A，B两个栈，A栈为队列入口，负责插入新元素，B栈为队列出口，负责移除老元素。

![37ba368bde2d4eb480a9ff2e33a31fba.png][]

### **图解所示：** ###

**（1）元素3入队**

![d682f2ee1e404720889aff0e9a4b8cf5.png][]

**（2）元素5入队**

![01614bba885b49b4bf1b39fd5852155c.png][]

**（3）元素1入队**

![41985b6d39b7446b9078960ec4d48624.png][]

> **让栈A中的所有元素按顺序出栈，再按照出栈顺序压入栈B。这样一来，元素从栈A弹出并压入栈B的顺序是1、5、3，和当初进入栈A的顺序3、5、1是相反的。**

![e13b55dc369d4deca201596c122cbbdc.png][]

**（4）** **元素3出队**

![b51cb4d706eb4df3bdb6d33bef5f60b6.png][]

**（5）** **元素5出队**

![2c2b36a5a88e400ca11f1a367729b535.png][] **（6）元素4入队**

![7bdf48ffde3e461c97b2d4bacd97e2b2.png][] **（7）** **元素1出队**

![e50c887cb1ee48128bc48310735d367d.png][] **（8）** **元素4出队**

![fe6356eb6ee74c80a3968d64684508b8.png][]

![5492db50ea394435bd115e9ebccc1323.png][]

class StackToQueue:
        def __init__(self):
            self.sak_A=[]
            self.sak_B=[]
        #入队
        def in_queue(self,element):
            self.sak_A.append(element)
    
       #栈A出队的压入栈B
        def to_trans(self):
            #循环栈A大于0，则添加到栈B中的是（栈A出队的元素）
            while len(self.sak_A)>0:
                self.sak_B.append(self.sak_A.pop())
        #出队
        def de_queue(self):
            if len(self.sak_B)==0:
                if len(self.sak_A)==0:
                    raise Exception('栈已空了！')
                self.to_trans() #调用方法
            return self.sak_B.pop()  #栈B出队
    
    if __name__ == '__main__':
        sq=StackToQueue()
        sq.in_queue(3)
        sq.in_queue(5)
        sq.in_queue(1)
        #出队
        print(sq.de_queue())  #3
        print(sq.de_queue())  #5
        print("&"*20)
        #入队
        sq.in_queue(4)
        # 出队
        print(sq.de_queue())  #1
        print(sq.de_queue())  #4
        # print(sq.de_queue())  # 发生异常

![836aeaefa44b451c8d36998f73f49e61.png][]

![42ec5a8c18a44844bb25929a7a65a5e3.png][]

总之：入队操作的时间复杂度显然是O (1)。至于出队操作，如果涉及栈A和栈B的元 素迁移，那么一次出队的时间复杂度是o (n)﹔如果不用迁移，时间复杂度是O(1)。所以把时间均摊到每一次出队操作上面，其**时间复杂度是O （1)**

[f9be6d91775f4334859c0f0bbdcabf45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/b7a117fc499a47d5a9d45ae497493a99.png
[ee89a4e11e5d4cde8866a3e7db58bdc3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/92f859e522c2406ab5a25962cee3421b.png
[0aec36d343ee456fbcb30359410b4447.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/24c06138b61345b4ba2709827f5515e5.png
[37ba368bde2d4eb480a9ff2e33a31fba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/e295d8912453467b933478c76c0bfa9a.png
[d682f2ee1e404720889aff0e9a4b8cf5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/8ae47cb81bbf4e1e9c091ecf5b80f1ec.png
[01614bba885b49b4bf1b39fd5852155c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/0cfece495db340ef9e83b844e2642ef9.png
[41985b6d39b7446b9078960ec4d48624.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/a7e68917b6134828b5e2f394c22c9801.png
[e13b55dc369d4deca201596c122cbbdc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/d419f45c2dd2419ab515257351af2714.png
[b51cb4d706eb4df3bdb6d33bef5f60b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/2f4bd36d097040508fda2d5469347e9d.png
[2c2b36a5a88e400ca11f1a367729b535.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/b6795294b8a04c4e927a26909998c1ed.png
[7bdf48ffde3e461c97b2d4bacd97e2b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/dcf96edba7274342bdc81618a1021607.png
[e50c887cb1ee48128bc48310735d367d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/bcabb5b26d3a40988ccfc384bca0393e.png
[fe6356eb6ee74c80a3968d64684508b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/79749e35d756435f8601aee0fa3b17be.png
[5492db50ea394435bd115e9ebccc1323.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/44eea7f91e074bf6b317c59c6ce9a645.png
[836aeaefa44b451c8d36998f73f49e61.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/c711322eb99a47c8bfaf6b34778cfa3a.png
[42ec5a8c18a44844bb25929a7a65a5e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/43f6e7aaa27542039297bb32c616bf84.png