专栏首页python3数据结构之——Python实现循环队列

数据结构之——Python实现循环队列

栈是先入后出,与之相反的是队列,队列是先进先出的线性结构。队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。允许插入的一端称为队尾,允许删除的一端称为队头。

图1 队列的定义 队列的存储结构中使用的最多的是循环队列。循环队列包括两个指针, front 指针指向队头元素, rear 指针指向队尾元素的下一个位置。 队列为空的判断条件是: front == rear

队列满的判断条件是: (rear+1)%maxsize == front

队列长度的计算公式: (rear-front+maxsize)%maxsize

具体的python实现代码如下:

class SqQueue(object):
    def __init__(self, maxsize):
        self.queue = [None] * maxsize
        self.maxsize = maxsize
        self.front = 0
        self.rear = 0

    # 返回当前队列的长度
    def QueueLength(self):
        return (self.rear - self.front + self.maxsize) % self.maxsize

    # 如果队列未满,则在队尾插入元素,时间复杂度O(1)
    def EnQueue(self, data):
        if (self.rear + 1) % self.maxsize == self.front:
            print("The queue is full!")
        else:
            self.queue[self.rear] = data
           # self.queue.insert(self.rear,data)
            self.rear = (self.rear + 1) % self.maxsize

    # 如果队列不为空,则删除队头的元素,时间复杂度O(1)
    def DeQueue(self):
        if self.rear == self.front:
            print("The queue is empty!")
        else:
            data = self.queue[self.front]
            self.queue[self.front] = None
            self.front = (self.front + 1) % self.maxsize
            return data

    # 输出队列中的元素
    def ShowQueue(self):
        for i in range(self.maxsize):
            print(self.queue[i],end=',')
        print(' ')
# 测试程序
if __name__ == "__main__":
    # 建立大小为15的循环队列
    q = SqQueue(15)
    # 0~9入队列
    for i in range(10):
        q.EnQueue(i)
    q.ShowQueue()
    # 删除队头的5个元素:0~4
    for i in range(5):
        q.DeQueue()
    q.ShowQueue()
    # 从队尾增加8个元素:0~7
    for i in range(8):
        q.EnQueue(i)
    q.ShowQueue()

程序输出的结果为:

0,1,2,3,4,5,6,7,8,9,None,None,None,None,None, None,None,None,None,None,5,6,7,8,9,None,None,None,None,None, 5,6,7,None,None,5,6,7,8,9,0,1,2,3,4,

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Selenium&PhantomJS实战二:爬取漫画

    一般来说在线看漫画的网站都会使用JavaScript来返回页面,打开百度搜索在线漫画,如下图:

    py3study
  • python3 - 文本读音器

    本篇分享的是使用python3制作一个文本读音器,简单点就是把指定的文本文字转语音说出来;做这么个小工具主要是为了方便自己在平时看一些文章眼累的时候,可通过语音...

    py3study
  • 三、wss连接B站弹幕

    py3study
  • python高级编程第二讲:类与对象深度问题与解决技巧

    将上面的代码我们进行改造,引入内存跟踪的类,并且将2个类分别实例化100000次,并打印相应的内存大小

    小海怪的互联网
  • python模块:win32com用法详解

    import win32com from win32com.client import Dispatch, constants

    菲宇
  • 设计了一个简易的Python GUI界面

    设计一个支持多个招聘网站的检索,可以通过指定目标城市、检索职业和查询数量,个性化输出检索结果,尔后将结果显示在界面并保存于文档中。

    luanhz
  • PyQt5 动画类--跳舞的火柴人

    PyQt5.QtCore中的 QPropertyAnimation可以实现动画功能。

    用户6021899
  • 商业篇 | 使用python开发性格分析工具卖钱

    如此不均衡的贫富差距,各行业的领导者如何能管理好公司,让员工们即努力产出,又能安于现状呢?每个领导者必学的一门课程就是职场心理学。只有你充分了解员工心理与对应的...

    龙哥
  • selenium爬取拉勾网python职位信息

    菲宇
  • python的tkinter编程(九)Text多行文本框的详细解读

    一天不写程序难受

扫码关注云+社区

领取腾讯云代金券