二月 05, 2024

栈和队列

C语言实现栈和队列

栈和队列

栈的基本概念

栈是一种常用的数据结构，它具有特定的数据处理方式：后进先出（Last In, First Out，简称LIFO）。这意味着最后被添加到栈上的元素将是第一个被移除的元素。可以将栈想象成一摞盘子，你总是只能从顶部添加或移除盘子。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈的主要操作包括：

Push：将一个元素放置到栈顶。
Pop：移除并返回栈顶元素。
Peek：查看栈顶元素而不移除它。
IsEmpty：检查栈是否为空。

栈的用途非常广泛，包括：

函数调用：在大多数编程语言中，函数调用的执行是通过栈来管理的。每当调用一个函数时，其返回地址和相关参数都会被推送到一个调用栈上，函数返回时，则从栈上弹出。
表达式求值：在算术和逻辑表达式的求值中，栈用于存储操作数和操作符。这是编译器设计中的一个重要应用。
回溯算法：在需要回溯的算法（如深度优先搜索）中，栈用于存储之前的状态。
历史记录：在许多应用程序中，如Web浏览器的后退按钮，栈用于维护历史记录。

C语言实现栈

我们将定义一个栈的结构，实现基本操作：push（入栈）、pop（出栈）、peek（查看栈顶元素）和 isEmpty(检查栈是否为空）。

在实现栈之前简单分析一下需要定义哪些元素,以及使用什么样的数据结构
首先既然是存放和读取数据肯定需要设置一个或多个变量存储我们需要的数据,在这个示例里我选择一个int类型存储数据,同时为了维护方便,使用typedef为int类型取一个新的名字StackDataType,这样假使以后需要更换int为其它类型,只需要修改typedef后面的类型就可以了
其次得考虑选择顺序表还是链表来实现栈,先简单介绍下顺序表和链表各自的优缺点吧:
链表
优点:
任意位置插入删除,时间复杂度O(1);
按需申请释放空间;
缺点:
不支持下标的随机访问;
CPU高速缓存命中率会低(文末有关于CPU高速缓存的补充说明)
顺序表
优点：
尾插尾删效率不错
下标的随机访问
CPU高速缓存命中率会更高(文末有关于CPU高速缓存的补充说明)
缺点:
前面部分插入数据,效率是O(N),需要挪动数据
如果空间不够,需要扩容.而扩容又分以下种情况, A、数组是物理连续的，扩容会继续向后开辟空间，如果后面空间足够则原地扩容，并返回原来的指针。这是最理想的情况，因为它不涉及数据的复制。而如果没有足够的连续空间，则会异地扩容，异地扩容就是从内存中其他地方找到足够的空间，然后将原内存块的数据复制到新内存块中，释放原内存块，并返回新内存块的指针。这种情况下，会涉及到数据的复制，会有一定的性能开销。B、内存分配失败：如果无法分配足够的内存，realloc 将返回 NULL。需要注意，在这种情况下，原始内存块不会被释放，因此应该保留原始指针以避免内存泄漏。
扩容空间一般还会带来空间的浪费，因为扩容空间基本都是按原空间的二倍容量扩容.
分析完优缺点后，对顺序表和链表优缺点有了一个基本的认识. 最终根据栈的后进先出特性考虑，使用顺序表来实现栈的操作，因为顺序表尾插和尾删的效率都非常高，以及它有CPU高速缓存命中率更高的优势, 所以它比链表更适合实现栈。
除了定义数据类型和顺序表外,还需要定义两个整型,分别记录栈的结构中栈顶位置top以及容量capacity,

首先定义栈的头文件

`stack.h`:


xxxxxxxxxx
25
1
#pragma once
2
#include <stdio.h>
3
#include <assert.h>
4
#include <stdbool.h>
5
#include <stdlib.h>
6

7
typedef int StackDataType; //定义数据类型
8

9
//栈的结构定义
10
typedef struct StackNode
11
{
12
    StackDataType* arr;  //存储空间的基址
13
    int top;            //栈顶元素的下一个元素
14
    int capacity;       //当前分配的存储容量
15
}STNode;
16

17
void STInit(STNode* st);//初始化栈
18
void STDestroy(STNode* st);//销毁栈
19
void STPop(STNode* st);//移除栈顶元素
20
void STPush(STNode* st, StackDataType x);//入栈操作
21
StackDataType STTop(STNode* st);  //`peek`(查看栈顶元素)
22

23
bool STEmpty(STNode* st); // 检查栈是否为空
24

25
int STSize(STNode* st); //查看栈元素的个数

然后实现函数的定义

`stack.c`:

初始化栈(栈需要自己手动创建)


xxxxxxxxxx
10
1
#define _CRT_SECURE_NO_WARNINGS  //Vscode studio上特有的设置,以方便使用`scanf`函数
2
#include "stack.h"  //包含头文件
3

4
void STInit(STNode* st)
5
{
6
    assert(st);
7
    st->arr = NULL; 
8
    st->top = 0; //初始化置零意味着top指向栈顶元素的后一个,如果想指向栈顶元素,初始化-1
9
    st->capacity = 0;
10
}

销毁栈


xxxxxxxxxx
8
1
void STDestroy(STNode* st)
2
{
3
    assert(st);
4
    free(st->arr);
5
    st->top = 0;
6
    st->capacity = 0;
7
    st->arr = NULL;
8
}

移除栈顶元素


xxxxxxxxxx
7
1
void STPop(STNode* st)
2
{
3
    assert(st);
4
    //assert(st->top > 0);
5
    assert(!STEmpty(st));
6
    st->top--;
7
}

入栈函数


xxxxxxxxxx
19
1
void STPush(STNode* st, StackDataType x)
2
{
3
    assert(st);
4
    if (st->top == st->capacity)//判断占空间已满
5
    {
6
        int size = st->capacity == 0 ? 4 : st->capacity * 2;
7
     //当realloc接受空指针时,其实际作用等同于malloc
8
        StackDataType* tmp = (StackDataType*)realloc(st->arr, sizeof(StackDataType)*size);
9
        if (tmp == NULL)
10
        {
11
            perror("relloc fail");
12
            return;
13
        }
14
        st->arr = tmp;
15
        st->capacity = size;
16
    }
17
    st->arr[st->top] = x;
18
    st->top++;
19
}

查看栈顶元素,返回栈顶元素的值,然后栈顶元素出栈


xxxxxxxxxx
8
1
StackDataType STTop(STNode* st)
2
{
3
    assert(st);
4
    assert(!STEmpty(st));
5
    StackDataType ret = st->arr[st->top-1];
6
    STPop(st);
7
    return ret;
8
}

判断是否为空栈


xxxxxxxxxx
5
1
bool STEmpty(STNode* st)
2
{
3
    assert(st);
4
    return st->top == 0;
5
}

返回栈的元素个数


xxxxxxxxxx
5
1
int STSize(STNode* st)
2
{
3
    assert(st);
4
    return st->top;
5
}

测试函数(展示)

`test.c`


xxxxxxxxxx
27
1
#define _CRT_SECURE_NO_WARNINGS
2
#include "stack.h"
3

4
void testStack()
5
{
6
    STNode stn;
7
    STInit(&stn);
8
    STPush(&stn, 1);
9
    STPush(&stn, 2);
10
    printf("topval:%d\n", STTop(&stn));
11
    STPush(&stn, 3);
12
    STPush(&stn, 4);
13
    printf("elements:%d\n", stn.top);
14
    while (STSize(&stn))
15
    {
16
        printf("%d ", STTop(&stn));
17
    }
18
    printf("\nelements:%d\n", stn.top);
19

20
    STDestroy(&stn);
21
}
22

23
int main()
24
{
25
    testStack();
26
    return 0;
27
}

栈的应用示例

`leetcode`题:有效的括号原题链接

题目描述:
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
xxxxxxxxxx
2
1
输入：s = "()"
2
输出：true
示例 2：
xxxxxxxxxx
2
1
输入：s = "()[]{}"
2
输出：true
示例 3：
xxxxxxxxxx
2
1
输入：s = "(]"
2
输出：false
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

这道题可以很好地使用栈解决,思路如下:

遍历字符串,如果是左括号就入栈
如果是右括号就和栈顶元素比较
比较的过程很类似于消消乐游戏,先分析逻辑:
遍历到当前的字符是右括号时,如果栈顶是同样类型的右括号,就出栈然后继续往下比较;
如果是不同类型的右括号或者栈为空,则直接返回false,因为已经确定最左边的都是左括号,右括号只会跟最近的左括号相匹配,一旦不匹配或者空栈就能肯定整个字符串的括号是不闭合的
还有一种情况是遍历完字符串所有元素,过程中的括号都恰巧匹配,但也不能忘记判断栈是否为空,如果不为空说明左括号数量是多于右括号数量的,这样也是返回false,只有在判断完成后栈为空的情况下才能确定是闭合的,返回true

接下来开始使用C语言代码实现这样一个思路

使用C实现会比C++麻烦很多,因为C不像C++有STL库的支持.
使用C需要自己写一个栈出来完成函数的调用,也就是常说的造轮子.
但是这个过程可以帮助更深入地理解这些数据结构和算法的内部工作原理。

编写代码:


xxxxxxxxxx
99
1
#include <stdio.h>
2
#include <stdbool.h>
3
#include <assert.h>
4
typedef char STDataType;
5

6
typedef struct StackNode
7
{
8
    STDataType* cval;
9
    int top;
10
    int capacity;
11
}STNode;
12
void STInit(STNode*st);
13
bool STEmpty(STNode* st);
14
STDataType STPeek(STNode*st);
15
void STPop(STNode *st);
16
void STPush(STNode *st, STDataType c);
17
void STDestroy(STNode *st);
18

19
void STInit(STNode*st)
20
{
21
    assert(st);
22
    st->top = 0;
23
    st->capacity = 0;
24
    st->cval=NULL;
25
}
26

27
bool STEmpty(STNode* st)
28
{
29
    assert(st);
30
    return st->top==0;
31
}
32

33
STDataType STPeek(STNode*st)
34
{
35
    assert(st);
36
    assert(!STEmpty(st));
37
    return st->cval[st->top-1];
38
}
39

40
void STPop(STNode *st)
41
{
42
    assert(st);
43
    assert(!STEmpty(st)); 
44
    st->top--;
45
}
46

47
void STPush(STNode *st, STDataType c)
48
{
49
    assert(st);
50
    if(st->top==st->capacity)
51
    {
52
        int size = st->capacity==0?4:st->capacity*2;
53
        STDataType* tmp = (STDataType*)realloc(st->cval, sizeof(STDataType)*size);
54
        if(tmp ==NULL)
55
        {
56
            perror("realloc fail");
57
            return;
58
        }
59
        st->capacity = size;
60
        st->cval = tmp;
61
    }
62
    st->cval[st->top] = c;
63
    st->top++;
64
}
65

66
void STDestroy(STNode *st)
67
{
68
    assert(st);
69
    //assert(st->cval); 暴力检查会导致一些用例过不去
70
    if(st->cval==NULL) return;
71
    free(st->cval);
72
    st->top=0;
73
    st->capacity=0;
74
}
75

76
bool isValid(char* s)
77
{
78
    STNode st;
79
    STInit(&st);
80
    while(*s)
81
    {
82
        if(*s=='{'||*s=='('||*s=='[')
83
            STPush(&st, *s);
84
        else if(*s=='}'||*s==')'||*s==']')
85
        {
86
            //STDataType sttop = STPeek(&st);
87
            if(STEmpty(&st) || (STPeek(&st)!=(*s)-2 && STPeek(&st)!=(*s)-1))
88
            {
89
                STDestroy(&st);
90
                return false;
91
            }
92
            STPop(&st);
93
        }
94
        s++;
95
    }
96
    bool ret = STEmpty(&st);
97
    STDestroy(&st);
98
    return ret;
99
}

用例测试通过

提交通过

当然,做这道题其实也用不着这么麻烦,用变长数组加条件判断就可以解决问题,只不过需要定义一个比较大的数组,空间上会有一些浪费

大概如下:


xxxxxxxxxx
37
1
bool isValid(char* s) {
2
    int max_size=10000;//一次性开辟足够空间
3
    typedef struct {
4
       char arr[max_size];
5
       int top;
6
    } Stack;
7

8
    Stack t;
9
    t.top = -1;
10

11
    for (int i = 0; s[i] != '\0'; i++) {
12
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
13
            t.top++;
14
            t.arr[t.top] = s[i];
15
        }
16
        else if (s[i] == ')') {
17
            if (t.top >= 0 && t.arr[t.top] == '(')
18
                t.top--;
19
            else
20
                return false;
21
        }
22
        else if (s[i] == ']') {
23
            if (t.top >= 0 && t.arr[t.top] == '[')
24
                t.top--;
25
            else
26
                return false;
27
        }
28
        else if (s[i] == '}') {
29
            if (t.top >= 0 && t.arr[t.top] == '{')
30
                t.top--;
31
            else
32
                return false;
33
        }
34
    }
35

36
    return t.top == -1;
37
}

