文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2023-01-31 02:57

关注

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

图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,

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