【栈和队列OJ题】有效的括号&&用队列实现栈&&用栈实现队列&&设计循环队列(下)

简介: 【栈和队列OJ题】有效的括号&&用队列实现栈&&用栈实现队列&&设计循环队列(下)

4.设计循环队列

描述:

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


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


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

MyCircularQueue(k): 构造器,设置队列长度为 k 。

Front: 从队首获取元素。如果队列为空,返回 -1 。

Rear: 获取队尾元素。如果队列为空,返回 -1 。

enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

isEmpty(): 检查循环队列是否为空。

isFull(): 检查循环队列是否已满。

示例:

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3

circularQueue.enQueue(1); // 返回 true

circularQueue.enQueue(2); // 返回 true

circularQueue.enQueue(3); // 返回 true

circularQueue.enQueue(4); // 返回 false,队列已满

circularQueue.Rear(); // 返回 3

circularQueue.isFull(); // 返回 true

circularQueue.deQueue(); // 返回 true

circularQueue.enQueue(4); // 返回 true

circularQueue.Rear(); // 返回 4


提示:

所有的值都在 0 至 1000 的范围内;

操作数将在 1 至 1000 的范围内;

请不要使用内置的队列库。

4.1思路:

在本题中,循环队列的大小是固定的,可重复利用之前的空间。接下来,就开始分析结构。

结构分析:

题目给定循环队列的大小为 k ,不论数组和链表,构建的大小为 k ,可行吗?

给定 front 和 rear 为0,front 标识队头,rear 标识队尾的下一个数据的位置,每当 入数据, rear++,向后走。

由于是循环队列,空间可以重复利用,当放置完最后一个数据后,rear需要回到头部。

那么问题来了,如何判空和判满 ?无论队列空或满,front 和 rear 都在一个位置。

e4bfb59b3e204c8596ba5066befdd22a.png1.解决方法一:

结构设计时,多加一个 size ,标识队列数据个数。

size=0为空,size=k就是满

2.解决方法二 :

创建队列时,额外创建一个空间。

870322d63f0342f6a780bf4a417e83d4.png

缺陷:单链表取尾不好取

数组:

对于数组,那么我们就开上 k + 1 个空间。

frontrear 分别标识队头和队尾。

1ba28587373c4f75b4a7120feb2962a2.png

每当入数据,rear 向后走一步,front 不动;每当出数据,front 向后走一步,rear 不动。当走过下标 k 处后,front 和 rear 的位置需要加以调整。比如,rear 下一步应该走到第一个空间:下标0位置。

a90de715e78d4362a01efec6f410cdb2.png队列空 时,front == rear。


队列满 时, rear 的下一个位置是 front 。平常只需要看 rear + 1 是否等于 front 即可。但是 放置的元素在 k 下标处时,此刻的 rear 需要特殊处理,rear 的位置会移动到 0 下标。经公式推导:(rear + 1) % (k + 1) == front 时,队列满,平常状况也不会受到公式影响。

d5020ba2a2bc4c96b649b525934e919a.png入数据时,在 rear 位置入数据,然后 rear 向后移动,同样的,当入数据时到 k 下标的空间后,rear 需要特殊处理:rear %= k + 1

48e204b8793e4490bda3c0315007a18d.png出数据时,将 front 向后移动,当出数据到 k 下标的空间后,front 需要特殊处理:front %= k + 1

取队头数据时,不为空取 front 处元素即可。

dec1005c5019415faa2287c869d0041b.png

取队尾数据时,需要取rear 前一个位置,当队列非空时且 rear 不在 0下标时,直接取前一个;当队列非空且 rear 在 0 位置时,需要推导一下公式,前一个数据的下标为:(rear-1 + k+1) % (k + 1),两种情况都适用。

5f47437b52df4357b5649b2ff21bfd7a.png

