孜孜不倦：孜孜：勤勉，不懈怠。指工作或学习勤奋不知疲倦。💓💓💓

目录

 说在前面

题目一：括号匹配问题

题目二：用队列实现栈

题目三：用栈实现队列

题目四：设计循环队列

SUMUP结尾

---

 说在前面

 dear朋友们大家好！💖💖💖我们又见面了，有到了我们数据结构的刷题时间了。我们上次刚学完了栈和队列，现在正好练练手~

 👇👇👇

友友们！🎉🎉🎉点击这里进入力扣leetcode学习🎉🎉🎉

​以下是leetcode题库界面：

​​

 👇👇👇

🎉🎉🎉点击这里进入牛客网NowCoder刷题学习🎉🎉🎉
​以下是NowCoder题库界面：

​

  ​​​

题目一：括号匹配问题

题目链接：20. 有效的括号 - 力扣（LeetCode）

题目描述：

​

题目分析：

 思路：由于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 + 1;
}

//栈的销毁
void STDestroy(ST* pst)
{
	assert(pst);
	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结尾

数据结构就像数学题，需要刷题才能对它有感觉。之后还会更新数据结构相关的练习题、面试题，希望大家一起学习，共同进步~

如果大家觉得有帮助，麻烦大家点点赞，如果有错误的地方也欢迎大家指出~