队列的基本概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 特性。
这意味着在队列中，元素是按照它们被添加的顺序来被移除的。可以将队列想象成排队等候做核酸的人群，最先来的人将是最先享受捅嗓子并离开队伍的。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

使用链表实现的话,优先选择头删尾插的方式, 因为假如使用头插尾删的方式,在尾删的时候不仅要记录尾结点,同时还要记录尾结点的前一个结点

队列的主要操作包括：

Enqueue（入队）：在队列的尾部添加一个元素。
Dequeue（出队）：移除队列头部的元素，并返回它。
Peek 或 Front：查看队列头部的元素，但不移除它。
IsEmpty：检查队列是否为空。

队列的用途

任务调度和管理：在操作系统中，队列用于任务调度，管理等待处理的任务。
缓冲处理：在数据处理和网络通信中，队列作为缓冲（buffer）来管理数据流，平衡不同处理速率的任务。
异步数据传输：队列可以用于异步数据传输，其中数据的生产和消费速度不一致。
用户界面事件处理：在许多应用程序中，用户生成的事件（如鼠标点击、键盘事件等）会排队等待处理。
打印队列管理：在打印任务中，打印机使用队列来管理打印作业的顺序。

C语言实现队列

队列的创建和栈很相似, 但是链列需要定义个tail变量用来存储尾结点地址,所以在这里定义两个结构体

