写在前面：很久没更新博客了，没有其他原因，主要是懒（狗头保命），言归正传，由于我使用的是纯c语言，库中没有队列和栈所以要在做题前首先要创建队列或栈，因此首先在正文开始前附上队列和栈的代码实现，后续题目代码将不再贴有关栈和队列的实现代码。
栈的实现：
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack { //类似于顺序表，数组，top，容量 STDataType* a; int top; int capacity; }ST; //接口函数：判断是否为空，插入，删除，顶部，size void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps, STDataType x); void StackPop(ST* Ps); STDataType top(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST* ps); void StackInit(ST* ps) { //初始化,top和容量都置空 ps->a = NULL; ps->capacity = ps->top = 0; } void StackDestory(ST* ps) { assert(ps); //销毁链表释放a的空间 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 newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, newcapcity * sizeof(STDataType)); if (tmp == NULL)//检查realloc是否成功 { perror("realloc fail\n"); } //扩容成功 ps->a = tmp; ps->capacity = newcapcity; } //开始插入数据 ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } STDataType top(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top-1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; }
队列的实现：
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QNDataType; typedef struct QueueNode { //使用单链表 struct QueueNode* next; QNDataType data; }QNode; //链表的缺陷就在于尾插太麻烦，不如直接定义一个尾节点 typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; //队尾入，队头出,与单链表的实现唯一的区别在于这个有两个结构体，什么时候用什么样的结构体定义变量要分清楚 void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QNDataType x); void QueuePop(Queue* pq); QNDataType QueueFront(Queue* pq); QNDataType QueueBack(Queue* pq); bool QueueEmpty(Queue* pq); int QueueSize(Queue* pq); void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); //要释放每一个节点 QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); del = NULL; } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QNDataType x) { assert(pq); //要开辟一个节点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode==NULL) { perror("malloc fail\n"); exit(-1); } else { newnode->data = x; newnode->next = NULL; } //对空链表和非空链表进行分类讨论 if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //非空队列删除，队头出，分一个元素和多个元素的区别 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* del = pq->head; pq->head = pq->head->next; free(del); del = NULL; } pq->size--; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL&&pq->head==NULL; } QNDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QNDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } int QueueSize(Queue* pq) { assert(pq); return pq->size; }
本文目录
一.用队列实现栈
二.用栈实现队列
三.循环队列
##一.用队列实现栈
题目链接
题目描述
仅用两个队列实现一个先入后出的栈，并支持栈的四种基本操作.
解题思路
队列是先进先出而栈要后进先出，题目给了两个队列，将所有元素插入到其中一个队列，另外一个为空队列，每次要删除元素时，把要删除元素前的所有元素push到非空队列中即可。
代码实现
typedef struct {//定义两个队列 Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { //队列的初始化，要malloc MyStack*obj=(MyStack*)malloc(sizeof(MyStack)); QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } 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*nonempty=&obj->q2; if(!QueueEmpty(&obj->q1)) { //q1不为空则说明假设错误，交换位置 empty=&obj->q2; nonempty=&obj->q1; } //把nonempty中n-1个数据插到empty中 while(QueueSize(nonempty)>1) { QueuePush(empty,QueueFront(nonempty)); //要让nonempty的front后移 QueuePop(nonempty); } //题目要求该函数要返回栈顶元素 int top=QueueFront(nonempty); QueuePop(nonempty); return top; } int myStackTop(MyStack* obj) { //判断非空，返回非空队列的back 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) { //分开free QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); //obj=NULL; }
