数据结构基础 ——栈和队列（三）

àì夳堔傛蜴生んèń 2024-04-20 12:27 5阅读 0赞

## 一、物理结构和逻辑结构 ##

![457c2e1decd24b27801b5570d632abc2.png][]

>  *  **物理结构**就是看得见，摸得着。而数组和链表，就是内存中实实在在的存储结构。
>  *  **逻辑结构**就是看不见、摸不着。

## 二、 栈(stack） ##

栈(stack）是一种线性数据结构，栈中的元素只能**先进后出** (First In Last Out，简称FILO）。最早进入的元素存放的位置叫作栈底(bottom），最后进入的元素存放的位置叫作栈顶（top)。

**栈这种数据结构既可以用数组来实现，也可以用链表来实现。**

![0f48405cf6dd401fb25c1c34a17e6ce8.png][]

![8105673fea4944f6ac83ebb40cd6c6b1.png][]

### 栈的基本操作 ###

**1.入栈**  
入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。

![efa1ad50f54b4fc28e279b0278dc098b.png][]

**2.出栈**

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

![8765c6f575954554875fa635f2da5881.png][]

在Python语言中，列表很好地实现了栈的功能，append方法相当于入栈，pop方法相当于出栈。由于栈操作的代码实现相对简单。

ll=[1,2,3,4,5,6]
    #入栈
    ll.append(50)
    ll.append(60)
    print(ll)
    #出栈第一个
    ll.pop(0)
    #出栈最后一个
    ll.pop(len(ll)-1)
    print(ll)

![ae0de2977213484f8f455ade95766dc7.png][]

## 四、队列 ##

队列(queue）是一种**线性数据结构**，队列中的元素只能**先进先出**(First In First Out，简称FIFO)。队列的出口端叫作队头（front），队列的入口端叫作队尾（ rear) 。  
**与栈类似，队列这种数据结构既可以用数组来实现，也可以用链表来实现。**  
![a01d77872ace42018de0398dd16b7a8f.png][]

![86de06109e25447bb374ac7f7a803efd.png][]

### 队列的基本操作 ###

**1、入队**

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

![46d96962fc894345a7285f1ea368a56e.png][]

**2、出队**

出队操作(dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。  
![172dd89f6d714c97ae30b16c65597997.png][]

如果不断出队，队头左边的空间失去作用，那队列的容量岂不是越来越小？

![422731d971e94fc69d3b02b7ec8e0624.png][]

那么就使用数组实现的队列可以采用**循环队列**的方式来维持队列容量的恒定。

![0b35617d5beb4220a16f64706d5239d2.png][]

![a030dd86e5e2468ba207d951deaa02f5.png][]

![479bdf2d0947442698af759497b8dda6.png][] 一直到(队尾下标+1）%数组长度=队头下标时，代表此队列真的已经满了。需要注意的是，队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1。

![bed1dd6f4d0b4defaa0666506e6cce25.png][]

#用列表实现循环队列
    class MyQueue:
        '''初始化'''
        def __init__(self, capacity):
            self.list = [None] * capacity #队列长度
            self.head = 0 #头指针
            self.tail = 0 #尾指针
    
        #入队操作
        def enqueue(self, element):
            #循环队列判断队列是否满
            if (self.tail + 1) % len(self.list) == self.head:
                raise Exception("队列已满")
            self.list[self.tail] = element
            self.tail = (self.tail + 1) % len(self.list)
    
        #出队操作
        def dequeue(self):
            #循环队列判断队列是否为空，如果为空。
            if self.tail == self.head:
                raise Exception("队列为空")
            dequeue_element = self.list[self.head]
            self.head = (self.head + 1) % len(self.list)
            return dequeue_element
    
        #打印循环队列内的元素
        def show(self):
            i = self.head  #队头
            while i is not self.tail:
                print(self.list[i],end="\t")
                i = (i + 1) % len(self.list)

（1）入队已满

if __name__ == '__main__':
        #队列对象
        myQueue = MyQueue(3)
        #入队
        myQueue.enqueue(3)
        myQueue.enqueue(4)
        myQueue.enqueue(5)
        myQueue.enqueue(6)

![1617290ffd5441439cab65b2de6a5e19.png][]

(2) 入队，再出队OK

if __name__ == '__main__':
        #队列对象
        myQueue = MyQueue(6)
        #入队
        myQueue.enqueue(3)
        myQueue.enqueue(4)
        myQueue.enqueue(5)
        myQueue.enqueue(6)
        #出队
        print(myQueue.dequeue())
        print(myQueue.dequeue())
        print('*'*20)

![aa8c296a1d474a738a89e7d6fd4684a5.png][]

（3) 入队，再出队,队列为空

if __name__ == '__main__':
        #队列对象
        myQueue = MyQueue(6)
        #入队
        myQueue.enqueue(3)
        #出队
        print(myQueue.dequeue())
        print(myQueue.dequeue())

![2e485eefba9943b991a45da0ab9359c3.png][] （4) 入队，再出队

if __name__ == '__main__':
        #队列对象
        myQueue = MyQueue(6)
        #入队
        myQueue.enqueue(3)
        myQueue.enqueue(4)
        myQueue.enqueue(5)
        myQueue.enqueue(6)
    
        #出队
        print(myQueue.dequeue())
        print(myQueue.dequeue())
        print('*'*20)
    
        #再入队
        myQueue.enqueue(10)
        myQueue.enqueue(20)
    
        #显示
        myQueue.show()

![ec3b2811791548fcbe79c51fc500ba50.png][]

**总之：入队和出队的时间复杂度，也同样是O (1)**

[457c2e1decd24b27801b5570d632abc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/8e298fdd94774481a5745426dbfe72a8.png
[0f48405cf6dd401fb25c1c34a17e6ce8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/1d6b2da02afa43b78dfeb885e7ead98a.png
[8105673fea4944f6ac83ebb40cd6c6b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/b153a9f39e414fe8bde8419e8f9b7628.png
[efa1ad50f54b4fc28e279b0278dc098b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/03bf3f58cd24432590dfb74c8b6dff2f.png
[8765c6f575954554875fa635f2da5881.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/6ae85144e5d340eb8766599976350338.png
[ae0de2977213484f8f455ade95766dc7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/f635b49ae8754ff4abe83967485ee725.png
[a01d77872ace42018de0398dd16b7a8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/05ecf093ff154a638af89a9fdf4da16c.png
[86de06109e25447bb374ac7f7a803efd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/857bd30f592d464aa512eae73023e607.png
[46d96962fc894345a7285f1ea368a56e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/7b060cf3146b400cb039f09334f1702e.png
[172dd89f6d714c97ae30b16c65597997.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/f44e953a39194c5cb6f6c0807c60efa4.png
[422731d971e94fc69d3b02b7ec8e0624.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/202a3255269847ee99047363466dc866.png
[0b35617d5beb4220a16f64706d5239d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/b680d38b6bbb499794d5ff5897e63e19.png
[a030dd86e5e2468ba207d951deaa02f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/0aca0794053c43478d27f856d4e8c94f.png
[479bdf2d0947442698af759497b8dda6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/4266cce0b1f14a3d9702a59f37dcbff3.png
[bed1dd6f4d0b4defaa0666506e6cce25.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/2c8845267032454c8f203c0b8551b163.png
[1617290ffd5441439cab65b2de6a5e19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/5b64f73206fb49389aeba34251cb9d3d.png
[aa8c296a1d474a738a89e7d6fd4684a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/3545f4f076904c99b19932d7952683c5.png
[2e485eefba9943b991a45da0ab9359c3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/cd751c763a5c43f0b0086a9312e4cb94.png
[ec3b2811791548fcbe79c51fc500ba50.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/6326e22da75343ebbe61da05354f5dc8.png