LeetCode/NowCoder-栈和队列OJ练习
孜孜不倦：孜孜：勤勉，不懈怠。指工作或学习勤奋不知疲倦。💓💓💓
目录
说在前面
dear朋友们大家好！💖💖💖我们又见面了，有到了我们数据结构的刷题时间了。我们上次刚学完了栈和队列，现在正好练练手~
👇👇👇
以下是leetcode题库界面：
👇👇👇
🎉🎉🎉点击这里进入牛客网NowCoder刷题学习🎉🎉🎉
以下是NowCoder题库界面：
题目一：括号匹配问题
题目描述：
题目分析：
思路：由于C语言没有单独提供栈的实现，我们首先需要把我们之前写的栈的实现的接口都复制到题当中，接口如下：
typedef char STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
//栈的初始化
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
//top指的是栈顶数据的下一个位置
pst->top = pst->capacity = 0;
}
//扩容
static void STCheckCapacity(ST* pst)
{
if (pst->top == pst->capacity)
{
int NewCapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
STDataType* temp = (STDataType*)realloc(pst->a, NewCapacity * sizeof(STDataType));
if (temp == NULL)
{
perror("realloc operation failed");
exit(1);
}
pst->a = temp;
pst->capacity = NewCapacity;
}
}
//入栈
void STPush(ST* pst, STDataType x)
{
assert(pst);
STCheckCapacity(pst);
pst->a[pst->top++] = x;
}
//出栈
void STPop(ST* pst)
{
assert(pst && pst->top);
pst->top--;
}
//获取栈顶元素
STDataType STTop(ST* pst)
{
assert(pst && pst->top);
return pst->a[pst->top - 1];
}
//检测栈是否为空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
//获取栈中有效元素个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
//栈的销毁
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}在此基础上我们才能完成题解。
这题为什么会想到用栈来解决呢？我们可以认为每次得到一个右括号，都和从右边往左的第一个左括号进行匹配，如果匹配成功，就是对的，如果有哪一次匹配失败了，说明不正确，返回false。那么我们观察左括号很明显就有个特点，就是最后输入的左括号要先和右括号匹配，这和我们栈的LIFO（Last In First Out）是一样的。
比如：
像上面这个例子，我们可以用栈存放左括号。如果是三种左括号的一种，我们就把它压入栈中，如果是三种右开括号的一种，我们取出栈顶的左括号，和它进行匹配。
当放入这三个左括号，我们输入了一个右括号，此时我们需要得到栈顶的括号（STTop）和当前右有括号对比看是否匹配。如果匹配成功，我们还需要将这个数据删除，然后继续这个操作，也就是每次对比都会消耗一个左括号。
显然两个左括号都匹配成功，此时再继续压栈。最后两个右括号刚好也和两个左括号匹配成功，所以最后我们可以判断栈是否为空（STEmpty）来判断是否整体都是匹配成功的。
代码如下：
bool isValid(char* s) {
ST st;
STInit(&st);
while(*s)
{
//左括号入栈
if(*s == '(' || *s == '[' || *s == '{')
{
STPush(&st, *s);
}
else//右括号去栈顶左括号尝试匹配
{
if(STEmpty(&st))//栈为空
{
STDestroy(&st);
return false;
}
char top = STTop(&st);
STPop(&st);
//匹配失败
if(*s == ')' && top != '('
|| *s == ']' && top != '['
|| *s == '}' && top != '{')
return false;
}
s++;
}
bool ret = STEmpty(&st);
STDestroy(&st);
return ret;
}最后有一个地方需要注意，就是如果我们刚开始就进入右括号，此时没有做括号匹配，那么直接就跳出循环，栈也是为空的，就返回了true，这显然是错误的。所以我们在输入右括号的时候也要判断一下栈是否为空，若为空直接返回false。
题目二：用队列实现栈
题目链接：225. 用队列实现栈 - 力扣（LeetCode）
题目描述：
题目分析：
思路：和题目一同样的，我们需要将队列的实现的所有接口都复制到题目当中，才能在接下来使用队列，接口如下：
typedef int QDataType;
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
struct QueueNode* phead;
struct QueueNode* ptail;
int size;
}Queue;
//队列的初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc operation failed");
exit(1);
}
newnode->next = NULL;
newnode->val = x;
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
//队头出队列
void QueuePop(Queue* pq)
{
assert(pq && pq->size);
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
//获取队列有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
//获取队列头部元素
QDataType QueueFront(Queue* pq)
{
assert(pq && pq->phead);
return pq->phead->val;
}
//获取队列尾部元素
QDataType QueueBack(Queue* pq)
{
assert(pq && pq->ptail);
return pq->ptail->val;
}
//检测队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}
//销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}有了上述接口以后，我们思考接下来如何用两个队列实现栈。
我们知道，栈是后入先出的，而队列是先入先出的。函数需要我们实现栈的基本操作：push（压栈）、pop（弹栈）、top（取栈顶元素）、empty（判空）。对于压栈来说，其实可以直接实现，我们把一个队列的队头当做栈底，队尾入队列（QueuePush）就相当于压栈。问题是如何弹栈呢？队列只能是一端入，另一端出，没办法直接实现删除队尾的数据。这个时候，我们可以借助另一个队列。我们可以将队列中的数据从队头开始都入到另一个队列的中，只留下最后一个队尾的数据，然后再删除这个数据就可以了。
这也是这道题中重要的思想 ，去栈顶元素可以直接用QueueBack实现，而判空就是两个队列都为空即为空，同时要注意压栈应该压入到不为空的队列中，栈顶元素返回的也是不为空的队列中的尾元素，请大家注意。
代码如下：
//创建包含两个队列的匿名结构体
typedef struct {
Queue q1;
Queue q2;
} MyStack;
//初始化这两个队列
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
压栈，即压入不为空的队列中，如果都为空那就都行
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
//弹栈
int myStackPop(MyStack* obj) {
//假设法，假设q1是空的，若不成立那就q2是空的
Queue* empty = &obj->q1;
Queue* noempty = &obj->q2;
if(!QueueEmpty(empty))
{
empty = &obj->q2;
noempty = &obj->q1;
}
//把不空的队列入到空队列中，并留下最后一个
while(QueueSize(noempty) - 1)
{
QueuePush(empty, QueueFront(noempty));
QueuePop(noempty);
}
int top = QueueFront(noempty);
QueuePop(noempty);
return top;
}
//取栈顶元素
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
//判空
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
//销毁栈
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
题目三：用栈实现队列
题目链接：232. 用栈实现队列 - 力扣（LeetCode）
题目描述：
题目分析：
思路1：和队列实现栈是基本类似的，建议大家做了第二题再看这道题。不过这里有个地方不太一样，就是Pop，在队列实现栈中，我们只需要将队列中的数据插入到另外一个队列中，再删除剩下的那一个就行了，但是栈实现队列，将栈中的数据压栈到另外的一个栈，删除栈底的那个数据后，由于顺序反了，我们还需要将另一个栈的数据再放回来才行。
也就是这里会有区别，其他地方其实都和题目二是一样的。
代码如下：
//创建包含两个栈的匿名结构体
typedef struct {
ST st1;
ST st2;
} MyQueue;
//初始化结构体
MyQueue* myQueueCreate() {
MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&pq->st1);
STInit(&pq->st2);
return pq;
}
//队尾入队列
void myQueuePush(MyQueue* obj, int x) {
if(!STEmpty(&obj->st1))
{
STPush(&obj->st1, x);
}
else
{
STPush(&obj->st2, x);
}
}
//队头出队列
int myQueuePop(MyQueue* obj) {
ST* empty = &obj->st1;
ST* noempty = &obj->st2;
if(!STEmpty(empty))
{
empty = &obj->st2;
noempty = &obj->st1;
}
while(STSize(noempty) > 1)
{
STPush(empty, STTop(noempty));
STPop(noempty);
}
int top = STTop(noempty);
STPop(noempty);
while(STSize(empty))
{
STPush(noempty, STTop(empty));
STPop(empty);
}
return top;
}
//获得队头数据
int myQueuePeek(MyQueue* obj) {
ST* empty = &obj->st1;
ST* noempty = &obj->st2;
if(!STEmpty(empty))
{
empty = &obj->st2;
noempty = &obj->st1;
}
while(STSize(noempty) > 1)
{
STPush(empty, STTop(noempty));
STPop(noempty);
}
int top = STTop(noempty);
STPush(empty, STTop(noempty));
STPop(noempty);
while(STSize(empty))
{
STPush(noempty, STTop(empty));
STPop(empty);
}
return top;
}
//判空
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->st1) && STEmpty(&obj->st2);
}
//销毁队列
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->st1);
STDestroy(&obj->st2);
free(obj);思路2：除了思路1，我们其实还有另外一种方法，就是将一个栈的栈顶当做队头，入数据，另外一个栈的栈顶当做队尾，出数据：
那么入队列就相当于将数据压入到左边的栈（pushst）中，出队列就相当于是删除右边的栈（popst）的栈顶数据，如果右边的栈中没有数据了，再把左边的栈的数据全部导入到右边，这样往复就可以了。
代码如下：
//创建包含两个栈的匿名结构体
typedef struct {
ST pushst;
ST popst;
} MyQueue;
//初始化结构体内容
MyQueue* myQueueCreate() {
MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&pst->pushst);
STInit(&pst->popst);
return pst;
}
//队尾入队列
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->pushst, x);//相当于压入pushst中
}
//取得队头数据
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&obj->popst))//如果popst中没有数据，就把pushst中的数据导到popst中
{
while(!STEmpty(&obj->pushst))
{
STPush(&obj->popst, STTop(&obj->pushst));
STPop(&obj->pushst);
}
}
return STTop(&obj->popst);
}
//队头出队列
int myQueuePop(MyQueue* obj) {
int front = myQueuePeek(obj);//有数据，直接获取，没数据，先将pushst导入
STPop(&obj->popst);
return front;
}
//判空
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}
//销毁队列
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->pushst);
STDestroy(&obj->popst);
free(obj);
} 
题目四：设计循环队列
题目链接：622. 设计循环队列 - 力扣（LeetCode）
题目描述：
题目分析：
思路：创建数组，利用模运算使得操作控制在0~k元素范围内，并保证tail不放数据。
我们一般的队列是用链表实现的，但是对于循环队列，数组的方法可能更好实现，链表的方法并不比数组的方法简单多少。
//创建包含数组相关内容的匿名结构体
typedef struct {
int* arr;
int head;
int tail;
int k;
} MyCircularQueue;
//初始化结构体中的各项数据
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* st = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
st->arr = (int*)malloc((k + 1) * sizeof(int));
st->head = 0;
st->tail = 0;
st->k = k;
return st;
}
//如果head和tail位置相同，循环队列为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->head == obj->tail;
}
//如果head在tail的下一个位置，循环队列为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return obj->head == (obj->tail + 1) % (obj->k + 1);
}
//队尾入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
obj->arr[obj->tail] = value;
obj->tail++;
obj->tail %= (obj->k + 1);
return true;
}
//队头出队列
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
obj->head++;
obj->head %= (obj->k + 1);
return true;
}
//取队头数据
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
else
return obj->arr[obj->head];
}
//取队尾数据
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
else
return obj->tail == 0 ? obj->arr[obj->k] : obj->arr[obj->tail - 1];
//return obj->arr[(obj->tail + obj->k) % (obj->k + 1)];
}
//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->arr);
free(obj);
}这道题锻炼并加深了对模运算的理解，对上面每个函数体中的模运算大家一定要理解清楚。那链表的方式为什么复杂呢？原因就是因为，在数组中我们取尾的前一个只要下标-1就可以了，最多再加上模运算，但是对于链表是不好找前一个尾节点的前一个节点的。当然有解决办法，如改用双向链表，或者记录tail的前一个节点prev，也可以重新遍历链表。但是这些解决方法无一不大大增加了代码的复杂度且降低了可读性，所以对于循环链表来说，数组的解决方法是更好的。
SUMUP结尾
数据结构就像数学题，需要刷题才能对它有感觉。之后还会更新数据结构相关的练习题、面试题，希望大家一起学习，共同进步~
如果大家觉得有帮助，麻烦大家点点赞，如果有错误的地方也欢迎大家指出~