【C语言】三道例题让你彻底学会栈和队列
慕雪年华

[TOC]

前言

本篇博客,将带着大家刷3道非常经典的OJ题。它们并不算特别难,但对我们理解数据结构中栈和队列的概念有很大的帮助。

如果你还不了解,可以看看我之前的博客👉点我

队列的博客就不写啦,本篇刷题的时候会提到队列的操作

话不多说,直接开始吧!


1.用队列实现栈

leetcode:225. 用队列实现栈

image-20220330132359088

这道题的要求很简单,用两个队列来模拟栈的实现。

我们知道,队列的操作是从后进,从前出,这就和我们在餐厅排队一样,先进入餐厅排队的人先得到座位。

而栈是遵循上进上出的,即栈只能在栈顶插入元素和删除元素

两个队列要如何结合,才能实现栈的要求呢?

1.1思路

首先我们讲数据push到其中一个队列中

用队列实现栈1

如果要访问此时的栈顶,使用队列中的tail尾指针来访问,即题目要求的TOP函数

当我们需要pop数据的时候,将队列中的N-1个数据全部移动到另外一个队列里,再将最后的栈顶数据删除并返回

  • 最终的目的就是保证一个队列为空,另外一个队列保存数据

用队列实现栈2

这样就达成了栈只能在栈顶删除数据的要求

最后还有一个函数是boolean empty() 如果栈是空的,返回 true ;否则,返回 false

  • 当两个队列中都没有数据的时候,这个模拟的栈就是空的;
  • 只要其中一个队列有数据的时候,就代表这个栈是有数据的。

1.2队列的代码

你可能会注意到,这道题中并没有给我们初始的队列代码,也就是说我们需要“造轮子”,将自己写的C语言队列代码放在前头

  • 这也是C语言在写一些OJ题目时不方便的原因

image-20220330134840833

这里我贴出一个队列的代码,大家可以复制到自己的编译器上测试一下。

如果有不理解的地方,可以在评论区提出

  • 和栈的代码实现不同,队列使用链表的方式更加方便。其相当于一个只能尾插和头删的单链表
  • 为了方便我们找尾进行尾插,这里定义了另外一个结构体类型Queue,其中tail指针指向链表的尾部,方便尾插(否则每次尾插都需要遍历)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
typedef int QDataType;

typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;

typedef struct Queue
{//这个结构体里有两个指针
QNode* head;//头
QNode* tail;//尾
}Queue;

//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
//摧毁
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* findtail = pq->head;//找尾挨个挨个free
while (findtail)
{
QNode* next = findtail->next;
free(findtail);
findtail = next;
}

pq->head = NULL;
pq->tail = NULL;
}
//插入(尾插)
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
printf("Push err\n");
exit(-1);
}

newnode->data = x;
newnode->next = NULL;

if (pq->tail == NULL)
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
return;
}
//删除(头删)
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);//判断是否为空

if (pq->head->next == NULL)
{
free(pq->head);
pq->head = NULL;
pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
//判断是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
//在C中bool类型和int类型可以直接混用
return pq->head == NULL && pq->tail == NULL;
}
//返回它的长度
size_t QueueSize(Queue* pq)
{
assert(pq);

size_t size = 0;
QNode* findtail = pq->head;

while (findtail)
{
size++;
findtail = findtail->next;
}

return size;
}
//返回头
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);

return pq->head->data;
}
//返回尾部
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);

return pq->tail->data;
}

1.3本题的代码

将上述的队列代码拷贝在题目所给模板之前后,我们就可以开始写这道题需要的代码实现了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//创建两个队列
typedef struct {
Queue q1;
Queue q2;
} MyStack;


MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
//因为是在函数中,所以需要使用动态内存管理
if (pst == NULL)//malloc可能失败
return NULL;

QueueInit(&pst->q1);//直接调用队列的函数进行初始化
QueueInit(&pst->q2);

return pst;
}

