爆肝两万字，我爷爷都看的懂的《栈和队列》，建议各位观众姥爷先收藏

全栈程序员站长

发布于 2022-09-05 10:07:45

3610

发布于 2022-09-05 10:07:45

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

文章目录

一、栈

💦 栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO (Last In First Out) 的原则；同时对于栈来说，一种入栈顺序对应多种出栈顺序

栈有两个经典的操作

1️⃣ 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

2️⃣ 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

💦 栈的实现

这里对于栈的实现我们既可以选择数组也可以和选择链表两者的效率都差不多，但是还是建议使用数组

1.初始化

函数原型

函数实现

void StackInit(ST* ps)
{ 
   
	assert(ps);
	//初始化
	ps->a = NULL;
	ps->top = 0;
	ps->capacicy = 0;
}

2.插入

函数原型

函数实现

void StackPush(ST* ps, STDatatype x)
{ 
   
	assert(ps);
	//检查空间，满了就增容
	if (ps->top == ps->capacicy)
	{ 
   
		//第一次开辟空间容量为4，其它次容量为当前容量*2
		int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;
		//第一次开辟空间，a指向空，realloc的效果同malloc
		STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);
		//检查realloc
			//realloc失败
		if (tmp == NULL)
		{ 
   
			printf("realloc fail\n");
			exit(-1);
		}
			//realloc成功
		ps->a = tmp;
		ps->capacicy = newcapacity;
	}
	//插入数据 
	ps->a[ps->top] = x;
	ps->top++;
}

3.判空

函数原型

函数实现

bool StackEmpty(ST* ps)
{ 
   
	assert(ps); 
	//等于0是真，否则为假
	return ps->top == 0;
}

4.删除

函数原型

函数实现

void StackPop(ST* ps)
{ 
   
	assert(ps);
	//删除的话得保证指向的空间不为空
	assert(!StackEmpty(ps));
	//删除
	--ps->top;
}

5.长度

函数原型

函数实现

int StackSize(ST* ps)
{ 
   
	assert(ps);
	//此时的top就是长度
	return ps->top;
}

6.栈顶

函数原型

函数实现

STDatatype StackTop(ST* ps)
{ 
   
	assert(ps);
	//找栈顶的话得保证指向的空间不为空
	assert(!StackEmpty(ps));
	//此时的top-1就是栈顶数据
	return ps->a[ps->top - 1];
}

7.销毁

函数原型

函数实现

void StackDestory(ST* ps)
{ 
   
	assert(ps);
	//a为真代表它指向动态开辟的空间
	if (ps->a)
	{ 
   
		free(ps->a);
	}
	ps->a = NULL;
	ps->top = 0;
	ps->capacicy = 0;
}

💦 完整代码

这里需要三个文件

1️⃣ Static.h，用于函数的声明

2️⃣ Static.c，用于函数的定义

3️⃣ Test.c，用于测试函数

🧿 Stack.h

#pragma once

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

//结构体
typedef int STDatatype;
typedef struct Stack
{ 
   
	STDatatype* a; //指向动态开辟的空间
	int top; //栈顶
	int capacicy; //容量
}ST;

//函数 
//注意链表和顺序表我们写Print，但是栈不写，因为如果栈可以Print的话，就不符合后进先出了
	//初始化
void StackInit(ST* ps);
	//插入
void StackPush(ST* ps, STDatatype x);
	//判空
bool StackEmpty(ST* ps);
	//删除
void StackPop(ST* ps);
	//长度
int StackSize(ST* ps);
	//栈顶
STDatatype StackTop(ST* ps);
	//销毁
void StackDestory(ST* ps);

🧿 Stack.c

#include"Stack.h"