typedef struct 
{
    int* a;//数组模拟环形队列
    int front;队头
    int rear;//队尾
    int k;//队列可存储的有效数据总数
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //申请一个环形队列
    obj->a = (int*)malloc(sizeof(int) * (k + 1));//开K=1层//开辟队列空间
    obj->front = obj->rear = 0;
    //初始时,队头和队尾均为0
    obj->k = k;//设置队列可存储的有效数据个数
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->front == obj->rear;
    //当front和rear指向同一位置时,队列为空
}
bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if (myCircularQueueIsFull(obj))
    //队列已满,不能再插入数据
        return false;
    //插入数据
    obj->a[obj->rear++] = value;//放数据
    obj->rear %= (obj->k + 1);
    return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
    //当队列为空时,无法再删除数据
        return false;
    //删除数据
    obj->front++;
    obj->front %= (obj->k + 1);
    return true;
}
int myCircularQueueFront(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
    //当队列为空时,无数据可返回
        return -1;
    else
    //返回队头指向的数据
        return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
    //当队列为空时,无数据可返回
        return -1;
    else
    //返回rear指向位置的数据
        return obj->a[(obj->rear-1 + obj->k+1) % (obj->k + 1)];
    //可读性更强的方法
    //int x=obj->rear==0?obj->k:obj->rear-1;
    //rear=0 返回k的位置 反之返回rear-1
    //return obj->a[x];
}
void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->a);//先释放动态开辟的数组
    free(obj);//再释放动态开辟的结构体
}

链表:

其实对于循环队列而言,使用链表来构建是最清晰的。

注意 当构建链表时,构建的是 k + 1 个节点的 单向循环链表

front 和 rear 分别标识 队头 和 队尾。

队列空,front == rear 。

队列满,rear 的下一个节点就是 front 节点,rear->next == front。

入数据时,比数组设计简单很多,就直接让rear 迭代到下一个节点就可以。

出数据时,队列非空时,直接让front 迭代到下一个节点。

取队头元素时,如果非空,直接取 front 节点处的值。

取队尾元素时,如果非空,则从头开始迭代到rear 的前一个节点,取出元素。

需要注意 销毁的时候,由于链表不带头,所以销毁的时候可以从第二个节点开始迭代销毁,然后销毁第一个节点,最后销毁队列本身。这里比较细节,过会可以看一下代码。

typedef struct  CQNode
{
    struct CQNode* next;
    int data;
}CQNode;
typedef struct 
{
    CQNode* front;
    CQNode* rear;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj); 
// 创建节点
CQNode* BuyNode()
{
    CQNode* newnode = (CQNode*)malloc(sizeof(CQNode));
    newnode->next = NULL;
    return newnode;
}
MyCircularQueue* myCircularQueueCreate(int k) 
{
    // 构建长度 k + 1 的单向循环链表
    // 多开一个空间,防止边界问题
    CQNode* head = NULL, *tail = NULL;
    int len = k + 1;
    while (len--)
    {
        CQNode* newnode = BuyNode();
        if (tail == NULL)
        {
            head = tail = newnode;
        }
        else
        {
            tail->next = newnode;
            tail = newnode;
        }
        tail->next = head;
    }
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->front = cq->rear = head;
    return cq;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if (myCircularQueueIsFull(obj))
        return false;
    // 直接插入在rear位置,rear后移
    obj->rear->data = value;
    obj->rear = obj->rear->next;
    return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
        return false;
    obj->front = obj->front->next;
    return true;
}
int myCircularQueueFront(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    return obj->front->data;
}
int myCircularQueueRear(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
        return -1;
    // 取rear前一个元素
    CQNode* cur = obj->front;
    while (cur->next != obj->rear)
    {
        cur = cur->next;
    }
    return cur->data;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return obj->rear->next == obj->front;
}
void myCircularQueueFree(MyCircularQueue* obj) 
{
    // 销毁需要逐个销毁
    CQNode* cur = obj->front->next;
    // 从第二个节点开始,防止找不到头
    while (cur != obj->front)
    {
        CQNode* next = cur->next;
        free(cur);
        cur = next;
    }
    // 销毁
    free(cur);
    free(obj);
}
/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 * bool param_2 = myCircularQueueDeQueue(obj);
 * int param_3 = myCircularQueueFront(obj);
 * int param_4 = myCircularQueueRear(obj);
 * bool param_5 = myCircularQueueIsEmpty(obj);
 * bool param_6 = myCircularQueueIsFull(obj);
 * myCircularQueueFree(obj);
*/

5.总结:

今天我们分析并完成栈和队列相关OJ题,通过分析明白了原理,愿这篇博客能帮助大家理解这些OJ题,因为栈和队列相关OJ题是还是有一些难度和细节需要注意。希望我的文章和讲解能对大家的学习提供一些帮助。之后会继续更新二叉树的相关知识点。

当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

c3ad96b16d2e46119dd2b9357f295e3f.jpg

相关文章
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
26 1
|
18天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
39 5
|
25天前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
42 0
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
159 9
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
51 4
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
43 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
初步认识栈和队列
初步认识栈和队列
61 10

热门文章

最新文章