Queue.h:


xxxxxxxxxx
38
1
#pragma once
2
#include <assert.h>
3
#include <stdio.h>
4
#include <stdlib.h>
5
#include <stdbool.h>
6

7
//队列使用链表实现，使用尾插头删实现队列先进先出的行为模式
8
typedef int QDataType; //定义数据类型
9

10
typedef struct QueueNode
11
{
12
    QDataType data;
13
    struct QueueNode* next;
14
    
15
}QNode;
16

17
struct Queue
18
{
19
    struct QueueNode* head; //记录队列头
20
    struct QueueNode* tail; //记录队列的尾
21
    int size;               //记录队列长度
22
};
23

24
void QueueInit(struct Queue *q); //初始化队列
25

26
QDataType QueuePop(struct Queue* q); //出队
27

28
void QueuePush(struct Queue* q, QDataType x); //入队
29

30
void QueueDestory(struct Queue* q); //销毁队列
31

32
bool QueueEmpty(struct Queue* q); //判断队列是否为空
33

34
QDataType QueueFront(struct Queue* q); //查看队头
35

36
QDataType QueueBack(struct Queue* q); //查看队尾
37

38
int QueueSize(struct Queue* q);      //查看队列长度

然后实现队列函数的定义

`Queue.c`:

初始化队列