void StackInit(ST* ps)
{ 
   
	assert(ps);
	//初始化
	ps->a = NULL;
	ps->top = 0;
	ps->capacicy = 0;
}
void StackPush(ST* ps, STDatatype x)
{ 
   
	assert(ps);
	//检查空间，满了就增容
	if (ps->top == ps->capacicy)
	{ 
   
		//第一次开辟空间容量为4，其它次容量为当前容量*2
		int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;
		//第一次开辟空间，a指向空，realloc的效果同malloc
		STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);
		//检查realloc
			//realloc失败
		if (tmp == NULL)
		{ 
   
			printf("realloc fail\n");
			exit(-1);
		}
			//realloc成功
		ps->a = tmp;
		ps->capacicy = newcapacity;
	}
	//插入数据 
	ps->a[ps->top] = x;
	ps->top++;
}
bool StackEmpty(ST* ps)
{ 
   
	assert(ps); 
	//等于0是真，否则为假
	return ps->top == 0;
}
void StackPop(ST* ps)
{ 
   
	assert(ps);
	//删除的话得保证指向的空间不为空
	assert(!StackEmpty(ps));
	//删除
	--ps->top;
}
int StackSize(ST* ps)
{ 
   
	assert(ps);
	//此时的top就是长度
	return ps->top;
}
STDatatype StackTop(ST* ps)
{ 
   
	assert(ps);
	//找栈顶的话得保证指向的空间不为空
	assert(!StackEmpty(ps));
	//此时的top-1就是栈顶数据
	return ps->a[ps->top - 1];
}
void StackDestory(ST* ps)
{ 
   
	assert(ps);
	//a为真代表它指向动态开辟的空间
	if (ps->a)
	{ 
   
		free(ps->a);
	}
	ps->a = NULL;
	ps->top = 0;
	ps->capacicy = 0;
}

🧿 Test.c

#include"Stack.h"

int main()
{ 
   
	ST st;
	//初始化
	StackInit(&st);
	//插入+删除
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);
	StackPop(&st);
	StackPop(&st);
	//长度
	StackSize(&st);
	//栈顶
	StackTop(&st);
	//销毁
	StackDestory(&st);
	return 0;
}

二、队列

💦 队列的概念及结构

相比栈，队列的特性和栈是相反的。
它只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO (First In First Out) 的特性。
入队列：进行插入操作的一端称为队尾；出队列：进行删除操作的一端称为队头
对于队列来说，一种入队顺序，只有一种出队顺序

队列的拓展：实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

为了能使用Q.rear == Q.front 来区别是队空还是队满,我们常常认为出现左图时的情况即为队空的情况，此时: rear == front；而右图的情况即为队满的情况，此时：rear + 1 == front

关于环形队列在下面的的栈和队列面试题中会讲到

队列的应用：

1️⃣ 实际中要保证公平排队的地方可以用它

2️⃣ 广度优先遍历

💦 队列的实现

这里对于队列的实现我们使用链表的方式

1.初始化

函数原型

函数实现

void QueueInit(Queue* pq)
{ 
   
	assert(pq);
	//把2个指针置空
	pq->phead = pq->ptail = NULL;
}

2.插入

函数原型

函数实现

