[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

1.4优化设计

使用一个队列就能实现这个功能。

  • 数据入队列；
  • 需要top/pop的时候，将队列前的数据全部重新移动到队列尾部，留下最后一个，就是栈顶数据；
  • top函数调用完毕后需要将剩下的这个数据也移动到队列尾部；
  • pop函数调用完毕后将size--;

代码如下

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
class MyStack {
    int size = 0;
    queue<int> que;
public:
    MyStack() {

    }
    
    void push(int x) {
        que.push(x);
        size++;
    }
    
    int pop() {
        // 把前面的数据全部移动到后面去
        int count = size;
        while(count-->1){
            int temp = que.front();
            que.pop();
            que.push(temp);
        }
        // 剩下的是需要删除的
        int ret = que.front();
        que.pop();
        size--;
        return ret;
    }
    
    int top() {
        // 这里不能复用函数了，因为位置移动后必须要删除才是对的，否则会乱
        // 把前面的数据全部移动到后面去
        int count = size;
        while(count-->1){
            int temp = que.front();
            que.pop();
            que.push(temp);
        }
        // 剩下的是top函数
        int ret = que.front();
        que.push(ret);
        que.pop(); // 需要把这个数字也移动到后面去
        return ret;
    }
    
    bool empty() {
        return size == 0;
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

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

2.4优化设计

上面的这个方法在peek和pop的时候都需要把数据搬两次，比较麻烦；

但使用另外一种方式，一个做入栈，一个做出栈，就可以减少数据在两个栈间拷贝的次数。

  • 队列插入数据的时候，往入栈插入；
  • 队列删除数据的时候，将入栈的所有数据弹出并插入出栈，此时出栈顶部就是需要删除的数据；
  • 新数据插入，继续往入栈插入，重复上述两个步骤。

出队列的时候需要遵循先入先出的顺序，如果出栈中有数据，那么就直接取就是需要出队列的数据了。出栈中没有数据，才需要将入栈中的所有数据都放入出栈。

代码如下

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
class MyQueue {
    stack<int> stIn,stOut;
    int size = 0;
public:
    MyQueue() {

    }
    
    void push(int x) {
        stIn.push(x);
        size++;
    }
    
    int pop() {
        int ret = peek(); // 复用函数
        stOut.pop();
        size--;
        return ret;
    }
    
    int peek() {
        if(stOut.empty()){
            // stOut为空，将stIn的全都移动过去
            int count = size;
            while(count--)
            {
                stOut.push(stIn.top());
                stIn.pop();
            }   
        }
        // 此时stOut顶部就是需要出队列的数据
        int ret = stOut.top();
        return ret;
    }
    
    bool empty() {
        return size == 0;
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

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道题，有没有感觉数据结构的很多内容都是关系紧密的？🤩

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

加油！