AI 助理
备案控制台
开发者社区 云计算 文章 正文

【DS】队列@栈和队列

2022-07-29 93
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 队列

@TOC
上次实现队列，是在三个月之前，拖到现在才写文章非常惭愧，但细节忘得差不多了反倒利于我思考嘞，写的过程也犯了几个傻错误，它们都变成小注意写在文章中了。

正文开始

1. 队列的概念和结构

1.1 队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

<img src=" title="">

1.2 队列结构

队列也可以数组和链表的结构实现。但数组结构明显不适合，出队列，即头删要挪动数据，效率会低。

//队列
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

为了避免每次找尾的麻烦，我们定义一个尾指针，一头一尾构成队列的结构体。

//多个变量，那就用结构体封起来
typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}Queue;

2. 队列的实现

头文件附在后面大家自己写嗷，单链表增删查改都会了，这个就是一样的，除了尾指针的加入带来了一点小变动，也没关系，小注意都写好嘞~

2.1 初始化和销毁

2.1.1 初始化

<img src=" title="">
开始时，队列为空，因此我们这样初始化这个结构体 ——
<img src=" title="">

我要的改变head，tail是结构体中的内容，不需要传二级指针，要改变结构体，就传结构体指针就行。

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}

2.1.2 销毁

遍历销毁即可。

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

2.2 求队列中有效元素个数、队列是否为空

2.2.1 求队列中有效元素个数

int QueueSize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QueueNode* cur = pq->head;
    while (cur)
    {
        cur = cur->next;
        size++;
    }
    return size;
}

2.2.2 队列是否为空

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}

2.3 入队和出队

要考虑的和单链表的尾插和头删基本一致。

2.3.1 入队

尾插考虑空链表时的插入。

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;//迭代
    }
}

2.3.2 出队

注意！删完了，此时head为空，tail要更改，否则是野指针。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kl3mQswC-1644214522589)(C:\Users\13136\AppData\Roaming\Typora\typora-user-images\image-20220207135835481.png)]

如果不过更改看似好像没什么问题，毕竟正常人谁会销毁了队列还去访问它呢，但我就是抽风我去取队尾元素，原本被销毁后空间归还系统应该拿不到，可tail未被更改，就还是能拿得到。

void QueuePop(Queue* pq)
{
    assert(pq);
     assert(!QueueEmpty(pq)); 
    QueueNode* newhead = pq->head->next;
    free(pq->head);
    pq->head = newhead;
    if (pq->head == NULL)
    {
        pq->tail = NULL;
    }
}

2.4 取队头队尾元素

注意断言空链表。

2.4.1 取队头数据

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

2.4.2 取队尾数据

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

附

Queue.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;

//队列
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

//多个变量，那就用结构体封起来
typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);

//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//求队列中有效元素个数
int QueueSize(Queue* pq);
//判断队列是否为空？
bool QueueEmpty(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;//迭代
    }
}

void QueuePop(Queue* pq)
{
    assert(pq);
     assert(!QueueEmpty(pq));
    QueueNode* newhead = pq->head->next;
    free(pq->head);
    pq->head = newhead;
    if (pq->head == NULL)
    {
        pq->tail = NULL;
    }
}

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

int QueueSize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QueueNode* cur = pq->head;
    while (cur)
    {
        cur = cur->next;
        size++;
    }
    return size;
}

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}

test.c

  • [ ] 遍历队列要保证队列的性质，先进先出。
  • [ ] 想取下一个，那就pop掉这个再取下一个，别忘记pop。
#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

void testQueue1()
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    QueuePop(&q);
    QueuePop(&q);
    /*QueuePop(&q);
    QueuePop(&q);*/

    printf("front:%d\n", QueueFront(&q));
    printf("rear:%d\n", QueueBack(&q));
    printf("size:%d\n", QueueSize(&q));

    QueueDestroy(&q);
}

void testQueue2()
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);

    // 遍历栈，要保证先进先出的性质
    while (!QueueEmpty(&q))
    {
        printf("%d ", QueueFront(&q));
        QueuePop(&q);//想取下一个，那就pop掉这个再取下一个
    }
    QueueDestroy(&q);
}

int main()
{
    //testQueue1();
    testQueue2();
    return 0;
}
关键词：
栈数据结构
队列数据结构
队列栈数据结构
ds数据结构
ds队列数据结构
@浮光掠影
目录
相关文章
2的n次方_
|
3天前
|
存储 Java
【数据结构】优先级队列（堆）从实现到应用详解
本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现，堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值，小根堆则相反。文章详细讲解了如何通过数组模拟实现堆，并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外，还介绍了堆排序及解决Top K问题的应用，并展示了Java中`PriorityQueue`的基本用法和注意事项。
2的n次方_
18 5
【数据结构】优先级队列（堆）从实现到应用详解
小徐在进步
|
9天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
28 8
小徐在进步
|
11天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
45 3
2的n次方_
|
12天前
|
Java
【数据结构】栈和队列的深度探索，从实现到应用详解
本文介绍了栈和队列这两种数据结构。栈是一种后进先出（LIFO）的数据结构，元素只能从栈顶进行插入和删除。栈的基本操作包括压栈、出栈、获取栈顶元素、判断是否为空及获取栈的大小。栈可以通过数组或链表实现，并可用于将递归转化为循环。队列则是一种先进先出（FIFO）的数据结构，元素只能从队尾插入，从队首移除。队列的基本操作包括入队、出队、获取队首元素、判断是否为空及获取队列大小。队列可通过双向链表或数组实现。此外，双端队列（Deque）支持两端插入和删除元素，提供了更丰富的操作。
2的n次方_
14 0
【数据结构】栈和队列的深度探索，从实现到应用详解
可能只会写BUG
|
17天前
|
Linux C++ Windows
栈对象返回的问题 RVO / NRVO
具名返回值优化（(Name)Return Value Optimization，(N)RVO）是一种优化机制，在函数返回对象时，通过减少临时对象的构造、复制构造及析构调用次数来降低开销。在C++中，通过直接在返回位置构造对象并利用隐藏参数传递地址，可避免不必要的复制操作。然而，Windows和Linux上的RVO与NRVO实现有所不同，且接收栈对象的方式也会影响优化效果。
可能只会写BUG
29 2
1387503158665997
|
19天前
crash —— 获取内核地址布局、页大小、以及栈布局
crash —— 获取内核地址布局、页大小、以及栈布局
1387503158665997
20 0
睡觉待开机
|
1月前
|
算法 C语言 C++
【practise】栈的压入和弹出序列
【practise】栈的压入和弹出序列
睡觉待开机
21 0
服务端技术栈
|
1月前
栈的几个经典应用，真的绝了
文章总结了栈的几个经典应用场景，包括使用两个栈来实现队列的功能以及利用栈进行对称匹配，并通过LeetCode上的题目示例展示了栈在实际问题中的应用。
服务端技术栈
44 1
栈的几个经典应用，真的绝了
小狮子安度因1
|
1月前
|
负载均衡 网络协议 安全
DKDP用户态协议栈-kni
DKDP用户态协议栈-kni
小狮子安度因1
26 5
小Lee
|
1月前
|
存储 安全 编译器
缓冲区溢出之栈溢出（Stack Overflow
【8月更文挑战第18天】
小Lee
55 3