void myStackPush(MyStack* obj, int x) {
assert(obj);
//在push的时候,需要找到不为空的队列进行push
if (!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}

int myStackPop(MyStack* obj) {
assert(obj);
//通过判断找到为空和不为空的队列
Queue* empty = &obj->q1;
Queue* unempty = &obj->q2;
if (!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
unempty = &obj->q1;
}

while (QueueSize(unempty) > 1)
{
int top1 = QueueFront(unempty);
QueuePush(empty, top1);
QueuePop(unempty);
}
//先保存top,再进行出队列操作
int top = QueueFront(unempty);
QueuePop(unempty);

return top;//返回报错的top
}

int myStackTop(MyStack* obj) {
assert(obj);

if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}

bool myStackEmpty(MyStack* obj) {
assert(obj);
//只有两个队列都为空的时候,模拟的栈才是空
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
assert(obj);

QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);//因为是动态内存开辟的,所以最后销毁的时候还需要销毁模拟栈的结构体

return;
}

16个用例都完美通过了!

image-20220330135927133


2.用栈实现队列

leetcode: 232. 用栈实现队列

image-20220330140031669

有了上一道题目的经验,这道题的实现就不那么困难了。

2.1思路

  • 栈的特点是只能在栈顶删除和插入数据

  • 队列需要在队尾插入数据,在对头删除数据

假设现在我们有下面这两个栈,第一个栈里面存放了1 2 3 4的数据

需要进行队列的POP操作时,我们需要删除的是最底部的1

image-20220330140654849

可以先将栈中的所有数据pop并push到另外一个空栈中,再将最后一个数据存放后删除,返回存放的值。

image-20220330140840445

这部分操作与第一题中的操作很像,但是有一个致命的问题:在新的栈里的数据和我们原本想要的数据是相反的!

1
2
3
1 2 3 4 删除1
原本数据 2 3 4
实际数据 4 3 2

解决这个问题的方法只有一个,那就是把这一批数据再复制回原本的栈中,它的顺序就对了

image-20220330141357363

而我自己写的栈是用数组实现的,题目要求的peek函数可以直接通过访问非空栈的0下标元素得到

empty函数同理,只有两个栈中都为空时,模拟的队列才是空的


2.2栈的代码

栈的实现在本文开头的博客链接中有详细解释,这里不再复述

回到开头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;

// 初始化
void StackInit(Stack* ps)
{
STDataType* new = (STDataType*)malloc(sizeof(STDataType) * 4);
if (new == NULL)
{
exit(-1);
}
else
{
ps->a = new;
ps->top = 0;
ps->capacity = 4;
}
}

// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);

free(ps->a);
ps->a = NULL;

ps->capacity = 0;
ps->top = 0;
}

// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->top == ps->capacity)
{
STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2);
if (new == NULL)
{
exit(-1);
}
else
{
ps->a = new;
ps->capacity *= 2;
}
}
ps->a[ps->top] = data;
ps->top++;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
if (ps->top > 0)
(ps->top)--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];

}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
// 检测栈是否为空,如果为空返回true,如果不为空返回false
bool StackEmpty(Stack* ps)
{
assert(ps);
if (ps->top == 0)
return true;
else
return false;
}