xxxxxxxxxx
10
1
#define _CRT_SECURE_NO_WARNINGS
2
#include "Queue.h"
3

4
void QueueInit(struct Queue *q)
5
{
6
    assert(q);
7
    q->head = NULL;
8
    q->tail = NULL;
9
    q->size = 0;
10
}

出队并返回值


xxxxxxxxxx
14
1
QDataType QueuePop(struct Queue* q)
2
{
3
    assert(q);
4
    //assert(q->head);
5
    assert(!QueueEmpty(q));
6
    QNode* next = q->head->next;
7
    QDataType ret = q->head->data;
8
    free(q->head);
9
    q->head = next;
10
    if (next == NULL)
11
        q->tail = NULL;
12
    q->size--;
13
    return ret;
14
}

入队


xxxxxxxxxx
24
1
void QueuePush(struct Queue* q, QDataType x)
2
{
3
    assert(q);
4
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
5
    if (newnode == NULL)
6
    {
7
        perror("malloc fail");
8
        return;
9
    }
10
    newnode->data = x;
11
    newnode->next = NULL;
12

13
    if (q->head == NULL)
14
    {
15
        q->head = newnode;
16
        q->tail = q->head;
17
    }
18
    else
19
    {
20
        q->tail->next = newnode;
21
        q->tail = newnode;
22
    }
23
    q->size++;
24
}

销毁队列


xxxxxxxxxx
13
1
void QueueDestory(struct Queue* q)
2
{
3
    assert(q);
4
    while (q->head)
5
    {
6
        QNode*next = q->head->next;
7
        free(q->head);
8
        q->head = next;
9
    }
10
    q->head = NULL;
11
    q->tail = NULL;
12
    q->size = 0;
13
}

判断队列是否为空


xxxxxxxxxx
6
1
bool QueueEmpty(struct Queue* q)
2
{
3
    assert(q);
4
    //return (q->head == NULL) && (q->tail == NULL);
5
    return q->size == 0;
6
}

查看队首


xxxxxxxxxx
6
1
QDataType QueueFront(struct Queue* q)
2
{
3
    assert(q);
4
    assert(!QueueEmpty(q));
5
    return q->head->data;
6
}

查看队尾


xxxxxxxxxx
6
1
QDataType QueueBack(struct Queue* q)
2
{
3
    assert(q);
4
    assert(!QueueEmpty(q));
5
    return q->tail->data;
6
}

查看队列长度


xxxxxxxxxx
5
1
int QueueSize(struct Queue* q)
2
{
3
    assert(q);
4
    return q->size;
5
}

测试函数(展示)

`test.c`


xxxxxxxxxx
49
1
#define _CRT_SECURE_NO_WARNINGS
2
#include "Queue.h"
3

4
void testQueue()
5
{
6
    struct Queue q;
7
    QueueInit(&q);
8
    QueuePush(&q, 1);
9
    QueuePush(&q, 2);
10
    QueuePush(&q, 3);
11
    QueuePush(&q, 4);
12
    QueuePush(&q, 5);
13
    while (!QueueEmpty(&q))
14
    {
15
        printf("%d ", QueuePop(&q));
16
    }
17
    printf("\n");
18
    QueuePush(&q, 100);
19
    printf("head:%d\n", QueuePop(&q));
20
    QueueDestory(&q);
21
}
22

23
void testQueue2()
24
{
25
    struct Queue q;
26
    QueueInit(&q);
27
    QueuePush(&q, 1);
28
    QueuePush(&q, 2);
29
    QueuePush(&q, 3);
30
    QueuePush(&q, 4);
31
    QueuePush(&q, 5);
32

33
    printf("Rear:%d\n", QueueBack(&q));
34
    printf("head:%d\n", QueueFront(&q));
35
    printf("Pop:%d\n", QueuePop(&q));
36
    printf("Rear:%d\n", QueueBack(&q));
37
    printf("head:%d\n", QueueFront(&q));
38
    printf("length:%d\n", QueueSize(&q));
39
    QueueDestory(&q);
40
    printf("Destroyed\n");
41
    printf("length:%d\n", QueueSize(&q));
42
}
43
int main()
44
{
45
    testQueue();
46
    printf("\n\n");
47
    testQueue2();
48
    return 0;
49
}

队列的应用示例

`leetcode`题: 225.用队列实现栈

题目描述:
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
xxxxxxxxxx
13
1
输入：
2
["MyStack", "push", "push", "top", "pop", "empty"]
3
[[], [1], [2], [], [], []]
4
输出：
5
[null, null, null, 2, 2, false]
6

7
解释：
8
MyStack myStack = new MyStack();
9
myStack.push(1);
10
myStack.push(2);
11
myStack.top(); // 返回 2
12
myStack.pop(); // 返回 2
13
myStack.empty(); // 返回 False
提示：
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

这道题本身没有什么实际意义,因为生产环境中不会有这种奇葩的代码需求,但是通过这道题可以帮助初学者加深了解栈和队列之间的关系,下面开始分析如何实现:

最基本的想法是使用两个队列（我们可以称之为 queueA 和 queueB）来模拟栈的行为：
Push 操作（入栈）：
将新元素加入到空闲的队列（假设初始时为 queueA）。
Pop 操作（出栈）：
将除最后一个元素外的所有元素从 queueA 移到 queueB。
出队 queueA 的最后一个元素（这就是栈顶元素）。
交换 queueA 和 queueB 的角色（现在 queueB 是用来入队新元素的队列）。
Top 操作（获取栈顶元素）：
类似于 Pop 操作，但是在移动元素到另一个队列后，将栈顶元素保存并返回，而不是删除它。当然也可以返回尾结点值的方式直接完成
Empty 操作（判断栈是否为空）：
如果两个队列都为空，则栈为空。
Free 操作(释放栈) :
不光要释放栈本身,同时也要释放queueA 和 queueB

编写代码实现


xxxxxxxxxx
181
1
#include <assert.h>
2
#include <stdbool.h>
3

4
typedef int QueueDataType;
5

6
typedef struct QueueNode
7
{
8
    QueueDataType qdata;
9
    struct QueueNode* next;
10
}QNode;
11

12
typedef struct Queue
13
{
14
    QNode* head;
15
    QNode* tail;
16
    int size;
17
}Queue;
18

19

20
typedef struct {
21
    Queue qa;
22
    Queue qb;
23
} MyStack;
24

25
void QueueInit(Queue* pq);
26
void QueueDestroy(Queue*pq);
27
void QueuePush(Queue*pq, QueueDataType x);
28
void QueuePop(Queue*pq);
29
QueueDataType QueueTail(Queue*pq);
30
QueueDataType QueueFront(Queue*pq);
31

32
bool QueueEmpty(Queue*pq);
33

34
bool QueueEmpty(Queue*pq)
35
{
36
    assert(pq);
37
    return pq->size == 0;
38
}
39
void QueueInit(Queue* pq)
40
{
41
    assert(pq);
42
    pq->head = NULL;
43
    pq->tail = NULL;
44
    pq->size = 0;
45
}
46
void QueueDestroy(Queue*pq)
47
{
48
    assert(pq);
49
    //assert(pq->head);
50
    while(pq->head)
51
    {
52
        QNode*next = pq->head->next;
53
        free(pq->head);
54
        pq->head = next;
55
    }
56
    pq->head = NULL;
57
    pq->tail = NULL;
58
    pq->size = 0 ;
59
}
60
void QueuePush(Queue*pq, QueueDataType x)
61
{
62
    assert(pq);
63
    QNode*newnode = (QNode*)malloc(sizeof(QNode));
64
    if(newnode ==NULL)
65
    {
66
        perror("malloc fail");
67
        return;
68
    }
69
    newnode->qdata = x;
70
    newnode->next = NULL;
71
    if(QueueEmpty(pq))
72
    {
73
        pq->tail=newnode;
74
        pq->head = newnode;
75
    }
76
    else
77
    {
78
        pq->tail->next = newnode;
79
        pq->tail = newnode;
80
    }
81
    pq->size++;
82
}
83
void QueuePop(Queue*pq)
84
{
85
    assert(pq);
86
    assert(!QueueEmpty(pq));
87
    QNode*next = pq->head->next;
88
    free(pq->head);
89
    pq->head = next;
90
    if(next==NULL)
91
        pq->tail = NULL;
92
    pq->size--;
93
}
94
QueueDataType QueueTail(Queue*pq)
95
{
96
    assert(pq);
97
    assert(!QueueEmpty(pq));
98
    return pq->tail->qdata;
99
}
100
QueueDataType QueueFront(Queue*pq)
101
{
102
    assert(pq);
103
    assert(!QueueEmpty(pq));
104
    return pq->head->qdata;
105
}
106
MyStack* myStackCreate() {
107
    MyStack *MS = (MyStack*)malloc(sizeof(MyStack));
108
    QueueInit(&MS->qa);
109
    QueueInit(&MS->qb);
110

111
    return MS;
112
}
113

114
void myStackPush(MyStack* obj, int x) {
115
    if(!QueueEmpty(&obj->qa))
116
    {
117
        QueuePush(&obj->qa, x);
118
    }
119
    else
120
    {
121
        QueuePush(&obj->qb, x);
122
    }
123
}
124

125
int myStackPop(MyStack* obj) {
126
    if(!QueueEmpty(&obj->qa))
127
    {
128
        while((obj->qa.head)->next)
129
        {
130
            QueuePush(&obj->qb, QueueFront(&obj->qa));
131
            QueuePop(&obj->qa);
132
        }
133
        int ret = QueueFront(&obj->qa);
134
        QueuePop(&obj->qa);
135
        return ret;
136
    }
137
    else
138
    {
139
        while((obj->qb.head)->next)
140
        {
141
            QueuePush(&obj->qa, QueueFront(&obj->qb));
142
            QueuePop(&obj->qb);
143
        }
144
        int ret = QueueFront(&obj->qb);
145
        QueuePop(&obj->qb);
146
        return ret;
147
    }
148
}
149