void QueuePush(Queue* pq, QDataType x)
{ 
   
	assert(pq);
	//malloc空间,如果需要频繁的开辟空间建议再实现一个BuyQueueNode用于malloc
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{ 
   
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//第一次插入
	if (pq->phead == NULL)
	{ 
   
		pq->phead = pq->ptail = newnode;
	}
	//非第一次插入
	else
	{ 
   
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
}

3.判空

函数原型

函数实现

bool QueueEmpty(Queue* pq)
{ 
   
	assert(pq);
	//空链表返回true，非空链表返回false
	return pq->phead == NULL;
}

4.删除

函数原型

函数实现

void QueuePop(Queue* pq)
{ 
   
	assert(pq);
	//链表为空时不能删除
	assert(!QueueEmpty(pq));
	//只有一个节点的情况
	if (pq->phead->next == NULL)
	{ 
   
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多个节点的情况
	else
	{ 
   
		QueueNode* next = pq->phead->next;
		free(pq->phead)	;
		pq->phead = next;
	}
}

5.长度

函数原型

函数实现

QDataType QueueSize(Queue* pq)
{ 
   
	assert(pq);
	//如果需要频繁的调用QueueSize这个接口，可以在Queue这个结构体中增加一个成员用于记录长度
	int sz = 0;
	QueueNode* cur = pq->phead;
	while (cur)
	{ 
   
		sz++;
		cur = cur->next;
	}
	return sz;
}

6.取头

函数原型

函数实现

QDataType QueueFront(Queue* pq)
{ 
   
	assert(pq);
	//链表为空时不能取头
	assert(!QueueEmpty(pq));
	
	return pq->phead->data;
}

7.取尾

函数原型

函数实现

QDataType QueueBack(Queue* pq)
{ 
   
	assert(pq);
	//链表为空时不能取尾
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}

8.销毁

函数原型

函数实现

void QueueDestory(Queue* pq)
{ 
   
	assert(pq);
	
	QueueNode* cur = pq->phead;
	//遍历链表
	while (cur)
	{ 
   
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
}

💦 完整代码

这里需要三个文件

1️⃣ Queue.h，用于函数的声明

2️⃣ Queue.c，用于函数的定义

3️⃣ Test.c，用于测试函数

🧿 Queue.h

#pragma once

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

//结构体
typedef int QDataType;
typedef struct QueueNode
{ 
   
	struct QueueNode* next; //指向下一个节点
	QDataType data; //存储整型数据
}QueueNode;

typedef struct Queue
{ 
   
	QueueNode* phead;//头指针
	QueueNode* ptail;//尾指针
}Queue;

//函数
void QueueInit(Queue* pq); 
void QueuePush(Queue* pq, QDataType x);
bool QueueEmpty(Queue* pq);
void QueuePop(Queue* pq);
QDataType QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueDestory(Queue* pq);

🧿 Queue.c

#include"Queue.h"

void QueueInit(Queue* pq)
{ 
   
	assert(pq);
	//把2个指针置空
	pq->phead = pq->ptail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{ 
   
	assert(pq);
	//malloc空间,如果需要频繁的开辟空间建议再实现一个BuyQueueNode用于malloc
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{ 
   
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//第一次插入
	if (pq->phead == NULL)
	{ 
   
		pq->phead = pq->ptail = newnode;
	}
	//非第一次插入
	else
	{ 
   
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
}
bool QueueEmpty(Queue* pq)
{ 
   
	assert(pq);
	//空链表返回true，非空链表返回false
	return pq->phead == NULL;
}
void QueuePop(Queue* pq)
{ 
   
	assert(pq);
	//链表为空时不能删除
	assert(!QueueEmpty(pq));
	//只有一个节点的情况
	if (pq->phead->next == NULL)
	{ 
   
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多个节点的情况
	else
	{ 
   
		QueueNode* next = pq->phead->next;
		free(pq->phead)	;
		pq->phead = next;
	}
}
QDataType QueueSize(Queue* pq)
{ 
   
	assert(pq);
	//如果需要频繁的调用QueueSize这个接口，可以在Queue这个结构体中增加一个成员用于记录长度
	int sz = 0;
	QueueNode* cur = pq->phead;
	while (cur)
	{ 
   
		sz++;
		cur = cur->next;
	}
	return sz;
}
QDataType QueueFront(Queue* pq)
{ 
   
	assert(pq);
	//链表为空时不能取头
	assert(!QueueEmpty(pq));
	
	return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{ 
   
	assert(pq);
	//链表为空时不能取尾
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}
void QueueDestory(Queue* pq)
{ 
   
	assert(pq);
	
	QueueNode* cur = pq->phead;
	//遍历链表
	while (cur)
	{ 
   
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
}

🧿 Test.c

#include"Queue.h"

int main()
{ 
   
	//1、传二级指针
	//2、返回值
	//3、带哨兵位的头节点
	//4、嵌套结构体 (这里使用这种方式)
	QueueNode q;
	//初始化
	QueueInit(&q);
	//插入
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	//删除
	QueuePop(&q);
	QueuePop(&q);
	//取头
	QueueFront(&q);
	//取尾
	QueueBack(&q);
	//释放
	QueueDestory(&q);

	return 0;
}

三、栈和队列面试题

💦 括号匹配问题 <难度系数⭐>

📝 题述：给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1️⃣ 左括号必须用相同类型的右括号闭合。

2️⃣ 左括号必须以正确的顺序闭合。

💨 示例1：输入：s = “()” 输出：true

💨 示例2：输入：s = “()[]{}” 输出：true

💨 示例3：输入：s = “(]” 输出：false

💨 示例4：输入：s = “([)]” 输出：false

💨 示例5：输入：s = “{[]}” 输出：true

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：这里我们自己实现一个栈(具体看下图)

leetcode原题

//结构体
typedef char STDatatype;
typedef struct Stack
{ 
   
	STDatatype* a; //指向动态开辟的空间
	int top; //栈顶
	int capacicy; //容量
}ST;
//函数 
//注意链表和顺序表我们写Print，但是栈不写，因为如果栈可以Print的话，就不符合后进先出了
	//初始化
void StackInit(ST* ps);
	//插入
void StackPush(ST* ps, STDatatype x);
	//判空
bool StackEmpty(ST* ps);
	//删除
void StackPop(ST* ps);
	//长度
int StackSize(ST* ps);
	//栈顶
STDatatype StackTop(ST* ps);
	//销毁
void StackDestory(ST* ps);

bool isValid(char* s){ 
   
    ST st;
    StackInit(&st); 
    //match记录真假
    bool match = true;
    while(*s)
    { 
   
        //如果*s等于左括号其中一个则入栈
        if(*s == '[' || *s == '(' || *s == '{')
        { 
   
            StackPush(&st, *s);
            ++s;
        }
        //否则*s等于右括号，出栈里的数据进行匹配
        else
        { 
   
            //如果字符串里只有右括号时，返回false
            if(StackEmpty(&st))
            { 
   
                match = false;
                break;
            }
            //取栈顶的数据 (ch是已经入栈的数据，*s是还未入栈的数据) 
            char ch = StackTop(&st);
            //出栈 '{[]}'为了取上一个数据
            StackPop(&st); 
            //比较
                //不匹配
            if((*s == ']' && ch != '[') 
            || (*s == '}' && ch != '{')
            || (*s == ')' && ch != '('))
            { 
   
                match = false;
                break;                
            }
                //匹配
            else
            { 
   
                ++s;
            }
        }
    }
    if (match == true)
    { 
   
        //如果字符串只有一个左括号时，StackEmpty会返回false
        match = StackEmpty(&st);
    }
    //统一回收
    StackDestory(&st);
    return match;
}

void StackInit(ST* ps)
{ 
   
	assert(ps);
	//初始化
	ps->a = NULL;
	ps->top = 0;
	ps->capacicy = 0;
}
void StackPush(ST* ps, STDatatype x)
{ 
   
	assert(ps);
	//检查空间，满了就增容
	if (ps->top == ps->capacicy)
	{ 
   
		//第一次开辟空间容量为4，其它次容量为当前容量*2
		int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;
		//第一次开辟空间，a指向空，realloc的效果同malloc
		STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);
		//检查realloc
			//realloc失败
		if (tmp == NULL)
		{ 
   
			printf("realloc fail\n");
			exit(-1);
		}
			//realloc成功
		ps->a = tmp;
		ps->capacicy = newcapacity;
	}
	//插入数据 
	ps->a[ps->top] = x;
	ps->top++;
}
bool StackEmpty(ST* ps)
{ 
   
	assert(ps); 
	//等于0是真，否则为假
	return ps->top == 0;
}
void StackPop(ST* ps)
{ 
   
	assert(ps);
	//删除的话得保证指向的空间不为空
	assert(!StackEmpty(ps));
	//删除
	--ps->top;
}

STDatatype StackTop(ST* ps)
{ 
   
	assert(ps);
	//找栈顶的话得保证指向的空间不为空
	assert(!StackEmpty(ps));
	//此时的top-1就是栈顶数据
	return ps->a[ps->top - 1];
}
void StackDestory(ST* ps)
{ 
   
	assert(ps);
	//a为真代表它指向动态开辟的空间
	if (ps->a)
	{ 
   
		free(ps->a);
	}
	ps->a = NULL;
	ps->top = 0;
	ps->capacicy = 0;
}

int main()
{ 
   
	char arr[] = "{[]}";
	printf("%d\n", isValid(arr));
	return 0;
}

💦 用队列实现栈 <难度系数⭐>

📝 题述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

1️⃣ void push(int x) 将元素 x 压入栈顶。

2️⃣ int pop() 移除并返回栈顶元素。

3️⃣ int top() 返回栈顶元素。

4️⃣ boolean empty() 如果栈是空的，返回 true ；否则，返回 false

⚠ 注意

1️⃣ 你只能使用队列的基本操作——也就是push to back、peek/pop from front、size和is empty这些操作。

2️⃣ 你所使用的语言也许不支持队列。你可以使用list (列表) 或者deque (双端队列) 来模拟一个队列，只要是标准的队列操作即可。

💨 示例：输入： [“MyStack”, “push”, “push”, “top”, “pop”, “empty”] – 调用函数接口简称 [[], [1], [2], [], [], []] – 参数输出： [null, null, null, 2, 2, false] 解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False

🍳 提示

1️⃣ 1 <= x <= 9

2️⃣ 最多调用100 次 push、pop、top 和 empty

3️⃣ 每次调用 pop 和 top 都保证栈不为空

⚜ 进阶你能否实现每种操作的均摊时间复杂度为 O(1) 的栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：队列的数据是不能从队尾出的，只能从队头出，而这里要实现的是队列实现栈，所以只能遵循栈的特性——后进先出。这里就需要另外一个队列，具体步骤如下：

1、一个队列有数据，一个队列没数据

2、入数据时向不为空的那个入

3、出数据时，就将不为空的队列的前 size-1 个拷贝至另一个队列，然后再Pop掉剩下的一个数据

leetcode原题

//声明
    //结构体
typedef int QDataType;
typedef struct QueueNode
{ 
   
	struct QueueNode* next; //指向下一个节点
	QDataType data; //存储整型数据
}QueueNode;

typedef struct Queue
{ 
   
	QueueNode* phead;//头指针
	QueueNode* ptail;//尾指针
}Queue;

    //函数
void QueueInit(Queue* pq); 
void QueuePush(Queue* pq, QDataType x);	
bool QueueEmpty(Queue* pq);
void QueuePop(Queue* pq);
QDataType QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueDestory(Queue* pq);
//函数实现
void QueueInit(Queue* pq)
{ 
   
	assert(pq);
	//把2个指针置空
	pq->phead = pq->ptail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{ 
   
	assert(pq);
	//malloc空间,如果需要频繁的开辟空间建议再实现一个BuyQueueNode用于malloc
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{ 
   
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//第一次插入
	if (pq->phead == NULL)
	{ 
   
		pq->phead = pq->ptail = newnode;
	}
	//非第一次插入
	else
	{ 
   
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
}
bool QueueEmpty(Queue* pq)
{ 
   
	assert(pq);
	//空链表返回true，非空链表返回false
	return pq->phead == NULL;
}
void QueuePop(Queue* pq)
{ 
   
	assert(pq);
	//链表为空时不能删除
	assert(!QueueEmpty(pq));
	//只有一个节点的情况
	if (pq->phead->next == NULL)
	{ 
   
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多个节点的情况
	else
	{ 
   
		QueueNode* next = pq->phead->next;
		free(pq->phead)	;
		pq->phead = next;
	}
}
QDataType QueueSize(Queue* pq)
{ 
   
	assert(pq);
	//如果需要频繁的调用QueueSize这个接口，可以在Queue这个结构体中增加一个成员用于记录长度
	int sz = 0;
	QueueNode* cur = pq->phead;
	while (cur)
	{ 
   
		sz++;
		cur = cur->next;
	}
	return sz;
}
QDataType QueueFront(Queue* pq)
{ 
   
	assert(pq);
	//链表为空时不能取头
	assert(!QueueEmpty(pq));
	
	return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{ 
   
	assert(pq);
	//链表为空时不能取尾
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}
void QueueDestory(Queue* pq)
{ 
   
	assert(pq);
	
	QueueNode* cur = pq->phead;
	//遍历链表
	while (cur)
	{ 
   
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
}

typedef struct { 
   
    Queue q1;
    Queue q2;
} MyStack;

/** Initialize your data structure here. */

MyStack* myStackCreate() { 
   
    //malloc空间
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    //Init两个队列
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) { 
   
    assert(obj);
    //QueueEmpty为空时返回true，不为空时返回false
        //往不为空的那个队列里插入数据(q1不为空往q1插入，q2不为空往q2插入)
    if(!QueueEmpty(&obj->q1))
    { 
   
        QueuePush(&obj->q1, x);
    }
    else
    { 
   
        QueuePush(&obj->q2, x);
    }
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) { 
   
    assert(obj);
    //先默认q1为空，q2不为空
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    //q1不为空，重新赋值
    if(!QueueEmpty(&obj->q1))
    { 
   
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    //拷贝 - 将非空队列的size-1个数据拷贝
    while(QueueSize(nonemptyQ) > 1)
    { 
   
        //将非空的队列拷贝至空的队列
        QueuePush(emptyQ, QueueFront(nonemptyQ));
        //删除迭代
        QueuePop(nonemptyQ);
    }
    //top记录非空队列的剩下一个值
    int top = QueueFront(nonemptyQ);
    //删除非空队列的剩下一个数据，这个数据就是栈顶的数据
    QueuePop(nonemptyQ);
    //返回
    return top;
}

/** Get the top element. */
int myStackTop(MyStack* obj) { 
   
    assert(obj);
    //q1不为空，取q1的数据
    if(!QueueEmpty(&obj->q1))
    { 
   
        return QueueBack(&obj->q1);
    }
    //q2不为空，取q2的数据
    else
    { 
   
        return QueueBack(&obj->q2);
    }
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) { 
   
    assert(obj);
    //q1和q2一定有一个为空
    //q1为空返回真，q2为空返回真，mystackEmpty为空返回真;
    //q1为空返回真，q2为非空返回假，myStackEmpty为非空，返回假
    //q1为非空返回假，q2为空返回真，myStackEmpty为非空，返回假
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) { 
   
    assert(obj);
    //结合上面的代码分析我们需要回收两个队列和myStackcreate里malloc的空间
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);

    free(obj);
}

/** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj); */

💦 用栈实现队列 <难度系数⭐>

📝 题述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

1️⃣ void push(int x) 将元素 x 推到队列的末尾。

2️⃣ int pop() 从队列的开头移除并返回元素。

3️⃣ int top() 返回队列开头的元素。

4️⃣ boolean empty() 如果队列是空的，返回 true ；否则，返回 false

⚠ 注意 1️⃣ 你只能使用标准的栈操作 —— 也就是只有push to top，peek/pop from top，和 is empty 操作是合法的。

2️⃣ 你所使用的语言也许不支持栈。你可以使用 list 或者 deque (双端队列) 来模拟一个栈，只要是标准的栈操作即可。

⚜ 进阶

你能否实现每个操作均摊时间复杂度为0(1)的队列?换句话说，执行 n 个操作的总时间复杂度为o(n)，即使其中一个操作可能花费较长时间。

💨 示例：输入： [“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”] – 调用函数接口简称 [[], [1], [2], [], [], []] – 参数输出： [null, null, null, 1, 1, false] 解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false

🍳 提示

1️⃣ 1 <= x <= 9

2️⃣ 最多调用100 次 push、pop、top 和 empty

3️⃣ 假设所有操作都是有效的 (例如，一个空的队列不会调用 pop 或者 peek 操作)

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

1、入数据，进 pushst

2、出数据，看 popst 是否为空，如果为空，就先把 pushst 的数据倒过来，然后出数据；如果不为空，则直接出 popst 的数据

leetcode原题

//一、声明
    //结构体
typedef int STDatatype;
typedef struct Stack
{ 
   
	STDatatype* a; //指向动态开辟的空间
	int top; //栈顶
	int capacicy; //容量
}ST;

    //函数 
	    //初始化
void StackInit(ST* ps);
	    //插入
void StackPush(ST* ps, STDatatype x);
	    //判空
bool StackEmpty(ST* ps);
	    //删除
void StackPop(ST* ps);
	    //长度
int StackSize(ST* ps);
	//栈顶
STDatatype StackTop(ST* ps);
	    //销毁
void StackDestory(ST* ps);

//二、实现
void StackInit(ST* ps)
{ 
   
	assert(ps);
	//初始化
	ps->a = NULL;
	ps->top = 0;
	ps->capacicy = 0;
}
void StackPush(ST* ps, STDatatype x)
{ 
   
	assert(ps);
	//检查空间，满了就增容
	if (ps->top == ps->capacicy)
	{ 
   
		//第一次开辟空间容量为4，其它次容量为当前容量*2
		int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;
		//第一次开辟空间，a指向空，realloc的效果同malloc
		STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);
		//检查realloc
			//realloc失败
		if (tmp == NULL)
		{ 
   
			printf("realloc fail\n");
			exit(-1);
		}
			//realloc成功
		ps->a = tmp;
		ps->capacicy = newcapacity;
	}
	//插入数据 
	ps->a[ps->top] = x;
	ps->top++;
}
bool StackEmpty(ST* ps)
{ 
   
	assert(ps); 
	//等于0是真，否则为假
	return ps->top == 0;
}
void StackPop(ST* ps)
{ 
   
	assert(ps);
	//删除的话得保证指向的空间不为空
	assert(!StackEmpty(ps));
	//删除
	--ps->top;
}
int StackSize(ST* ps)
{ 
   
	assert(ps);
	//此时的top就是长度
	return ps->top;
}
STDatatype StackTop(ST* ps)
{ 
   
	assert(ps);
	//找栈顶的话得保证指向的空间不为空
	assert(!StackEmpty(ps));
	//此时的top-1就是栈顶数据
	return ps->a[ps->top - 1];
}
void StackDestory(ST* ps)
{ 
   
	assert(ps);
	//a为真代表它指向动态开辟的空间
	if (ps->a)
	{ 
   
		free(ps->a);
	}
	ps->a = NULL;
	ps->top = 0;
	ps->capacicy = 0;
}

typedef struct { 
   
    ST pushST;
    ST popST;
} MyQueue;

/** Initialize your data structure here. */
//malloc空间
MyQueue* myQueueCreate() { 
   
    //malloc一块MyQueue类型大小的空间
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    //初始化
    StackInit(&q->pushST);
    StackInit(&q->popST);
    //返回MyQueue这块空间的地址 
    return q;
}
/** Push element x to the back of queue. */
//插入
void myQueuePush(MyQueue* obj, int x) { 
   
    assert(obj);
    //往pushST这个结构体里插入
    StackPush(&obj->pushST, x);
}
/** Get the front element. */
//取队头
int myQueuePeek(MyQueue* obj) { 
   
    assert(obj);
    //如果popST为空，则倒pushST的数据，再取队头
    if(StackEmpty(&obj->popST))
    { 
   
        //popST内有数据，返回false，再非
        while(!StackEmpty(&obj->pushST))
        { 
   
            //把pushST栈顶的数据插入至popST
            StackPush(&obj->popST, StackTop(&obj->pushST));
            //迭代
            StackPop(&obj->pushST); 
        }
    }
    //如果popST不为空，直接取队头
    return StackTop(&obj->popST);
}
/** Removes the element from in front of queue and returns that element. */
//删除
int myQueuePop(MyQueue* obj) { 
   
    assert(obj);
    //如果popST为空，则倒pushST的数据，再出数据
    if(StackEmpty(&obj->popST))
    { 
   
        //popST内有数据，返回false，再非
        while(!StackEmpty(&obj->pushST))
        { 
   
            //把pushST栈顶的数据插入至popST
            StackPush(&obj->popST, StackTop(&obj->pushST));
            //迭代
            StackPop(&obj->pushST); 
        }
    }
        //备份popST内栈顶的数据，用于返回
    int front = StackTop(&obj->popST);
    //如果popST不为空，直接出数据
    StackPop(&obj->popST);
    //返回popST栈顶的数据
    return front;
}
/** Returns whether the queue is empty. */
//判空
bool myQueueEmpty(MyQueue* obj) { 
   
    assert(obj);
    //pushST和popST同时为空，才为空
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
//回收
void myQueueFree(MyQueue* obj) { 
   
    assert(obj);
    //上面的代码中，我们先malloc了一块MyQueue类型的空间，在插入的操作接口中又malloc了pushST和popST
    StackDestory(&obj->pushST);
    StackDestory(&obj->popST);
    free(obj);
}

/** * Your MyQueue struct will be instantiated and called as such: * MyQueue* obj = myQueueCreate(); * myQueuePush(obj, x); * int param_2 = myQueuePop(obj); * int param_3 = myQueuePeek(obj); * bool param_4 = myQueueEmpty(obj); * myQueueFree(obj); */

💦 设计循环队列 <难度系数⭐⭐>

📝 题述：设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作： 1️⃣ MyCircularQueue(k): 构造器，设置队列长度为 k 。

2️⃣ Front: 从队首获取元素。如果队列为空，返回 -1 。

3️⃣ Rear: 获取队尾元素。如果队列为空，返回 -1 。

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

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

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

7️⃣ 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

🍳 提示

1️⃣ 所有的值都在 0 至 1000 的范围内；

2️⃣ 操作数将在 1 至 1000 的范围内；

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

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

问题一，使用数组还是链表 ❔❓

这里使用数组和链表都可以，但是使用数组的缓存利用率更高，且用链表(单链表)实现某些接口时会很恶心

问题二，数组和链表怎么构成环形 ❔❓

1、需要两个指针，head指向下标0，tail指向下标3，tail只要超过数组长度，就回到head的位置

2、让链表的最后一个节点不再指向空，而是指向第一个节点

问题三，怎么判断满与不满，空与非空， head 和 tail 一开始都是指向起始位置，说明为空；当最后一块空间插入数据后，tail 回到起始位置，说明为满。这就形成了矛盾) ❔❓

无论是数组还是链表都额外给一块空间。  (注意这里只是形象的说法) 如果 tail == head 则为空；如果 tail + 1 == head 则为满

leetcode原题

typedef struct { 
   
    int* a;//指向开辟的空间
    int front;//首
    int rear;//尾
    int k; //记录当前有效数据个数
} MyCircularQueue;

//开辟空间
MyCircularQueue* myCircularQueueCreate(int k) { 
   
    //先malloc一块MyCircularQueue类型的空间
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //再malloc指定的k个int类型的空间(注意这里需要额外一块空间)
    q->a = (int*)malloc(sizeof(int) * (k + 1));
    //初始化
    q->front = 0;
    q->rear = 0;
    q->k = k;
    //返回结构体的地址
    return q;
}
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) { 
   
    assert(obj);
    //当front等于rear时，队列为空
    return obj->front == obj->rear;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) { 
   
    assert(obj);
    //当front等于rear+1时则为满(但要防止rear+1越界)
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
//插入数据 - 不能插入返回false，能插入返回true
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { 
   
    assert(obj);
    //myCircularQueueIsFull判断队列是否为满
        //满了，返回真
    if(myCircularQueueIsFull(obj))
        return false;
        //不满，插入数据
    obj->a[obj->rear] = value;
    obj->rear++;    
        //当数组的最后一块空间插入数据时，rear++会越界
    if(obj->rear == obj->k+1)
        obj->rear = 0;
        //至此，返回真
    return true;
}
//删除数据 - 不能删除返回false，能删除返回true
bool myCircularQueueDeQueue(MyCircularQueue* obj) { 
   
    assert(obj);
    //myCircularQueueIsEmpty判断队列是否为空
        //空了，返回真，
    if(myCircularQueueIsEmpty(obj))
        return false;   
        //不空，删除数据，(这里只需要让front往后走即可)
    obj->front++;
        //当数组的最后一块空间删除数据时，front++会越界
    if(obj->front == obj->k+1)
        obj->front = 0;
        //至此，返回真
    return true;
}
//获取队头的数据 
int myCircularQueueFront(MyCircularQueue* obj) { 
   
    assert(obj);
    //如果队列为空返回-1
    if(myCircularQueueIsEmpty(obj))
        return -1;
    //返回队头
    return obj->a[obj->front];
}
//获取队尾的数据 
int myCircularQueueRear(MyCircularQueue* obj) { 
   
    assert(obj);
    //如果队列为空返回-1
    if(myCircularQueueIsEmpty(obj))
        return -1;
    //获取队尾(这里myCircularQueueEnQueue插入数据后tail++，所以队尾是tail)
    //prevRear记录前一个
    int prevRear = obj->rear - 1;
    //当rear是下标为0的那块空间时，prevRear就是k
    if(obj->rear == 0)
        prevRear = obj->k;
    //返回队尾
    return obj->a[prevRear];
}
//回收空间
void myCircularQueueFree(MyCircularQueue* obj) { 
   
    assert(obj);
    //在上面的代码中我们malloc了两次的空间，先回收结构体内成员的空间，再回收结构体
    free(obj->a);
    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); */

四、概念选择题

💦 1

1、一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是 ( )

A. 12345ABCDE

B. EDCBA54321

C. ABCDE12345

D. 54321EDCBA

📝 解析：B，根据栈的特点 —— 后进先出，先进后出，可以得到正确答案

💦 2

2、若进栈的序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是 ( )

A. 1，4，3，2

B. 2，3，4，1

C. 3，1，4，2

D. 3，4，2，1

📝 解析：C，本题需要注意的是进栈过程中可以出栈，这也导致了多种情况的出现：

进栈顺序：1 2 3 4

出栈顺序：1 2 3 4 4 3 2 1 … …

💦 3

3、循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后， front=rear=99 ，则循环队列中的元素个数为（）

A. 1

B. 2

C. 99

D. 0

📝 解析：D，当循环队列进行一系列操作后，front == rear 说明为空；front == rear+1 说明为满

💦 4

4、以下( )不是队列的基本运算？

A. 从队尾插入一个新元素

B. 从队列中删除第i个元素

C. 判断一个队列是否为空

D. 读取队头元素的值

📝 解析：B，从队列的特性先进先出，后进后出即可知道答案

💦 5

5、现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N，实际最多存储 N – 1 个数据。其队内有效长度为？（）

A. (rear – front + N) % N + 1

B. (rear – front + N) % N

C. (ear – front) % (N + 1)

D. (rear – front + N) % (N – 1)

📝 解析：B，这里分为两种情况：

1️⃣ 队列的有效长度是 (rear – front + N) % N == 3

对于第 1 种情况来说只需要 rear – front 即可，为什么还需要 +N 再 % N ❓❔ 因为这里还有第 2 种情况，而仅仅是 rear – front 这个公式是不能满足第 2 种情况的

2️⃣ 队列的有效长度是 (rear – front + N) % N == 4

对于第 2 种情况来说只需要 rear + N – front 即可，为什么还需要 +N 再 % N ❓❔ 因为本题是只有 1 个正确答案，所以还要顾虑到第 1 种情况，需要寻找能同时适用于两种情况的 1 个公式

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/137271.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年6月2，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法