首页 > 其他分享 >Leetcode 622. 设计循环队列

Leetcode 622. 设计循环队列

时间:2024-09-26 11:37:00浏览次数:9  
标签:622 head return 队列 self tail Leetcode 指针

1.题目基本信息

1.1.题目描述

设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

你的实现应该支持如下操作:

  • MyCircularQueue(k): 构造器,设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空,返回 -1 。
  • Rear: 获取队尾元素。如果队列为空,返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

1.2.题目地址

https://leetcode.cn/problems/design-circular-queue/description/

2.解题方法

2.1.解题思路

数组法 / 单链表法

2.2.解题步骤

数组法

  • 第一步,初始化存储数组和头尾指针head和rear,尾指针作为标志位始终在数组中占用一个空位置。
  • 第二步,构建判断队列为空和队列已满的判断函数,使用rear指针和head指针的值进行比较进行判断。
  • 第三步,构建入队函数,首先判断队列是否已满,如果已满,直接返回False;如果未满,在rear指针处添加值,并将rear指针加1并取数组长度数值的模,返回True。
  • 第四步,构建出队函数,首先判断队列是否为空,为空则直接返回False,如果不为空,则初始化head处数组的值,并将head指针加1并取数组长度数值的模,返回True。
  • 第五步,根据head和rear指针很容易构建获取队首和队尾的值,但注意先判断队列是否已满或者已空。
  • 注意:这里的rear指向空节点方便进行是否已满或者已空的判断。

单链表法

  • 第一步,初始化头结点指针head和尾节点指针tail为None,同时初始化循环队列的容量capacity和当前的大小size。
  • 第二步,构建isEmpty和isFull函数,根据size和capacity判断当前队列是否已满或为空。
  • 第三步,构建入队函数,如果队列已满,直接返回False;如果未满但是队列为空,设置head和tail指针指向新建的节点;如果未满但队列不为空,则设置将新节点添加到tail尾部,同时tail指向新的尾节点(即新构建的节点),同时将size加1。
  • 第四步,构建出队函数,如果队列为空,直接返回False;如果队列不为空,则head指针指向head的下一个节点,并将size减1。
  • 第五步,根据head和tail指针很容易构建Front和Rear获取头结点和尾节点的值。
  • 注意:这里的尾节点必须指向有值节点,否则tail指针想要获取尾节点的值必须遍历整个链表。

3.解题代码

Python代码 – 数组法

# 数组法
# 第一步,初始化存储数组和头尾指针head和rear,尾指针作为标志位始终在数组中占用一个空位置。第二步,构建判断队列为空和队列已满的判断函数,使用rear指针和head指针的值进行比较进行判断。第三步,构建入队函数,首先判断队列是否已满,如果已满,直接返回False;如果未满,在rear指针处添加值,并将rear指针加1并取数组长度数值的模,返回True。第四步,构建出队函数,首先判断队列是否为空,为空则直接返回False,如果不为空,则初始化head处数组的值,并将head指针加1并取数组长度数值的模,返回True。第五步,根据head和rear指针很容易构建获取队首和队尾的值,但注意先判断队列是否已满或者已空。
# 注意:这里的rear指向空节点方便进行是否已满或者已空的判断。
class MyCircularQueue:
    def __init__(self, k: int):
        self.data=[-1]*(k+1)    # k+1是为了让rear节点始终维持为空的状态
        self.head=self.rear=0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[self.rear]=value
        self.rear=(self.rear+1)%len(self.data)
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.data[self.head]=-1
        self.head=(self.head+1)%len(self.data)
        return True

    def Front(self) -> int:
        return -1 if self.isEmpty() else self.data[self.head]

    def Rear(self) -> int:
        return -1 if self.isEmpty() else self.data[self.rear-1]

    def isEmpty(self) -> bool:
        return True if self.head==self.rear else False

    def isFull(self) -> bool:
        return True if (self.rear+1)%len(self.data)==self.head else False

Python代码 – 单链表法

class LinkedNode():
    def __init__(self,val,next=None):
        self.val=val
        self.next=next

# 单链表法
# 第一步,初始化头结点指针head和尾节点指针tail为None,同时初始化循环队列的容量capacity和当前的大小size。第二步,构建isEmpty和isFull函数,根据size和capacity判断当前队列是否已满或为空。第三步,构建入队函数,如果队列已满,直接返回False;如果未满但是队列为空,设置head和tail指针指向新建的节点;如果未满但队列不为空,则设置将新节点添加到tail尾部,同时tail指向新的尾节点(即新构建的节点),同时将size加1。第四步,构建出队函数,如果队列为空,直接返回False;如果队列不为空,则head指针指向head的下一个节点,并将size减1。第五步,根据head和tail指针很容易构建Front和Rear获取头结点和尾节点的值。
# 注意:这里的尾节点必须指向有值节点,否则tail指针想要获取尾节点的值必须遍历整个链表。
class MyCircularQueue:
    def __init__(self, k: int):
        self.head=self.tail=None
        self.capacity=k
        self.size=0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        newNode=LinkedNode(value)
        if self.isEmpty():
            self.head=self.tail=newNode
        else:
            self.tail.next=newNode
            self.tail=newNode
        self.size+=1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.head=self.head.next
        self.size-=1
        return True

    def Front(self) -> int:
        return self.head.val if not self.isEmpty() else -1

    def Rear(self) -> int:
        return self.tail.val if not self.isEmpty() else -1

    def isEmpty(self) -> bool:
        return self.size==0

    def isFull(self) -> bool:
        return self.size==self.capacity