150
int myStackTop(MyStack* obj) {
151
    if(!QueueEmpty(&obj->qa))
152
    {
153
        return QueueTail(&obj->qa);
154
    }
155

156
    return QueueTail(&obj->qb);
157
}
158

159
bool myStackEmpty(MyStack* obj) {
160
    return QueueEmpty(&obj->qa) && QueueEmpty(&obj->qb);
161
}
162

163
void myStackFree(MyStack* obj) {
164
    QueueDestroy(&obj->qa);
165
    QueueDestroy(&obj->qb);
166
    free(obj);
167
}
168

169
/**
170
 * Your MyStack struct will be instantiated and called as such:
171
 * MyStack* obj = myStackCreate();
172
 * myStackPush(obj, x);
173
 
174
 * int param_2 = myStackPop(obj);
175
 
176
 * int param_3 = myStackTop(obj);
177
 
178
 * bool param_4 = myStackEmpty(obj);
179
 
180
 * myStackFree(obj);
181
*/

测试用例通过

提交通过

做完这道题之后其实还有一道姐妹题,使用栈实现队列,为了巩固对栈和队列这种数据结构的理解,顺便也做一下:

`leetcode`题:232.用栈实现队列

题目描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
xxxxxxxxxx
13
1
输入：
2
["MyQueue", "push", "push", "peek", "pop", "empty"]
3
[[], [1], [2], [], [], []]
4
输出：
5
[null, null, null, 1, 1, false]
6

7
解释：
8
MyQueue myQueue = new MyQueue();
9
myQueue.push(1); // queue is: [1]
10
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
11
myQueue.peek(); // return 1
12
myQueue.pop(); // return 1, queue is [2]
13
myQueue.empty(); // return false
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

这道题使用同样的思路会有些小问题, 假设两个栈分别是StackA StackB,按照顺序压栈1,2,3,4给StackA, 第一次出队的时候把数据挪动到了StackB,然后移除栈顶元素,这时完成了一次出队的操作,但是如下一次出队呢?是否就不需要再倒一遍给StackA了?那么如何判断每次出队是否需要导数据? 想省去判断的步骤也可以,但是每次pop步骤可能得来回倒两遍,时间上会有一定程度的浪费.

所以在这里可以换一种思路,仔细观察不难发现,给stackA压栈后,下一步执行出队操作时, 先把所有数据导给StackB,然后StackB正常出栈就是出队的操作,那么之后再有入队操作就把需要入队的数据压栈给StackA,出队操作就让StackB出栈,如果StackB为空栈,就再执行一遍从StackA导出所有数据给StackB的操作,如此一来就实现了两个栈的合理运用实现队列的效果
所以两个栈都有各自负责的功能,重新命名为StackPush和StackPop似乎更为合适

编写代码实现:


xxxxxxxxxx
133
1
#include <assert.h>
2
typedef int StackDataType;
3

4
typedef struct StackNode
5
{
6
    StackDataType* data;
7
    int top;
8
    int capacity;
9
}STNode;
10

11
typedef struct {
12
    STNode STPush;
13
    STNode STPop;
14
} MyQueue;
15
void StackInit(STNode*st);
16
void StackPush(STNode*st,StackDataType x);
17
StackDataType StackPop(STNode*st);
18
bool StackEmpty(STNode*st);
19
StackDataType StackTop(STNode*st);
20
void StackDestroy(STNode*st);
21

22

23
void StackInit(STNode*st)
24
{
25
    assert(st);
26
    st->top=0;
27
    st->capacity=0;
28
    st->data = NULL;
29
}
30
void StackPush(STNode*st, StackDataType x)
31
{
32
    assert(st);
33
    if(st->top == st->capacity)
34
    {
35
        int newcapacity = st->capacity==0?4:st->capacity*2;
36
        StackDataType* tmp = (StackDataType*)realloc(st->data, sizeof(StackDataType)*newcapacity);
37
        if(tmp ==NULL)
38
        {
39
            perror("realloc fail");
40
            return;
41
        }
42
        st->data = tmp;
43
        st->capacity = newcapacity;
44
    }
45
    st->data[st->top++] = x;
46
}
47
StackDataType StackPop(STNode*st)
48
{
49
    assert(st);
50
    assert(!StackEmpty(st));
51
    StackDataType ret = StackTop(st);
52
    st->top--;
53
    return ret;
54
}
55
bool StackEmpty(STNode*st)
56
{
57
    assert(st);
58
    return st->top==0;
59
}
60
StackDataType StackTop(STNode*st)
61
{
62
    assert(st);
63
    assert(!StackEmpty(st));
64
    return st->data[st->top-1];
65
}
66
void StackDestroy(STNode*st)
67
{
68
    assert(st);
69
    free(st->data);
70
}
71

72
void StackMove(STNode*STPush, STNode*STPop)
73
{
74
    while(!StackEmpty(STPush))
75
    {
76
        StackDataType __top = StackTop(STPush);
77
        StackPop(STPush);
78
        StackPush(STPop, __top);
79
    }
80
}
81

82
MyQueue* myQueueCreate() {
83
    MyQueue* Mq = (MyQueue*)malloc(sizeof(MyQueue));
84
    StackInit(&Mq->STPush);
85
    StackInit(&Mq->STPop);
86
    return Mq;
87
}
88

