专栏首页T客来了打牢地基-队列

打牢地基-队列

章节

  • 队列的特性 & 图示
  • 数组队列简介与实现
  • 循环队列简介与实现

队列的特性 & 图示

  1. 队列是一种FIFO的线性数据结构

数组队列简介与实现

实现一个数组队列

Queue
 
def enqueue(val): # 入队列 从队尾入队列
 
def dequeue(): # 出队列 从队首出队列
 
def get_front(): # 获取 队首元素
 
def get_size(): # 获取队列元素个数
 
def is_empty(): # 队列是否为空
 

ArrayQueue - 基于动态数组实现

#!/usr/bin/env python
 
# -*- coding: utf-8 -*-
 
"""
 
# @Time    : 2020/2/4 下午4:58
 
# @Author  : bofengliu@tencent.com
 
# @Site    : 
 
# @File    : queue.py
 
# @Software: PyCharm
 
# 队列 , 底层同样使用动态数组
 
# 缺陷: 使用动态数组实现的队列,dequeue 时间复杂度是 O(n)
 
"""

 
from array.Array import Array
 
class ArrayQueue:
 
 def __init__(self, capacity=None):
 
 if capacity is None:
 
            self.array = Array()
 
 else:
 
            self.array = Array(capacity)
 
 def enqueue(self, val):
 
 """
 
        队尾入队
 
        :param val:
 
        :return:
 
        """
 
        self.array.add_last(val)

 
 def dequeue(self):
 
 """
 
        队首出队
 
        :return:
 
        """
 
 return self.array.remove_first()
 


 
 def get_front(self):
 
 return self.array.get_first()
 


 
 def get_size(self):
 
 return self.array.get_size()
 


 
 def is_empty(self):
 
 return self.array.is_empty()
 


 
 def to_string(self):
 
        res_queue_arr = []
 
        res_queue_arr.append('Queue: front [')
 
 for i in range(0, self.get_size()):
 
            val = self.array.get(i)
 
 if isinstance(val, int):
 
                val = str(val)
 
            res_queue_arr.append(val)
 
 if i != self.get_size() - 1:
 
                res_queue_arr.append(',')
 
        res_queue_arr.append('] tail')
 
 return "".join(res_queue_arr)
 


 


 
if __name__ == '__main__':
 
    arrayQueue = ArrayQueue()
 
 for i in range(0, 10):
 
        arrayQueue.enqueue(i)
 


 
 print(arrayQueue.to_string())
 


 
    arrayQueue.dequeue()
 
 print(arrayQueue.to_string())
 
    arrayQueue.enqueue(1)
 
 print(arrayQueue.to_string())
 
    arrayQueue.enqueue(12)
 
 print(arrayQueue.to_string())
 

循环队列简介与实现

数组队列 dequeue 的时间复杂度是 o(n) ,因每次删除队首元素,后面的元素都得进行前移操作 使用循环队列可以将dequeue的时间复杂度降至o(1)

LoopQueue - 基于python list 实现

#!/usr/bin/env python
 
# -*- coding: utf-8 -*-
 
"""
 
# @Time    : 2020/2/5 上午11:29
 
# @Author  : bofengliu@tencent.com
 
# @Site    : 
 
# @File    : LoopQueue.py
 
# @Software: PyCharm
 
# 不使用动态数组、自己从底层实现循环队列
 
# 先实现查询、后实现增、删、改, 取余成环
 
"""
 


 


 
class LoopQueue:
 
 def __init__(self, capacity=None):
 
 if capacity is None:
 
            self._data = [None] * 10
 
 else:
 
            self._data = [None] * (capacity + 1)
 
 # 队首索引
 
        self._front = 0
 
 # 队尾索引
 
        self._tail = 0
 
 # 元素个数
 
        self._size = 0
 


 
 def get_capacity(self):
 
 # capacity 浪费一个空间,用来区分 队列空 & 队列满
 
 return len(self._data) - 1
 


 
 def is_empty(self):
 
 return self._front == self._tail
 


 
 def get_size(self):
 
 return self._size
 


 
 def enqueue(self, val):
 
 # 判断队列是否满, 取余,让队列索引循环起来
 
 if (self._tail + 1) % len(self._data) == self._front:
 
            self.resize(self.get_capacity() * 2)
 


 
        self._data[self._tail] = val
 
        self._tail = (self._tail + 1) % len(self._data)
 
        self._size += 1
 


 
 def dequeue(self):
 
 if self._tail == self._front:
 
 raise (Exception, 'cannot dequeue from an empty queue.')
 
        ret = self._data[self._front]
 
        self._data[self._front] = None
 
        self._front = (self._front + 1) % len(self._data)
 
        self._size -= 1
 


 
 if self._size == self.get_capacity() / 4:
 
            self.resize(self.get_capacity() / 2)
 
 return ret
 


 
 def get_front(self):
 
 if self.is_empty():
 
 raise (Exception, 'queue is empty')
 
 return self._data[self._front]
 


 
 def resize(self, new_capacity):
 
        new_data = [None] * (new_capacity + 1)
 
 for i in range(0, self._size):
 
 # 原始队列队首元素放在新队列的队首
 
            new_data[i] = self._data[(i + self._front) % len(self._data)]
 
        self._data = new_data
 
        self._front = 0
 
        self._tail = self._size
 


 
 def to_string(self):
 
        res_queue_arr = []
 
        res_queue_arr.append('Queue: size = %d, capacity = %d front [' % (self._size, self.get_capacity()))
 
        index = self._front
 
 while index != self._tail:
 
            val = self._data[index]
 
 if isinstance(val, int):
 
                val = str(val)
 
            res_queue_arr.append(val)
 
 if index != self._tail - 1:
 
                res_queue_arr.append(',')
 
            index = (index + 1) % len(self._data)
 
        res_queue_arr.append('] tail')
 
 return "".join(res_queue_arr)
 


 


 
