1、括号匹配问题
链接直达：
题目：
思路：
做题前，得先明确解题方案是啥，此题用栈的思想去解决是较为方便的，栈明确指出后进先出。我们可以这样设定：
- 遇到左括号“ ( ”、“ [ ”、“ { ”，入栈。
- 遇到右括号“ ) ”、“ ] ”、“ } ”，出栈，跟左括号进行匹配，不匹配就报错。
上两句话的意思就是说我去遍历字符串，如果遇到左括号，就入栈；遇到右括号，就出栈顶元素，并判断这个右括号是否与栈顶括号相匹配，若不匹配则返回false，匹配继续遍历字符串，直到遍历完全，遍历后，检查栈是否为空，若为空，则均匹配，返回true，反之false。
代码如下：
//创建栈结构
typedef char STDataType;
typedef struct Stack
{
STDataType* a; //存储数据
int top; //栈顶的位置
int capacity; //容量
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//访问栈顶数据
STDataType StackTop(ST* ps);
//有效元素个数
int StackSize(ST* ps);
//定义：
//初始化栈
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
//销毁栈
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
//压栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//如果栈满了，考虑扩容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //检测容量
ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//将数据压进去
ps->top++;//栈顶上移
}
//出栈
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0; //如果top为0，那么就为真，即返回
}
//访问栈顶数据
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}
//有效元素个数
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
//创建好了栈开始实现
bool isValid(char* s) {
ST st;//先创建一个栈
StackInit(&st);//初始化栈
while (*s)
{
if (*s == '[' || *s == '(' || *s == '{')
{
StackPush(&st, *s); //如果是左括号就入栈
++s;
}
else
{
if (StackEmpty(&st))
{
return false; //此处说明前面根本没有左括号，导致栈为空，直接返回false
}
char top = StackTop(&st); //获取栈顶元素
StackPop(&st); //出栈顶元素，接下来进行匹配
if ((*s == ']' && top != '[')
|| (*s == ')' && top != '(')
|| (*s == '}' && top != '{'))
{
StackDestory(&st); //返回前先销毁，防止内存泄漏
return false; //如果不匹配，直接返回false
}
else
{
//此时匹配，继续比较，直到遍历结束
++s;
}
}
}
//栈为空，说明所有左括号都匹配
bool ret = StackEmpty(&st);
StackDestory(&st); //返回前先销毁，防止内存泄漏
return ret;
}
2、用队列实现栈
链接直达：
题目：
思路：
做题之前，再明确下两个基本知识点
- 栈：后进先出
- 队列：先进先出
此题要用先进先出的队列来实现后进先出的栈，并模拟实现队列的基本接口。
假设我们有一串数字，进入队列A顺序为1 2 3 4，此时再有一个队列B，此时我们取队列A的队头数据，并将其导入队列B，当队列A出到只剩最后一个时，把队列A给pop删掉，此时队列B就是1 2 3，间接性是实现了栈的功能，实现了后进先出的功能。当我们需要再入数据时，只需往不为空的队列入即可。再出就像刚刚那样。简而言之两句话：
- 入栈：push数据到不为空的队列。
- 出栈：把不为空的队列的数据前N-1导入另一个空队列，最后剩下一个删掉。
本质：保持一个队列存储数据，另外一个队列空着，要出栈时，空队列用来导数据。
代码如下：
//创建队列结构
typedef int QDataType; //方便后续更改存储数据类型，本文以int为例
//创建队列节点
typedef struct QueueNode
{
QDataType data; //存储数据
struct QueueNode* next; //记录下一个节点
}QNode;
//保存队头和队尾
typedef struct Queue
{
QNode* head; //头指针
QNode* tail; //尾指针
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//获取有效元素个数
size_t QueueSize(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);
//定义：
//初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
//销毁队列
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
//入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//创建一个新节点保存数据
QNode* newnode = (QNode*)malloc(sizeof(QNode));
//暴力检测newnode，因为malloc的都要检测
assert(newnode);
newnode->next = NULL;
newnode->data = x;
//如果一开始没有数据，为空的情况
if (pq->tail == NULL)
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail); //tail和head均不能为空
//特殊：当删到head=tail的位置时
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
//一般情况
else
{
//保存head的下一个节点
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
//获取有效元素个数
size_t QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->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;
}
/**************创建好队列结构，开始正文模拟实现栈**************/
typedef struct {
Queue q1; //队列q1
Queue q2; //队列q2
} MyStack;
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); //申请一个MyStack类型的栈
assert(pst);
QueueInit(&pst->q1);//初始化队列1
QueueInit(&pst->q2);//初始化队列2
return pst;
}
void myStackPush(MyStack* obj, int x) {
assert(obj);
if (!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);//如果q1不为空，就往q1插入数据
}
else
{
QueuePush(&obj->q2, x);//这儿不需要知道q2是否为空，直接push
}
}
int myStackPop(MyStack* obj) {
assert(obj);
Queue* emptyQ = &obj->q1; //默认q1为空
Queue* nonEmtpyQ = &obj->q2;//默认q2不为空
if (!QueueEmpty(&obj->q1))
{
emptyQ = &obj->q2; //若假设错误，则q2为空
nonEmtpyQ = &obj->q1;//此时q1就为空
}
while (QueueSize(nonEmtpyQ) > 1)
{
QueuePush(emptyQ, QueueFront(nonEmtpyQ)); //把非空的队列数据导到空的队列，直到只剩一个
QueuePop(nonEmtpyQ); //此时把非空的队头数据给删掉，方便后续导入数据
}
int top = QueueFront(nonEmtpyQ); //记录此时的栈顶数据
QueuePop(nonEmtpyQ); //删除栈顶数据，使该队列置空
return top;
}
int myStackTop(MyStack* obj) {
assert(obj);
if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);//如果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); //释放q1
QueueDestory(&obj->q2); //释放q2
free(obj);
}
3、用栈实现队列
链接直达：
题目：
思路：
假设入栈的顺序为1 2 3 4，那么根据题意，想要达到1 2 3 4的出栈顺序以此实现队列。
此题和上一道题正好相反，用栈实现队列，上一道题中，我们需要把数据来回导，从而实现栈的后进先出功能，但是此题就完全不需要来回导了，只需要导一次即可。
假设我们有两个栈，分别命名为pushST和popST。并往栈pushST里头入4个数据1 2 3 4，在出数据时根据栈的性质只能拿到4，此时我们直接把4拿下来并导入栈popST里头，并继续把pushST栈里的数据导下来，直至栈pushST数据为空。此时popST数据即为 4 3 2 1，刚好反过来了。
根据队列的先进先出规则，进1 2 3 4，出必然是1 2 3 4，而上文已经知晓栈popST的数据为4 3 2 1，当删除数据时，会按照1 2 3 4 的顺序逐个删除。恰好利用栈的性质实现了队列的先进先出功能。并只需导一次即可，无需多次。
代码如下：
//创建栈结构
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //存储数据
int top; //栈顶的位置
int capacity; //容量
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//访问栈顶数据
STDataType StackTop(ST* ps);
//有效元素个数
int StackSize(ST* ps);
//初始化栈
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
//销毁栈
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
//压栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//如果栈满了，考虑扩容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity; //检测容量
ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//将数据压进去
ps->top++;//栈顶上移
}
//出栈
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0; //如果top为0，那么就为真，即返回
}
//访问栈顶数据
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}
//有效元素个数
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
/************创建好栈结构，开始正文************/
typedef struct {
ST pushST; //插入数据的栈
ST popST; //删除数据的栈
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); //申请队列类型
assert(obj);
StackInit(&obj->pushST);//初始化pushST
StackInit(&obj->popST);//初始化popST
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
assert(obj);
StackPush(&obj->pushST, x);//不管有没有数据，都插入
}
int myQueuePop(MyQueue* obj) {
assert(obj);
if (StackEmpty(&obj->popST)) //如果popST数据为空，要从pushST里导入数据才能删除
{
while (!StackEmpty(&obj->pushST)) //pushST数据不为空，就一直向popST里导入数据
{
StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST栈顶数据导到popST里
StackPop(&obj->pushST);//导完后把pushST栈顶元素删掉，方便后续继续导
}
}
int front = StackTop(&obj->popST); //记录popST栈顶元素
StackPop(&obj->popST);//删除popST栈顶元素，实现队列先进先出
return front; //返回栈顶数据
}
//取队头数据
int myQueuePeek(MyQueue* obj) {
assert(obj);
//如果popST数据为空，要从pushST里导入数据才能取到队头数据
if (StackEmpty(&obj->popST))
{
while (!StackEmpty(&obj->pushST)) //pushST数据不为空，就一直向popST里导入数据
{
StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST栈顶数据导到popST里
StackPop(&obj->pushST);//导完后把pushST栈顶元素删掉，方便后续继续导
}
}
return StackTop(&obj->popST);//直接返回栈顶元素
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj) {
assert(obj);
StackDestory(&obj->pushST);
StackDestory(&obj->popST);
free(obj);
}
4、设计循环队列
链接直达：
题目：
思路：
此题可以用数组实现，也可以用链表实现，但其实是用数组更加方便些。
数组：
假设队头front和队尾tail都指向第一个数据，在队尾插入数据，tail随着数据的插入跟着移动，tail始终为最后一个数据的下一个位置。删除数据只需要将队头front往后挪即可，不需要按照之前队列的pop一样删完还挪动数据，因为是循环链表，且数据是可以重复利用的。
这样分析下来再加上画图看似没有什么缺陷，但是存在两个问题？
- 什么情况下数组为空？
- 什么情况下数组满了？
问题1：
当tail = front时数组为空，看似没什么问题，但相等又要分两种情况。先画个图：
由上图得知，在情况一下，数组里确实是一个数据也没有，并且tail也是等于front的，满足数组为空的条件，但是在情况二下，数组的数据全满，此时的tail和front同样是相等的，这里数组不为空了，而是全满，由此可见，是存在问题的。
解决方案：
这里我们可以多开一个空间，不存放数据，只是用来分别数组为空或满。原理如下：当数组长度为4时，也就是说实际能存放3个有效数据，另外一个空间用来判断空或满，此时判断空或满的条件如下：
- front == tail 时是空
- tail 下一个位置是 front 时，就是满
代码如下：
typedef struct {
int* a; //用数组模拟环形队列
int front;//队头
int tail; //队尾
int k; //表示存的数据长度为k
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj); //前置声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//前置声明
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//创建环形链表结构
assert(obj);
obj->a = (int*)malloc(sizeof(int) * (k + 1));//多开一个空间，便于后续区分空或满
obj->front = obj->tail = 0;
obj->k = k; //队列存储有效数据长度为k
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))
{
return false; //队列已满，不能插入数据
}
obj->a[obj->tail] = value; //赋值
if (obj->tail == obj->k)
{
obj->tail = 0; //当tail走到尾端
}
else
{
obj->tail++;
}
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return false; //队列为空，不能删除
}
if (obj->front == obj->k)
{
obj->front = 0; //当front走到尾端
}
else
{
obj->front++;
}
return true;
}
//取头
int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return -1; //队列为空，取不了
}
return obj->a[obj->front]; //返回队头
}
//取尾
int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return -1; //队列为空，取不了
}
if (obj->tail == 0)
{
return obj->a[obj->k]; //tail为0，队尾在长度的最后一个位置
}
else
{
return obj->a[obj->tail - 1];
}
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->tail; //front==tail时为空
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if (obj->tail == obj->k && obj->front == 0)
{
return true; //当tail尾端，front在头端时也是满
}
else
{
return obj->tail + 1 == obj->front; //一般情况，当tail的下一个位置为front时为满
}
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