89
void myQueuePush(MyQueue* obj, int x) {
90
    StackPush(&obj->STPush, x);
91
}
92

93
int myQueuePop(MyQueue* obj) {
94
    if(StackEmpty(&obj->STPop))
95
    {
96
        StackMove(&obj->STPush, &obj->STPop);
97
        return StackPop(&obj->STPop);
98
    }
99

100
    return StackPop(&obj->STPop);
101
}
102

103
int myQueuePeek(MyQueue* obj) {
104
    if(StackEmpty(&obj->STPop))
105
    {
106
        StackMove(&obj->STPush, &obj->STPop);
107
    }
108
    return StackTop(&obj->STPop);
109
}
110

111
bool myQueueEmpty(MyQueue* obj) {
112
    return StackEmpty(&obj->STPush) && StackEmpty(&obj->STPop);
113
}
114

115
void myQueueFree(MyQueue* obj) {
116
    StackDestroy(&obj->STPush);
117
    StackDestroy(&obj->STPop);
118
    free(obj);
119
}
120

121
/**
122
 * Your MyQueue struct will be instantiated and called as such:
123
 * MyQueue* obj = myQueueCreate();
124
 * myQueuePush(obj, x);
125
 
126
 * int param_2 = myQueuePop(obj);
127
 
128
 * int param_3 = myQueuePeek(obj);
129
 
130
 * bool param_4 = myQueueEmpty(obj);
131
 
132
 * myQueueFree(obj);
133
*/

用例通过

提交通过

`leetcode`题: 239. 滑动窗口最大值

题目描述:

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：


xxxxxxxxxx
11
1
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
2
输出：[3,3,5,5,6,7]
3
解释：
4
滑动窗口的位置                最大值
5
---------------               -----
6
[1  3  -1] -3  5  3  6  7       3
7
1 [3  -1  -3] 5  3  6  7       3
8
1  3 [-1  -3  5] 3  6  7       5
9
1  3  -1 [-3  5  3] 6  7       5
10
1  3  -1  -3 [5  3  6] 7       6
11
1  3  -1  -3  5 [3  6  7]      7

示例 2：


xxxxxxxxxx
2
1
输入：nums = [1], k = 1
2
输出：[1]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

这道题使用双端队列（deque）来解题是完全可行的,当然在解题前先捋一下思路:

解题步骤
初始化：
创建一个双端队列（存储索引）和一个数组（存储结果）。
定义两个指针 front 和 rear 来表示队列的头部和尾部。
遍历数组：
对数组中的每个元素执行以下操作：
移除旧的元素索引：如果队列头部的元素（最大值）不在当前窗口内（即其索引小于当前索引减去窗口大小），则将其从队列头部移除。
维持队列递减：从队列尾部开始，移除所有小于当前元素值的索引，因为这些元素不可能成为当前窗口的最大值。
添加新元素索引：将当前元素的索引添加到队列尾部。
记录结果：
当窗口形成（即遍历到的元素索引大于等于窗口大小减1时），将队列头部元素对应的值加入结果数组，因为队列头部的元素是当前窗口的最大值。
假设数组为 [1,3,-1,-3,5,3,6,7]，窗口大小为 3。
当处理前三个元素 [1,3,-1] 后，队列存储的索引为 [1, 2]，因为 3 > -1，所以下标1对应的值是这个窗口的最大值。
接下来滑动到 [3,-1,-3]，由于索引 0（对应元素 1）已经不在窗口内，我们将其从队列头部移除。队列变为 [1, 2, 3]。
以此类推，我们继续遍历数组，不断更新队列和结果数组。
需要注意的是:
队列始终保持递减，确保队列头部是当前窗口的最大值。
队列存储的是元素的索引，而不是元素的值，这样可以知道队列头部的元素是否仍在当前窗口内。
使用双端队列是因为我们需要从两端进行操作：头部移除旧的最大值，尾部添加新的潜在最大值。

编写代码实现:


xxxxxxxxxx
33
1
/**
2
 * Note: The returned array must be malloced, assume caller calls free().
3
 */
4
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
5
    int* result = (int*)malloc(sizeof(int) * (numsSize - k + 1));
6
    int* deque = (int*)malloc(sizeof(int) * numsSize);
7
    int front = 0, rear = -1;
8
    int index = 0;
9
    //deque存储的是nums元素对应的下标
10
    for (int i = 0; i < numsSize; i++) {
11
        // 移除不在窗口内的元素的索引
12
        while (front <= rear && deque[front] < i - k + 1) {
13
            front++;
14
        }
15

16
        // 移除所有比当前元素小的元素的索引
17
        while (front <= rear && nums[i] >= nums[deque[rear]]) {
18
            rear--;
19
        }
20

21
        // 添加当前元素的索引
22
        deque[++rear] = i;
23

24
        // 窗口形成后开始填充结果
25
        if (i >= k - 1) {
26
            result[index++] = nums[deque[front]];
27
        }
28
    }
29

30
    *returnSize = index;
31
    free(deque);
32
    return result;
33
}

补充说明:CPU缓存命中

我们知道现在CPU核心数越来越多,使用的新一代CPU基本上都已经有了三级缓存(L1, L2, L3)

