Python描述数据结构之循环队列篇

本篇章主要介绍队列及循环队列，并用Python实现循环队列的基本操作。

夏小悠

4389人浏览 · 2020-08-07 20:42:52

夏小悠 · 2020-08-07 20:42:52 发布

文章目录

前言

本篇章主要介绍队列及循环队列，并用Python实现循环队列的基本操作。

1. 队列

队列 $(Q u e u e)$ ，简称队，也是一种操作受限的线性表，只允许在表的一端(队首)进行插入，另一端(队尾)进行删除，与栈正相反，队列是先进先出 $(F i r s t$ $I n$ $F i r s t$ $O u t, F I F O)$ 。

在这里插入图片描述
队列有两个指针，队首指针front指向队首元素，队尾指针fear指向队尾元素。

入队操作：先将值送到队尾元素，然后队尾指针加1。

出队操作：先取队首元素，然后队首指针加1。

队空条件： $f r o n t = = r e a r = = 0$ 。

队满条件：╰( ´・ω・)つ──☆✿✿✿ $f r o n t = = r e a r$ 。

队列长度： $r e a r - f r o n t$ 。

很明显，上面的队满条件不合适，比如下面这种情况， $a_1,a_2,a_3$ 已经出队，这时 $f r o n t = r e a r$ 满足队满条件，但是队列并没有满，出现了“假溢出”的情况，所以我们引入了循环队列来解决这一问题。

在这里插入图片描述

2. 循环队列

循环队列在逻辑上可以将其视为一个环，当队首指针 $f r o n t = M a x S i z e - 1$ 后，再前进一个位置就自动到0，即取余运算。

队空条件： $f r o n t = = r e a r = = 0$ 。

队满条件： $(rear+1)\%MaxSize==front$ 。

队列长度： $(rear-front+MaxSize)\%MaxSize$ 。

队首指针进1： $front=(front+1)\%MaxSize$ 。

队尾指针进1： $rear=(rear+1)\%MaxSize$ 。

出队入队时，指针都按顺时针加1。

在这里插入图片描述

3. 基本操作

操作名称	操作说明
`CreateCircularSequenceQueue(val_list)`	创建循环队列
`IsEmpty()`	判断循环队列是否为空
`LengthQueue()`	返回循环队列的长度
`Traverse()`	打印出循环队列里的数据元素
`EnQueue(data)`	入队
`DeQueue()`	出队
`GetHead()`	取队首元素

4. 代码实现

class CircularSequenceQueue(object):
    def __init__(self):
        self.MaxQuenceSize = 10
        self.Q = [None for i in range(self.MaxQuenceSize)]
        self.front = 0
        self.rear = 0

    def CreateCircularSequenceQueue(self, val_list):
        for val in val_list:
            self.EnQueue(val)

    def IsEmpty(self):
        if self.front == self.rear:
            return True
        else:
            return False

    def LengthQueue(self):
        return (self.rear - self.front + self.MaxQuenceSize) % self.MaxQuenceSize

    def EnQueue(self, e):
        if (self.rear + 1) % self.MaxQuenceSize == self.front:
            print('队已满!')
            exit()
        else:
            self.Q[self.rear] = e
            self.rear = (self.rear + 1) % self.MaxQuenceSize

    def DeQueue(self):
        if self.IsEmpty():
            print('队为空!')
            exit()
        else:
            e = self.Q[self.front]
            self.front = (self.front + 1) % self.MaxQuenceSize
            return e

    def Traverse(self):
        for index in range(self.LengthQueue()):
            print(self.Q[index], end=' ')
        print('')

    def GetHead(self):
        return self.Q[self.front]

测试代码如下：

if __name__ == '__main__':
    q1 = CircularSequenceQueue()
    q1.CreateCircularSequenceQueue([1, 3, 5, 7, 9])
    print('队列里的元素为: ', end='')
    q1.Traverse()
    print('队列的长度为: %d' % q1.LengthQueue())
    print('队首元素为: %d' % q1.GetHead())
    print('出队: ', end='')
    for i in range(q1.LengthQueue()):
        print(q1.DeQueue(), end=' ')