有不懂的地方一定要看看我往期文章哦！
个人主页：小八哥向前冲~_博客
所属专栏：数据结构【c语言】
注意：这些题目实现全部由c语言实现，解决这些问题需要用到栈和队列，如果对c语言实现栈和队列有问题的同学，可以看：队列的实现 和 栈的实现 俩篇文章哦！
目录
配括号问题
题目：
思路：
我们将 '(' '[' '{'统称为左括号，将 ']' ')' '}'统称为右括号。
经过观察，这个配括号问题就是一个简单的配对问题。
我们遍历数组，将左括号全部入栈，然后一一出栈和数组中右括号进行配对。
实现代码的时候需要注意几点：
- 如果数组里面没有左括号，只有右括号，则永远配不成功。
- 如果出栈配对时，栈里最终还有左括号，也就是说右括号比左括号多，也配不成功。
代码：
typedef char STDateType;
//栈
typedef struct stack
{
STDateType* a;
int top;
int capacity;
}ST;
//栈的初始化和销毁
void STInit(ST* p);
void STDestroy(ST* p);
//入栈，出栈
void STpush(ST* p,STDateType x);
void STpop(ST* p);
//栈顶的数据
STDateType STtop(ST* p);
//栈的数据个数
int STsize(ST* p);
//判空
bool STEmpty(ST* p);
//栈的初始化和销毁
void STInit(ST* p)
{
assert(p);
p->a = NULL;
p->capacity = 0;
p->top = 0;
}
void STDestroy(ST* p)
{
assert(p);
free(p->a);
p->capacity = p->top = 0;
}
//入栈，出栈
void STpush(ST* p, STDateType x)
{
assert(p);
if (p->top == p->capacity)
{
int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
STDateType* tmp = (STDateType*)realloc(p->a, newcapacity * sizeof(STDateType));
if (tmp == NULL)
{
perror("realloc failed!");
return;
}
p->a = tmp;
p->capacity = newcapacity;
}
p->a[p->top++] = x;
}
void STpop(ST* p)
{
assert(p);
//出栈的话要判断一下空的情况
assert(!STEmpty(p));
p->top--;
}
//栈顶的数据
STDateType STtop(ST* p)
{
assert(p);
//出栈的话要判断一下空的情况
assert(!STEmpty(p));
return p->a[p->top-1];
}
//栈的数据个数
int STsize(ST* p)
{
assert(p);
return p->top;
}
//判空
bool STEmpty(ST* p)
{
assert(p);
return p->top == 0;
}
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(top=='('&&*s!=')'
||top=='['&&*s!=']'
||top=='{'&&*s!='}')
{
STDestroy(&st);
return false;
}
}
s++;
}
//如果出栈配对后，栈里还有左括号，那么也永远配不成功
bool ret=STEmpty(&st);
STDestroy(&st);
return ret;
}循环队列问题
题目：
思路：两种方法
方法一：
将这个循环队列看成循环数组。
由于队列的先进先出原则，我们可以定义三个变量：头变量，尾变量，数据个数变量。
我们简单推理知道：我们动态开辟k个数据，进队列，从尾插入数据，入队列，从头删除数据，出队列。
可是又有一个新的问题：如何判断这个循环数组里面是空还是满呢？
上图：
由此可知，我们判断不了满的情况和空的情况。
我们可以这样来解决：
- 定义一个size变量，记录数组数据个数。
- 多开辟一个数据空间。
我们主要介绍第二种解决方案。
那么如何判断空和满呢？
另外需要注意的是：
在入队列（tail++）时，tail可能会越界，也要取模运算，出队列（head++）时，head也可能越界，也要取模运算。
思路到了这里，还要最后一个问题：怎么访问尾队列数据和头队列数据呢?
我们访问头队列数据很容易，直接访问头变量就行，可是尾呢？
上图：
代码：
typedef struct {
int*a;
int head;
int tail;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue*p=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//多开一个空间，解决判满判空冲突问题
p->a=(int*)malloc(sizeof(int)*(k+1));
p->head=p->tail=0;
p->k=k;
return p;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->head==obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%(obj->k+1)==obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[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->a[obj->head];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
return obj->a[(obj->tail+obj->k)%(obj->k+1)];
//return obj->a[obj->tail==0?k:obj->tail-1];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
方法二
思路：
我们可以将这个循环队列看成循环链表。
定义三个指针变量：尾指针，头指针，尾指针的前一个指针。
进队列，从尾进，尾指针指向下一个，出队列，从头出，头指针指向下一个。
有了上一部分基础，我们判空判满依旧可以多开辟一个空间。
为什么要定义尾指针的前一个指针，只定义头指针和尾指针不行吗？
当我们访问尾队列数据时，可以直接用尾指针的前一个指针直接访问就行，省了一个循环找尾队列数据的遍历！
代码：
typedef struct Node
{
struct Node*next;
int val;
}Node;
typedef struct {
Node*phead;
Node*ptail;
Node*preptail;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->phead=obj->ptail=NULL;
for(int i=0;i<k+1;i++)
{
Node*cur=(Node*)malloc(sizeof(Node));
cur->next=NULL;
if(obj->phead==NULL)
{
obj->phead=obj->ptail=cur;
}
else
{
obj->ptail->next=cur;
obj->ptail=cur;
}
}
obj->ptail->next=obj->phead;
obj->preptail=obj->ptail;
obj->ptail=obj->phead;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->phead==obj->ptail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return obj->ptail->next==obj->phead;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->ptail->val=value;
obj->ptail=obj->ptail->next;
obj->preptail=obj->preptail->next;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->phead=obj->phead->next;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->phead->val;
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->preptail->val;
}
void myCircularQueueFree(MyCircularQueue* obj) {
while(obj->phead!=obj->ptail)
{
Node*next=obj->phead->next;
free(obj->phead);
obj->phead=next;
}
free(obj);
}用栈实现队列
题目：
思路：
我们可以将一个栈专门用来入数据的，另一个专门用来出数据的。
当出数据的栈为空时，还想出数据，将入数据的栈的数据全部导入出数据的栈，再继续出数据即可！
代码：
typedef int STDateType;
//栈
typedef struct stack
{
STDateType* a;
int top;
int capacity;
}ST;
//栈的初始化和销毁
void STInit(ST* p);
void STDestroy(ST* p);
//入栈，出栈
void STpush(ST* p,STDateType x);
void STpop(ST* p);
//栈顶的数据
STDateType STtop(ST* p);
//栈的数据个数
int STsize(ST* p);
//判空
bool STEmpty(ST* p);
//栈的初始化和销毁
void STInit(ST* p)
{
assert(p);
p->a = NULL;
p->capacity = 0;
p->top = 0;
}
void STDestroy(ST* p)
{
assert(p);
free(p->a);
p->capacity = p->top = 0;
}
//入栈，出栈
void STpush(ST* p, STDateType x)
{
assert(p);
if (p->top == p->capacity)
{
int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
STDateType* tmp = (STDateType*)realloc(p->a, newcapacity * sizeof(STDateType));
if (tmp == NULL)
{
perror("realloc failed!");
return;
}
p->a = tmp;
p->capacity = newcapacity;
}
p->a[p->top++] = x;
}
void STpop(ST* p)
{
assert(p);
//出栈的话要判断一下空的情况
assert(!STEmpty(p));
p->top--;
}
//栈顶的数据
STDateType STtop(ST* p)
{
assert(p);
//出栈的话要判断一下空的情况
assert(!STEmpty(p));
return p->a[p->top-1];
}
//栈的数据个数
int STsize(ST* p)
{
assert(p);
return p->top;
}
//判空
bool STEmpty(ST* p)
{
assert(p);
return p->top == 0;
}
typedef struct {
ST pushst;
ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue*p=(MyQueue*)malloc(sizeof(MyQueue));
STInit(&(p->pushst));
STInit(&(p->popst));
return p;
}
void myQueuePush(MyQueue* obj, int x) {
STpush(&(obj->pushst),x);
}
int myQueuePop(MyQueue* obj) {
int top=myQueuePeek(obj);
STpop(&(obj->popst));
return top;
}
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&(obj->popst)))
{
while(!STEmpty(&(obj->pushst)))
{
STpush(&(obj->popst),STtop(&(obj->pushst)));
STpop(&(obj->pushst));
}
}
return STtop(&(obj->popst));
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&(obj->pushst))&&STEmpty(&(obj->popst));
}
void myQueueFree(MyQueue* obj) {
STDestroy(&(obj->pushst));
STDestroy(&(obj->popst));
free(obj);
}用队列实现栈
题目：
思路：
我们可以将判断俩队列哪个为空队列，哪个不为空队列。
进栈时，入数据在不为空的队列里，出栈时，出数据时，需要将不为空队列的数据导入为空队列中去，然后再去出栈！
而判断哪个为空队列，我们可以用假设法！
代码：
typedef int QDataType;
//原则：先进先出
//队列
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
//管理队列的一些参数
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;//队列中数据的个数
}Queue;
//参数初始化
void QueueInit(Queue* pq);
//入队 队尾入队
void Queuepush(Queue* pq, QDataType x);
//出队 队头出队
void Queuepop(Queue* pq);
//数据个数
int Queuesize(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//队尾数据
QDataType QueueBack(Queue* pq);
//队头数据
QDataType QueueFront(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);
//参数初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//入队 队尾入队
void Queuepush(Queue* pq, QDataType x)
{
QNode* node = (QNode*)malloc(sizeof(QNode));
if (node == NULL)
{
perror("malloc failed!");
return;
}
node->next = NULL;
node->val = x;
//入队
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = node;
}
else
{
pq->ptail->next = node;
pq->ptail = node;
}
//插入数据，数据个数增加
pq->size++;
}
//出队 队头出队
void Queuepop(Queue* pq)
{
assert(pq);
//队列不能为空
assert(pq->size > 0);
//当只有一个节点时，出队后，尾指针变成野指针！
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--;
}
//队尾数据
QDataType QueueBack(Queue* pq)
{
assert(pq->size > 0);
return pq->ptail->val;
}
//队头数据
QDataType QueueFront(Queue* pq)
{
assert(pq->size != 0);
return pq->phead->val;
}
//数据个数
int Queuesize(Queue* pq)
{
assert(pq);
return pq->size;
}
//队列判空
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;
cur = NULL;
}
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack*p=(MyStack*)malloc(sizeof(MyStack));
QueueInit(&(p->q1));
QueueInit(&(p->q2));
return p;
}
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&(obj->q1)))
{
Queuepush(&(obj->q1),x);
}
else
{
Queuepush(&(obj->q2),x);
}
}
int myStackPop(MyStack* obj) {
Queue*empty=&(obj->q1);
Queue*noempty=&(obj->q2);
if(!QueueEmpty(&(obj->q1)))
{
noempty=&(obj->q1);
empty=&(obj->q2);
}
while(Queuesize(noempty)>1)
{
Queuepush(empty,QueueFront(noempty));
Queuepop(noempty);
}
int front=QueueFront(noempty);
Queuepop(noempty);
return front;
}
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);
}
这些题目你都掌握了吗？只要对链表和顺序表很熟悉，解决这种题目还是很轻松的！
我们下期见！