C++代码 – 单链表法

struct LinkedNode{
    int val;
    struct LinkedNode *next;
    LinkedNode(int x): val(x), next(NULL){};    // 初始化
};

class MyCircularQueue {
    LinkedNode *head;
    LinkedNode *tail;
    int capacity;
    int size;
public:
    MyCircularQueue(int k) {
        this->capacity=k;
        this->size=0;
        this->head = this->tail = nullptr;
    }
    
    bool enQueue(int value) {
        if(isFull()){
            return false;
        }
        LinkedNode* newNode=new LinkedNode(value);
        if(isEmpty()){
            head=newNode;
            tail=newNode;
        }else{
            tail->next = newNode;
            tail=newNode;
        }
        size++;
        return true;
    }
    
    bool deQueue() {
        if(isEmpty()){
            return false;
        }
        LinkedNode *node=head;
        head=head->next;
        size--;
        node->next = NULL;
        delete node;
        return true;
    }
    
    int Front() {
        return isEmpty() ? -1 : head->val;
    }
    
    int Rear() {
        return isEmpty() ? -1 : tail->val;
    }
    
    bool isEmpty() {
        return size==0;
    }
    
    bool isFull() {
        return size==capacity;
    }
};

4.执行结果

在这里插入图片描述

标签:622,head,return,队列,self,tail,Leetcode,指针
From: https://www.cnblogs.com/geek0070/p/18433123

相关文章

  • Leetcode 706. 设计哈希映射
    1.题目基本信息1.1.题目描述不使用任何内建的哈希表库设计一个哈希映射(HashMap)。实现MyHashMap类:MyHashMap()用空映射初始化对象voidput(intkey,intvalue)向HashMap插入一个键值对(key,value)。如果key已经存在于映射中,则更新其对应的值value。intget(in......
  • 【算法题】63. 不同路径 II-力扣(LeetCode)-”如果起点有障碍物,那么便到不了终点“
    【算法题】63.不同路径II-力扣(LeetCode)-”如果起点有障碍物,那么便到不了终点“1.题目下方是力扣官方题目的地址63.不同路径II一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格......
  • bfs 与优先队列————洛谷p1126(历经两个小时总算AC了,哭晕)
    机器人搬重物题目描述机器人移动学会(RMI)现在正尝试用机器人搬运物品。机器人的形状是一个直径\(1.6\)米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个\(N\timesM\)的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时......
  • 【C++】队列
    示意图什么是队列队列(queue)是一种具有先进入队列的元素一定先出队列性质的表。由于该性质,队列通常也被称为先进先出(firstinfirstout)表,简称FIFO表。就像排队一样,最先到的人也就最先买到单,优先离开队伍头文件与声明头文件#include<queue>声明定义queue<G>qu......
  • 【LeetCode Hot 100】19. 删除链表的倒数第N个结点
    题目描述由于单向链表只能从头往后遍历,所以无法向数组那样的随机存取结构一样进行下标运算,也无法从链表尾向前数n个结点。本题有两个思路,个人觉得都比较简单。可以先遍历一遍链表得到链表的长度len,然后再从头往后数len-n个结点就是所求结点。可以使用快慢指针,快指针先移动n......
  • 【线程】POSIX信号量---基于环形队列的生产消费者模型
    信号量概念这篇文章是以前写的,里面讲了 SystemV的信号量的概念,POSIX信号量和SystemV信号量作用相同,都是用于同步操作,达到无冲突的访问共享资源目的。但POSIX可以用于线程间同步。信号量的概念POSIX信号量的接口初始化信号量参数:pshared:0表示线程间共享,非0表示进程......
  • Leetcode 626-换座位题目解析
    1.题目编写解决方案来交换每两个连续的学生的座位号。如果学生的数量是奇数,则最后一个学生的id不交换。按 id 升序 返回结果表。 2.数据准备CreatetableIfNotExistsSeat(idint,studentvarchar(255));TruncatetableSeat;insertintoSeat(id,student)v......
  • 【JUC并发编程系列】深入理解Java并发机制:阻塞队列详解与简单纯手写(七、BlockingQueu
    文章目录【JUC并发编程系列】深入理解Java并发机制:阻塞队列详解与简单纯手写(七、BlockingQueue、ArrayBlockingQueue、LinkedBlocking)1.简单回顾1.1数组结构和链表结构1.1.1数组结构1.1.2链表结构1.2有界队列与无界队列1.3Lock锁使用回顾2.什么是阻塞队列3.B......
  • Leetcode 1472. 设计浏览器历史记录
    1.题目基本信息1.1.题目描述你有一个只支持单个标签页的浏览器,最开始你浏览的网页是homepage,你可以访问其他的网站url,也可以在浏览历史中后退steps步或前进steps步。请你实现BrowserHistory类:BrowserHistory(stringhomepage),用homepage初始化浏览器类。void......
  • Leetcode 1396. 设计地铁系统
    1.题目基本信息1.1.题目描述地铁系统跟踪不同车站之间的乘客出行时间,并使用这一数据来计算从一站到另一站的平均时间。实现UndergroundSystem类:voidcheckIn(intid,stringstationName,intt)通行卡ID等于id的乘客,在时间t,从stationName站进入乘客一次只......