L1缓存分成两种，一种是指令缓存，一种是数据缓存。L2缓存和L3缓存不分指令和数据。
L1和L2缓存在每一个CPU核中，L3则是所有CPU核心共享的内存。
L1、L2、L3的缓存容量越离CPU近就越小，速度也越快，越离CPU远，速度也越慢,容量也越大。
再往后面就是内存，内存的后面就是硬盘。
我们的数据就从内存开始，先加载到到L3，再到L2，再到L1，最后到寄存器进行CPU计算。

当CPU需要访问内存中的数据时，它首先检查这些数据是否已经在缓存中（缓存命中）。如果在缓存中找到数据，就不需要访问较慢的主内存，从而加快了数据处理速度。如果数据不在缓存中（缓存未命中），则必须从主内存中加载数据到缓存中。

缓存基本上来说就是CPU把内存上的数据加载到离自己近的地方，为了提高效率每次都会加载一块连续的内存空间，有个专业术语叫“Cache Line”，市面上主流的CPU的Cache Line 是 64 Bytes（也有的CPU用32 Bytes和128 Bytes），64 Bytes也就是16个32位的整型，这就是CPU从内存中一次性加载上来的数据单位。

拿我的CPU AMD Ryzen 5950X来举例, 网页链接techpowerup 该网页记录了近几年来发布的CPU处理器的性能参数,可以查询到我的CPUL1有64KB

比如：Cache Line单位是（64 Bytes），所以先把Cache分布多个Cache Line， L1有64KB，那么，64KB/64B = 1024 个 Cache Line。

顺序表
顺序表是一种线性数据结构，元素在内存中是连续存储的。访问顺序表中的一个元素时，相邻的元素往往也会被加载到CPU缓存中。这是因为现代CPU缓存通常采用了预取（prefetching）机制，会自动加载临近的内存区域到缓存中。
缓存友好性：顺序表因其连续的内存布局而具有较高的缓存友好性。连续的内存布局意味着更高的空间局部性（spatial locality），即一旦访问了一个数据项，接下来访问其相邻数据项的概率较高。
链表
链表是由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的元素在内存中通常是非连续的。
缓存不友好性：链表的这种非连续存储方式导致其缓存不友好。每次访问链表的一个节点时，下一个节点可能并没有被预先加载到缓存中，因为它们在内存中的位置可能相距甚远，降低了空间局部性。
缓存污染: 每次读取链表中的元素也同样是按照块的大小从内存加载进缓存, 就很有可能导致每次加载的这个块中的其他数据是无法利用的,如果 CPU 缓存有限，频繁的缓存未命中会导致缓存中的数据被频繁替换，这可能会污染缓存，因为原本可能还会被访问的数据被新加载的（但可能用不到的）数据替换掉了。这种缓存污染可以导致 CPU 的效率降低，因为它不得不频繁地在缓存和主内存之间传输数据，而不能有效地利用缓存。在需要频繁遍历的场景中，链表相比于如数组这样的连续存储结构，在性能上会有显著的不足。
CPU高速缓存命中率的关系
顺序表和高命中率：顺序表的连续内存布局有助于提高CPU缓存的命中率。当顺序遍历顺序表时，由于高空间局部性，缓存命中的概率更高。
链表和低命中率：链表的非连续存储方式通常导致较低的缓存命中率。当遍历链表时，由于每个元素的位置可能分散在内存中的不同地方，每次访问节点都可能导致缓存未命中，从而需要从主内存中加载数据。

搜索此博客

稳健咖啡馆

栈和队列

栈和队列

栈的基本概念

C语言实现栈

`stack.h`:

`stack.c`:

测试函数(展示)

`test.c`

栈的应用示例

`leetcode`题:有效的括号原题链接

接下来开始使用C语言代码实现这样一个思路

编写代码:

队列的基本概念

C语言实现队列

然后实现队列函数的定义

`Queue.c`:

测试函数(展示)

`test.c`

队列的应用示例

`leetcode`题: 225.用队列实现栈

编写代码实现

`leetcode`题:232.用栈实现队列

编写代码实现:

`leetcode`题: 239. 滑动窗口最大值

解题步骤

编写代码实现:

补充说明:CPU缓存命中

顺序表

链表

CPU高速缓存命中率的关系

评论

发表评论

栈和队列

栈和队列

栈的基本概念

C语言实现栈

stack.h:

stack.c:

测试函数(展示)

test.c

栈的应用示例

leetcode题:有效的括号 原题链接

接下来开始使用C语言代码实现这样一个思路

编写代码:

队列的基本概念

C语言实现队列

然后实现队列函数的定义

Queue.c:

测试函数(展示)

test.c

队列的应用示例

leetcode题: 225.用队列实现栈

编写代码实现

leetcode题:232.用栈实现队列

编写代码实现:

leetcode题: 239. 滑动窗口最大值

解题步骤

编写代码实现:

补充说明:CPU缓存命中

顺序表

链表

CPU高速缓存命中率的关系

评论

发表评论

`stack.h`:

`stack.c`:

`test.c`

`leetcode`题:有效的括号原题链接

`Queue.c`:

`test.c`

`leetcode`题: 225.用队列实现栈

`leetcode`题:232.用栈实现队列

`leetcode`题: 239. 滑动窗口最大值