网站制作怎么办,wordpress网站网速慢,中文静态网站下载,推广公众号平台的公司栈和队列小提升#xff01; 前言一、用队列实现栈队列接口实现#xff08;1#xff09;栈的接口定义#xff08;2#xff09;栈的初始化#xff08;3#xff09;入栈函数的定义#xff08;4#xff09;出栈函数的定义#xff08;5#xff09;查找栈顶元素#xff0… 栈和队列小提升 前言一、用队列实现栈队列接口实现1栈的接口定义2栈的初始化3入栈函数的定义4出栈函数的定义5查找栈顶元素6判空函数的定义7销毁函数的定义 二、用栈实现队列栈的接口实现1队列的接口定义2队列的初始化3入队函数的定义4出队函数的定义5查找队头函数的定义6判空函数的定义7销毁函数的定义 三、设计循环队列1循环队列的接口定义2循环队列的初始化3判空函数的定义4判满函数的定义5循环队列插入函数的定义6循环队列删除函数的定义7查找队头函数的定义8查找队尾函数的定义9销毁函数的定义 总结 前言
欢迎来到专项提升小课堂 今天的题目稍稍有难度哦 但是只要用心是难不倒同学们的 一、用队列实现栈
题目链接OJ链接 提示 1 x 9 最多调用100 次 push、pop、top 和 empty 每次调用 pop 和 top 都保证栈不为空 核心思想 用队列模拟出栈的先入后出这一特性
解题思路 此题可以用两个队列去实现一个栈每次始终保持一个队列为空 入栈操作相当于给非空队列进行入队操作 出栈操作相当于非空队列的队尾元素出队此时需要把非空队列除最后一个元素之外的其余元素入队到空队列然后出队最后一个队尾元素
图例解析 代码示例
队列接口实现 先将队列的实现接口导入 这里涉及到之前队列建立的内容啦 如果不了解的可以去看看栈和队列
//头文件的声明
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//链表接口定义
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//队列接口定义
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;//队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);
//插入
void QueuePush(Que* pq, QDataType x);
//删除
void QueuePop(Que* pq);
//查找队头元素
QDataType QueueFront(Que* pq);
//查找队尾元素
QDataType QueueBack(Que* pq);
//判断是否为空
bool QueueEmpty(Que* pq);
//计算长度
int QueueSize(Que* pq);void QueueInit(Que* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}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(Que* pq)
{assert(pq);//判断队列指针指向是否为空assert(!QueueEmpty(pq));//判断队列里面的数据是否为空if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}//查找队头元素
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}//查找队尾元素
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}//判断是否为空
bool QueueEmpty(Que* pq)
{assert(pq);return pq-head NULL;
}//长度计算
int QueueSize(Que* pq)
{assert(pq);return pq-size;
}队列实现栈的功能函数的定义 1栈的接口定义
typedef struct {Que q1;Que q2;
} MyStack;2栈的初始化
MyStack* myStackCreate() {MyStack*pst (MyStack*)malloc(sizeof(MyStack));QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}3入栈函数的定义
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}4出栈函数的定义
int myStackPop(MyStack* obj) {Que*Emptyobj-q1;Que*nonEmptyobj-q2;if(!QueueEmpty(obj-q1)){Emptyobj-q2;nonEmptyobj-q1;}while(QueueSize(nonEmpty)1){QueuePush(Empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int top QueueFront(nonEmpty);QueuePop(nonEmpty);return top;
}5查找栈顶元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}6判空函数的定义
bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1)QueueEmpty(obj-q2);
}7销毁函数的定义
void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}二、用栈实现队列
题目链接OJ链接 提示 1 x 9 最多调用 100 次 push、pop、peek 和 empty 假设所有操作都是有效的例如一个空的队列不会调用 pop 或者 peek 操作 核心思想 用栈模拟出队列的先入先出这一特性
解题思路 此题可以用两个栈实现一个栈进行入队操作另一个栈进行出队操作 出队操作 当出队的栈不为空是直接进行出栈操作如果为空需要把入队的栈元素全部导入到出队的栈然后再进行出栈操作
图例解析 代码示例
栈的接口实现 先将栈的实现接口导入 这里涉及到之前栈的建立的内容啦 如果不了解的可以去看看栈和队列
//栈的接口定义
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//查找栈顶元素
STDataType STTop(ST* ps);
//长度计算
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);//初始化
void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}//插入
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}//删除栈顶元素
void STPop(ST* ps)
{assert(ps);assert(ps-top 0);--ps-top;
}//查找栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}//长度计算
int STSize(ST* ps)
{assert(ps);return ps-top;
}//判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}栈实现队列的功能函数的定义 1队列的接口定义
typedef struct {ST pushst;ST popst;
} MyQueue;2队列的初始化
MyQueue* myQueueCreate() {MyQueue*obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;
}3入队函数的定义
void myQueuePush(MyQueue* obj, int x) {STPush(obj-pushst,x);
}4出队函数的定义
int myQueuePop(MyQueue* obj) {int front myQueuePeek(obj);STPop(obj-popst);return front;
}5查找队头函数的定义
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);
}6判空函数的定义
bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-popst)STEmpty(obj-pushst);
}7销毁函数的定义
void myQueueFree(MyQueue* obj) {STDestroy(obj-popst);STDestroy(obj-pushst);free(obj);
}三、设计循环队列
题目链接OJ链接 提示 所有的值都在 0 至 1000 的范围内 操作数将在 1 至 1000 的范围内 请不要使用内置的队列库。 核心思想 首尾相连循环即为环形
解题思路 通过一个定长数组实现循环队列 入队首先要判断队列是否已满再进行入队的操作入队操作需要考虑索引循环的问题当索引越界需要让它变成最小值 出队首先要判断队列是否为空再进行出队操作出队也需要考虑索引循环的问题 判空 队头 队尾 判满 队尾 1 队头
图例解析 代码示例
1循环队列的接口定义
typedef struct {int *a;int front;int rear;int k;
} MyCircularQueue;2循环队列的初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a(int*)malloc(sizeof(int)*(k1));obj-frontobj-rear0;obj-kk;return obj;
}3判空函数的定义
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-frontobj-rear;
}4判满函数的定义
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-rear1)%(obj-k1)obj-front;
}5循环队列插入函数的定义
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj-a[obj-rear]value;obj-rear;obj-rear%(obj-k1);return true;
}6循环队列删除函数的定义
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj-front;obj-front%(obj-k1);return true;
}7查找队头函数的定义
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-a[obj-front];
}8查找队尾函数的定义
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-a[(obj-rearobj-k)%(obj-k1)];
}9销毁函数的定义
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}总结
今天的题目难度真的不小哦 但也要相信自己 自信就是最好解决问题的方法
