保山网站建设多少钱,wordpress 简历,网站公司排行榜,食品贸易网站建设案例文章目录 一、循环队列1、题目简述2、方法讲解2.1、了解tail的指向2.2、了解空间是如何利用的2.3、如何判断队列是否为空#xff08;假溢出问题#xff09;#xff1f;2.4、实现代码 二、用栈实现队列1、题目简述2、方法讲解2.1、讲解2.2、实现代码 三、用队列实现栈1、题目… 文章目录 一、循环队列1、题目简述2、方法讲解2.1、了解tail的指向2.2、了解空间是如何利用的2.3、如何判断队列是否为空假溢出问题2.4、实现代码 二、用栈实现队列1、题目简述2、方法讲解2.1、讲解2.2、实现代码 三、用队列实现栈1、题目简述2、方法讲解2.1、讲解2.2、实现代码 四、谢谢观看 一、循环队列
1、题目简述
与队列的区别循环队列的空间大小是固定的且队尾连接队头形成循环。 要实现的方法
2、方法讲解
我们开始就说过循环队列的数据储存的数量是固定的为了方便讲解我们这里设队列可储存4个数据。即 k4。
2.1、了解tail的指向
我们将队列的数据存放在数组中head为队头下标tail为队尾的下一个元素的下标。 tail为队尾的下一个元素的下标 原因 若指向队尾数据 当对列为空时head、tail均指向首即headtail0 而当队列有一个元素时tail指向队尾则仍有headtail0 产生歧义无法区分队列是否有元素。 故tail必须指向队尾元素的下一个元素 2.2、了解空间是如何利用的
注队列遵循先进先出的规则 下面来举例了解数据的循环入队列 1、入三个数据1,23
2、出两次数据 3、入三个数据456 在有限空间内保证先进先出空间重复使用。 那么问题来了如何判断队列是否为空
2.3、如何判断队列是否为空假溢出问题
假溢出空、满时判断条件相同。 此时无法区分空、满。 为了解决假溢出问题我们有两种方法 方法一通过size来计录数据 空size 0 满size k (k:队列可储存数据个数) 方法二多开一个空间 k 4 (最多push入4个数据) push入4个数据 1234 空一个空间出来则满的时候 head不可能等于tail假溢出问题就解决了。 已经入了4个数据了想要再入数据就要先出数据把空间空出来。
pop 出三次 push 入 5,67 由上可得 空 head tail 满 tail1% k1 head 2.4、实现代码
1、初始化 2、获取队首元素 3、取尾 在取尾返回时也可写为
//数组
typedef struct {int* a;//数组下标int head;int tail;//指向尾的下一个int k;
} MyCircularQueue;//初始化
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//开k1个数组空间obj-a (int*)malloc(sizeof(int) * (k 1));obj-head obj-tail 0;obj-k k;return obj;
}
//判空
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;elsereturn obj-a[obj-head];
}
//取尾
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;elsereturn obj-tail0? obj-a[obj-k] : obj-a[obj-tail-1];
}//释放
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}
二、用栈实现队列
1、题目简述 注意C语言不支持栈我们需要先模拟栈。 模拟栈在这里就不赘述了以下是C语言模拟的栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;//指针指向数组int top;int capacity;//数组大小
}ST;//初始化与销毁
void STInit(ST* pst)
{assert(pst);//指针不为空pst-a NULL;//若初始化top0之后当要入栈的数据入完top指向的是栈顶元素的下一个位置因为top进行了//若初始化top-1之后当要入栈的数据入完top指向的是栈顶元素pst-top 0;pst-capacity 0;
}
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}//入栈、出栈
void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, newcapacity*sizeof(STDataType));//扩容是否成功if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}//入栈给数组栈放入值之后toppst-a[pst-top] x;//数组a中的元素为xpst-top;//若初始化top0之后当要入栈的数据入完top指向的是栈顶元素的下一个位置因为top进行了//若初始化top-1之后当要入栈的数据入完top指向的是栈顶元素}
void STPop(ST* pst)//出栈删除数据
{assert(pst);assert(pst-top 0);//栈不为空pst-top--;
}//取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);return pst-a[pst-top - 1];//若初始化top0之后当要入栈的数据入完top指向的是栈顶元素的下一个位置因为top进行了//所以栈顶元素是pst-top-1
}//判空
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;//top为0即为空返回1//不为空返回0
}//获取数据个数
int STSize(ST* pst)
{assert(pst);return pst-top;
}2、方法讲解 栈从栈顶入、从栈顶出。满足先进后出。 一种入栈顺序可有多种边进边出出栈顺序队列从队尾入、从队头出。满足先进先出。 一种入队顺序只有一种出队顺序。使用两个栈一个只入数据一个只出数据。要用栈来实现队列的顺序特点。
2.1、讲解 1、入数据1,23,4 2、出数据 如果popst内的数据为空就将pushst内的数据导入popst中此时从popst中按栈的顺序出数据时所出顺序即为队列的出数据顺序。 入的数据与出的数据的顺序相同符合队列先进先出的逻辑。
2.2、实现代码
typedef int STDataType;
typedef struct Stack
{STDataType* a;//指针指向数组int top;int capacity;//数组大小
}ST;//初始化与销毁
void STInit(ST* pst)
{assert(pst);//指针不为空pst-a NULL;//若初始化top0之后当要入栈的数据入完top指向的是栈顶元素的下一个位置因为top进行了//若初始化top-1之后当要入栈的数据入完top指向的是栈顶元素pst-top 0;pst-capacity 0;
}
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}//入栈、出栈
void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, newcapacity*sizeof(STDataType));//扩容是否成功if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}//入栈给数组栈放入值之后toppst-a[pst-top] x;//数组a中的元素为xpst-top;//若初始化top0之后当要入栈的数据入完top指向的是栈顶元素的下一个位置因为top进行了//若初始化top-1之后当要入栈的数据入完top指向的是栈顶元素}
void STPop(ST* pst)//出栈删除数据
{assert(pst);assert(pst-top 0);//栈不为空pst-top--;
}//取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);return pst-a[pst-top - 1];//若初始化top0之后当要入栈的数据入完top指向的是栈顶元素的下一个位置因为top进行了//所以栈顶元素是pst-top-1
}//判空
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;//top为0即为空返回1//不为空返回0
}//获取数据个数
int STSize(ST* pst)
{assert(pst);return pst-top;
}
//两个栈实现队列
typedef struct {ST pushst; //入数据ST popst; //出数据
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;
}
//入队
void myQueuePush(MyQueue* obj, int x) {STPush(obj-pushst,x);
}
//出队
int myQueuePop(MyQueue* obj) {int front myQueuePeek(obj); //队头STPop(obj-popst);return front;
}
//找队头
int myQueuePeek(MyQueue* obj) {//如果popst为空就倒数据倒完的popst的顺序为先进先出if(STEmpty(obj-popst)){//倒数据while(!STEmpty(obj-pushst)){int top STTop(obj-pushst);STPush(obj-popst,top);STPop(obj-pushst);}}return STTop(obj-popst);
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-popst) STEmpty(obj-pushst);
}void myQueueFree(MyQueue* obj) {STDestroy(obj-popst);STDestroy(obj-pushst);free(obj);
}
三、用队列实现栈
1、题目简述 C语言模拟的队列
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue//可避免使用二级指针和传多个参数
{int size;//size为每个节点的编号每增加一个sizeQNode* phead;QNode* ptail;
}Queue;
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq-size 0;pq-phead NULL;pq-ptail NULL;
}//销毁
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;
}//队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc error);return;}newnode-next NULL;newnode-val x;if (pq-phead NULL)//原队列无节点{pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}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 QueueFront(Queue* pq)
{assert(pq);//assert(pq-phead);return pq-phead-val;
}//找尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
//统计个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}2、方法讲解 2.1、讲解
1、入栈 1,23,4 判断哪一个队列为空入到为空的队列中 2、删除栈顶数据 将不为空的队列中的队尾数据之前的所有数据导入为空的队列中而原队列中只剩下要删除的元素。
//删除栈顶元素
int myStackPop(MyStack* obj) {//将该队列队尾之前的元素size-1push到空的队列中//原队列中只剩下要删除的元素Queue* empty obj-q1;Queue* nonEmpty obj-q2;if (!QueueEmpty(obj-q1)){empty obj-q2;nonEmpty obj-q1;}while (QueueSize(nonEmpty) 1){QueuePush(empty, QueueFront(nonEmpty));QueuePop(nonEmpty);}int top QueueFront(nonEmpty);QueuePop(nonEmpty);return top;
}2.2、实现代码
//两个队列实现栈后进先出
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue//可避免使用二级指针和传多个参数
{int size;//size为每个节点的编号每增加一个sizeQNode* phead;QNode* ptail;
}Queue;
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq-size 0;pq-phead NULL;pq-ptail NULL;
}//销毁
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;
}//队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc error);return;}newnode-next NULL;newnode-val x;if (pq-phead NULL)//原队列无节点{pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}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 QueueFront(Queue* pq)
{assert(pq);//assert(pq-phead);return pq-phead-val;
}//找尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
//统计个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}typedef struct {//匿名结构体Queue q1;Queue q2; //两个队列
} MyStack;//初始化
MyStack* myStackCreate() {MyStack* obj (MyStack*)malloc(sizeof(MyStack));//malloc开辟的空间在出函数后不会销毁QueueInit(obj-q1);QueueInit(obj-q2);//优先级-高于return obj;
}
//入栈
void myStackPush(MyStack* obj, int x) {//push到不为空的队列中if (!QueueEmpty(obj-q1)){QueuePush(obj-q1, x);}else{QueuePush(obj-q2, x);}}
//删除栈顶元素
int myStackPop(MyStack* obj) {//将该队列队尾之前的元素size-1push到空的队列中//原队列中只剩下要删除的元素Queue* empty obj-q1;Queue* nonEmpty obj-q2;if (!QueueEmpty(obj-q1)){empty obj-q2;nonEmpty obj-q1;}while (QueueSize(nonEmpty) 1){QueuePush(empty, QueueFront(nonEmpty));QueuePop(nonEmpty);}int top QueueFront(nonEmpty);QueuePop(nonEmpty);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);
}四、谢谢观看