if __name__ == '__main__':
 
    loopQueue = LoopQueue(1)
 
 print(loopQueue.to_string())
 
 for i in range(0, 5):
 
        loopQueue.enqueue(i)
 
 print(loopQueue.to_string())
 
 print(loopQueue.to_string())
 


 
    loopQueue.dequeue()
 
 print(loopQueue.to_string())
 


 
    loopQueue.dequeue()
 
 print(loopQueue.to_string())
 

本文分享自微信公众号 - T客来了(ltdo11),作者:bofeng

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-06

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打牢地基-链表

    注意: 关键点: 找到要插入节点的前一个节点 LinkedList - (head实现)

    用户1081422
  • 打牢地基-栈篇

    底层实现并不关心, 栈通过动态array(capacity 可以动态变化)实现即可,栈的操作是array的子集

    用户1081422
  • 打牢地基-二叉树、BST

    二分搜索树-BTS 加速查询过程的原因,假如根节点val = 28, 现在在查找 30 这个元素,因为BTS的存储特性,只需要查找右子树部分就可以了,大大提高了...

    用户1081422
  • 打牢地基-拿下红黑树

    红黑树与2-3树的等价关系,理解2-3树和红黑树之间的关系 红黑树就很简单了 学习2-3树不仅对理解红黑树有帮助,对于理解B类树,也是有巨大帮助的:

    用户1081422
  • 打牢地基-映射的底层实现(LinkedListMap、BSTMap)

    注意:设置了 getnode 辅助函数, contains()、get()、set() 都会用的到

    用户1081422
  • 【编程基础】盖大楼地基要牢固

    水之积也不厚,则其负大舟也无力。——庄子 上一篇讲了几个编译编辑器,大家都可以用用,新手掌握几个是没有坏处的。 学编程要从基础学起,就像盖大楼,先把地基打好,...

    程序员互动联盟
  • 打牢算法基础,从动手出发!

    大家好,我是光城。算法在计算机领域的重要性,就不用我多说了,每个人都想要学算法,打牢算法基础,可是不知道如何做,今天我来推荐一波学习思路。

    公众号guangcity
  • Python打牢基础,从12个语法开始!

    Python简单易学,但又博大精深。许多人号称精通Python,却不会写Pythonic的代码,对很多常用包的使用也并不熟悉。学海无涯,我们先来了解一些Pyth...

    小小詹同学
  • 大牛带你打牢Python基础,看看这10语法

    都说Python简单,易懂,但是有时候却又很深奥,许多人都觉的自己学会了,却老是写不出项目来,对很多常用包的使用也并不熟悉。学海无涯,我们先来了解一些Pytho...

    一墨编程学习
  • 腾讯安全Blade团队亮相CanSecWest峰会

    北京时间3月15日,世界顶级信息安全峰会CanSecWest于加拿大温哥华举办,来自腾讯安全平台部的Blade团队带来了手机基带相关的创新安全议题,这也是业内首...

    腾讯技术工程官方号
  • 队列基本概念、循环队列【重点】

    一种可以实现“先进先出”的存储结构,即“一端入,一端出”, 队首(front)出队,队尾(rear)入队(注:若front指向队首,则rear指向队尾最后一个...

    孙晨c
  • 花了3天总结的RabbitMQ实用技巧,有点东西!

    RabbitMQ是最受欢迎的开源消息中间件之一,在全球范围内被广泛应用。RabbitMQ是轻量级且易于部署的,能支持多种消息协议。RabbitMQ可以部署在分布...

    macrozheng
  • 如何提高编写代码的速度?

    如何提高代码编写的速度,一直是一个逃避不了的问题。在天朝你得像打字员一样做程序员,不然老板和上司都觉得你是在玩耍。对项目的贡献体现在哪里?码农难道不是以code...

    程序员互动联盟
  • 握草,你竟然在代码里下毒!

    除了有点味道以外,这回是不记住了,我们编程写代码的过程和我们日常生活的例子,往往都是这样可以对应上,有了真实可以触及的实物,再去了解编程就会更加容易,也很难忘记...

    小傅哥
  • [第31期] 掌握队列基础

    栈是一种先进后出的数据结构, 队列是一种先进先出的数据结构,那怎么用栈来模拟队列呢?

    皮小蛋
  • Travis CI + Hexo 实现静态博客自动部署

    众所周知,静态博客的一大特点就是没有管理后台,因此常规的操作流程一般是写文章-丢进_posts文件夹-手动执行构建-发布。事实上我也一直是这么干的,得益于 Co...

    Hans362
  • 3.1 VR扫描:CNN把实况新闻报道带进Magic Leap One;VR ZONE将于3月31日结束营业

    今日,美国CNN把实况新闻报道和点播内容带到MR世界,其允许佩戴ML1的用户在MR环境下观看新闻报道。用户可以在任何位置生成任意大小的屏幕,并能在所选空间中创建...

    VRPinea
  • 中国首篇Science机器人子刊!北航软体机器人实验室四年成果登上封面长篇

    【新智元导读】国际顶级期刊《科学》(Science)杂志机器人子刊《科学·机器人学》(Science Robotics)以长篇封面报道刊登北京航空航天大学文力副...

    新智元
  • 车俊书记:抓网络安全就是抓稳定 抓信息化就是抓发展

    ? ?   省委网络安全和信息化领导小组会议27日在杭举行。省委书记、省委网络安全和信息化领导小组组长车俊在会上强调,要认真贯彻落实习近平总书记网络强国战略思...

    安恒信息

扫码关注云+社区

领取腾讯云代金券