一、用队列实现栈
题目链接：力扣
对于这道题，我们想要使用两个队列去实现栈
队列的性质是先进先出，而栈的性质是先进后出
为了实现性质转换，我们需要有一个队列时刻保持空状态，当我们想要入栈的时候，我们在不是空的队列进行插入即可
而想要实现出栈，假设又n+1个数据，先将前n个数据给倒入另一个空队列，最后出最后一个数据即可
有了思路，但是这道题最难的地方就是栈的结构了。也就是创建栈的函数，根据题目的要求，我们是需要创建一个栈并且返回这个栈的指针的。所以这个创建栈的函数就类似于带头双向循环链表的创建。如下图所示，是我们这个栈的结构
所以我们很容易就写出来了第一个函数
MyStack* myStackCreate() { MyStack* st=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&(st->q1)); QueueInit(&(st->q2)); return st; }
我们将栈的结构给构建出来以后，这个题目就变得十分简单了。事实上，栈和队列的本身实现并不难，难的是结构的构造
最终代码为
typedef int QDateType; typedef struct QNode { QDateType data; struct QNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; //初始化队列 void QueueInit(Queue* q); //队尾入队列 void QueuePush(Queue* q, QDateType x); //队头出队列 void QueuePop(Queue* q); //获取队列头部元素 QDateType QueueFront(Queue* q); //获取队列尾部元素 QDateType QueueBack(Queue* q); //获取队列中的有效元素个数 int QueueSize(Queue* q); //检测队列是否为空 bool QueueEmpty(Queue* q); //销毁队列 void QueueDestroy(Queue* q); //初始化队列 void QueueInit(Queue* q) { assert(q); q->head = NULL; q->tail = NULL; q->size = 0; } //申请一个结点 QNode* BuyQNode(QDateType x) { QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->next = NULL; newnode->data = x; return newnode; } //队尾入队列 void QueuePush(Queue* q, QDateType x) { assert(q); QNode* newnode = BuyQNode(x); if (q->tail == NULL) { q->head = q->tail = newnode; } else { q->tail->next = newnode; q->tail = q->tail->next; } q->size++; } //队头出队列 void QueuePop(Queue* q) { assert(q); assert(q->head); QNode* first = q->head->next; free(q->head); q->head = first; q->size--; if (q->head == NULL) { q->tail = NULL; } } //获取队列头部元素 QDateType QueueFront(Queue* q) { assert(q); assert(q->head); return q->head->data; } //获取队列尾部元素 QDateType QueueBack(Queue* q) { assert(q); assert(q->head); return q->tail->data; } //获取队列中的有效元素个数 int QueueSize(Queue* q) { assert(q); return q->size; } //检测队列是否为空 bool QueueEmpty(Queue* q) { assert(q); return q->head == NULL; } //销毁队列 void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } q->head = q->tail = NULL; q->size = 0; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* st=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&(st->q1)); QueueInit(&(st->q2)); return st; } bool myStackEmpty(MyStack* obj) { assert(obj); return QueueEmpty(&(obj->q1))&&QueueEmpty(&(obj->q2)); } void myStackPush(MyStack* obj, int x) { assert(obj); Queue* emptyq=&(obj->q1); Queue* noemptyq=&(obj->q2); if(!QueueEmpty(emptyq)) { noemptyq=&(obj->q1); emptyq=&(obj->q2); } QueuePush(noemptyq,x); } int myStackPop(MyStack* obj) { assert(obj); assert(!myStackEmpty(obj)); Queue* emptyq=&(obj->q1); Queue* noemptyq=&(obj->q2); if(!QueueEmpty(emptyq)) { noemptyq=&(obj->q1); emptyq=&(obj->q2); } while(QueueSize(noemptyq)>1) { QDateType x=QueueFront(noemptyq); QueuePop(noemptyq); QueuePush(emptyq,x); } QDateType x=QueueFront(noemptyq); QueuePop(noemptyq); return x; } int myStackTop(MyStack* obj) { assert(obj); assert(!myStackEmpty(obj)); Queue* emptyq=&(obj->q1); Queue* noemptyq=&(obj->q2); if(!QueueEmpty(emptyq)) { noemptyq=&(obj->q1); emptyq=&(obj->q2); } while(QueueSize(noemptyq)>1) { QDateType x=QueueFront(noemptyq); QueuePop(noemptyq); QueuePush(emptyq,x); } QDateType x=QueueFront(noemptyq); QueuePush(emptyq,x); QueuePop(noemptyq); //QDateType x=QueueBack(noemptyq); return x; } void myStackFree(MyStack* obj) { QueueDestroy(&(obj->q1)); QueueDestroy(&(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); */
二、用栈实现队列
题目链接：力扣
对于这道题，与上面的题目十分类似，我们使用两各栈去模拟一个队列。那么我们可以这样做，一个栈专门用来入数据，一个栈专门用来出数据，当出数据的栈为空的时候，将入数据的栈的数据全部导入出数据的栈中。这样我们就可以模拟出一个队列
同样的，这个题的难点，仍然是结构。
如上所示，是我们的结构示意图
typedef struct { Stack push; Stack pop; } MyQueue;
一旦我们将结构给理清楚了，那么这道题就易如反掌了
typedef int STDateType; typedef struct Stack { STDateType* a; int top; int capacity; }Stack; //栈的初始化 void StackInit(Stack* ps); //栈的销毁 void StackDestroy(Stack* ps); //入栈 void StackPush(Stack* ps, STDateType x); //出栈 void StackPop(Stack* ps); //栈的个数 int StackSize(Stack* ps); //栈是否为空 bool StackEmpty(Stack* ps); //取出栈顶的数据 STDateType StackTop(Stack* ps); //栈的初始化 void StackInit(Stack* ps) { assert(ps); ps->a = (STDateType*)malloc(sizeof(STDateType) * 4); if (ps->a == NULL) { perror("malloc fail"); return; } ps->top = 0; ps->capacity = 4; } //栈的销毁 void StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; } //入栈 void StackPush(Stack* ps, STDateType x) { assert(ps); if (ps->top == ps->capacity) { STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType)); if (tmp == NULL) { perror("realloc fail"); return; } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; ps->top++; } //出栈 void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } //栈的个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } //栈是否为空 bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; } //取出栈顶的数据 STDateType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } typedef struct { Stack push; Stack pop; } MyQueue; MyQueue* myQueueCreate() { MyQueue* q=(MyQueue*)malloc(sizeof(MyQueue)); if(q==NULL) { perror("malloc fail"); return NULL; } StackInit(&(q->push)); StackInit(&(q->pop)); return q; } bool myQueueEmpty(MyQueue* obj) { assert(obj); return StackEmpty(&(obj->push))&&StackEmpty(&(obj->pop)); } void myQueuePush(MyQueue* obj, int x) { assert(obj); StackPush(&(obj->push),x); } int myQueuePop(MyQueue* obj) { assert(obj); assert(!myQueueEmpty(obj)); if(StackEmpty(&(obj->pop))) { while(!StackEmpty(&(obj->push))) { STDateType x=StackTop(&(obj->push)); StackPop(&(obj->push)); StackPush(&(obj->pop),x); } } STDateType x=StackTop(&(obj->pop)); StackPop(&(obj->pop)); return x; } int myQueuePeek(MyQueue* obj) { assert(obj); assert(!myQueueEmpty(obj)); if(StackEmpty(&(obj->pop))) { while(!StackEmpty(&(obj->push))) { STDateType x=StackTop(&(obj->push)); StackPop(&(obj->push)); StackPush(&(obj->pop),x); } } STDateType x=StackTop(&(obj->pop)); return x; } void myQueueFree(MyQueue* obj) { assert(obj); StackDestroy(&(obj->push)); StackDestroy(&(obj->pop)); free(obj); obj=NULL; } /** * 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); */
三、设计循环队列
题目链接：力扣
对于这道题，设计循环队列，我们最容易想到的方法就是使用链表。不难想到，对于单链表只需要将头尾给链接起来，似乎就能变成循环队列了
我们假设k为4，
我们一开始让front和rear都指向第一个元素，当需要入队列的时候，rear指向下一个元素
当想要出队列的时候，让front往后走一步即可
我们继续入队列，当数据入满的时候，如下图所示，我们发现一个问题，队列满和队列空都始front和rear相等，无法辨别。
为了解决这个问题，我们有两种解决方案：
1.使用一个变量size来记住队列有几个元素
2.多开辟一个结点，这样当队列满的时候，rear->next==front这就是判断队列满的标志了，得以区分
这样了以后，其实还是有一点问题的，如果我们需要取出尾数据的话，十分难受，我们必须得去遍历链表。
当然我们可以多定义一个指针有进行处理，但是这样代码可读性变差了
由上述分析得知，循环队列并不适合使用链表来实现，反而适合数组。
想要使用数组来实现，那么我们得先分析基本的思路
如果使用数组来模拟的话，首先我们假设k为4，为了区分满与空，我们需要开辟5个空间
当我们入队的时候，rear++
当我们出队的时候，front++
当数据一直插入直到满的时候，数组为下面的情景
此时rear+1==front，代表队列已满
有了上述的分析，那么这道题就很简单了，代码如下所示：
typedef struct { int* a; int front; int rear; int k; } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj) { assert(obj); return obj->front==obj->rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { assert(obj); return obj->front==(obj->rear+1)%(obj->k+1); } MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); q->a=(int*)malloc(sizeof(int)*(k+1)); q->front=0; q->rear=0; q->k=k; return q; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { assert(obj); if(myCircularQueueIsFull(obj)) { return false; } obj->a[obj->rear]=value; obj->rear++; obj->rear %= obj->k+1; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { assert(obj); if(myCircularQueueIsEmpty(obj)) { return false; } obj->front++; obj->front %= obj->k+1; return true; } int myCircularQueueFront(MyCircularQueue* obj) { assert(obj); if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { assert(obj); if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)]; } void myCircularQueueFree(MyCircularQueue* obj) { assert(obj); free(obj->a); obj->a=NULL; obj->front=0; obj->rear=0; obj->k=0; free(obj); obj=NULL; } /** * 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); */
本期内容到此为止
如果对你有帮助的话，不要忘记点赞加收藏哦！！！