void StackPrint(Stack* ps)
{
assert(ps);
int n = ps->top;
for (int i = 0; i < n; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}

2.3本题的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
typedef struct {
Stack st1;
Stack st2;
} MyQueue;

MyQueue* myQueueCreate() {
MyQueue* qt = (MyQueue*)malloc(sizeof(MyQueue));
if (qt == NULL)
return NULL;

StackInit(&qt->st1);
StackInit(&qt->st2);

return qt;
}

void myQueuePush(MyQueue* obj, int x) {
assert(obj);
if (!StackEmpty(&obj->st1))
{
StackPush(&obj->st1, x);
}
else
{
StackPush(&obj->st2, x);
}
return;
}

int myQueuePop(MyQueue* obj) {
assert(obj);

Stack* empty = &obj->st1;
Stack* nonempty = &obj->st2;
if (!StackEmpty(&obj->st1))
{
Stack* empty = &obj->st2;
Stack* nonempty = &obj->st1;
}

while (StackSize(nonempty) > 1)
{
int top1 = StackTop(nonempty);
StackPush(empty, top1);
StackPop(nonempty);
}

int top = StackTop(nonempty);
StackPop(nonempty);//原本不为空的的最后一个top被取出
//需要将数据再倒放一遍,否则访问是反的
while (StackSize(empty) > 0)
{
int top2 = StackTop(empty);
StackPush(nonempty, top2);
StackPop(empty);
}

return top;
}

int myQueuePeek(MyQueue* obj) {
assert(obj);

Stack* empty = &obj->st1;
Stack* nonempty = &obj->st2;
if (!StackEmpty(&obj->st1))
{
Stack* empty = &obj->st2;
Stack* nonempty = &obj->st1;
}

//这里的栈是用数组实现的,可以直接访问首位元素
return nonempty->a[0];
}

bool myQueueEmpty(MyQueue* obj) {
assert(obj);

return StackEmpty(&obj->st1) && StackEmpty(&obj->st2);
}

void myQueueFree(MyQueue* obj) {
assert(obj);

StackDestroy(&obj->st1);
StackDestroy(&obj->st2);
free(obj);

return;
}

image-20220330141959314


3.设计循环队列

leetcode:622. 设计循环队列

image-20220330142034892

这道题最主要的突破口,就是弄明白题目所说的循环队列的意思

实际上他就是一个下图所示的队列,当tail使用完已有空间后,可以跳到前面继续使用之前开辟好的空间,而不需要额外的扩容空间。

image-20220330142328532

为了方便找头以及找尾,本体将使用数组方式来实现它的代码


3.1思路

确定是数组形式后,我们就要来思考两个问题:什么时候队列为空?什么时候队列是满?

3.1.1判断是否为空

这个看起来好像非常简单,只要头指针和尾指针相同,队列不就是空的了嘛!

image-20220330142638400

这个想法对,但有有点瑕疵,即我们怎么界定空和非空的界限?

3.1.2判断是否为满

每插入一个数据,tail指针就会往后++一次,指向已有数据的下一位

image-20220330142755076

当下一位也被装好了数据之后,tail就会回到开头,来到front指针的位置!

image-20220330142858967

这个时候,tail=front,但是队列实际上已经满了!

这就让我们不得不思考,如何将这两种情况区分开来?

image-20220330143106322

啊哈哈哈哈,答案来喽:

如果需要的数据为K个,为队列的数组开辟K+1个空间

这时候,只要tail+1=front,就代表队列已经满了。多出来的这一个空间不存放数据

  • 注意:这个空间不一定是最末尾的哪一个,它会随着队列的插入、删除操作而移动
  • 当tail在尾部,tail=k(注意tail是下标而不是指针)且front=0时,队列为满

image-20220330143244364

这样就很完美的把空和满两种情况给区分开来了!


3.2本题代码实现

需要注意题目给出的返回值要求,依照题目函数要求来编写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
typedef struct {
int* data;
int front;
int tail;
int k;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);//为了让这个函数能在它之前使用

MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* qt = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if (qt == NULL)
return NULL;

qt->data = (int*)malloc(sizeof(int) * (k + 1));
qt->k = k;




qt->front = 0;
qt->tail = 0;

return qt;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
if (myCircularQueueIsFull(obj))
return false;

obj->data[obj->tail] = value;
//obj->tail++;
//obj->tail %= obj->k+1;//保证数据在数组内部
if (obj->tail == obj->k)
{
obj->tail = 0;
}
else
{
obj->tail ++ ;
}


return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
if (myCircularQueueIsEmpty(obj))
return false;

if (obj->front == obj->k)
{//front在预先开辟的第4个位置上
obj->front = 0;
}
else
{
obj->front++;
}

return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
if (myCircularQueueIsEmpty(obj))
return -1;

return obj->data[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
if (myCircularQueueIsEmpty(obj))
return -1;

if (obj->tail == 0)
{
return obj->data[obj->k];
}
else
{
return obj->data[obj->tail - 1];
}

return -1;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->tail == obj->front;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
if ((obj->tail == obj->k) && obj->front == 0)
{
return true;
}
else
{
return obj->tail + 1 == obj->front;
}
}

void myCircularQueueFree(MyCircularQueue* obj) {
assert(obj);

free(obj->data);
free(obj);

return;
}

image-20220330151955395

结语

刷完这3道题,有没有感觉数据结构的很多内容都是关系紧密的?🤩

只要我们把链表和顺序表的内容搞得透彻,栈和队列这部分就没那么难了!

加油!