南阳卧龙区网站建设哪家好,软件开发经费预算,微信小程序加盟,seo五大经验分享用队列实现栈 思路 栈的特点#xff1a;后进先出 队列的特点#xff1a;先进先出 使用两个队列实现栈#xff1a; 我们可以使用两个队列#xff0c;一个队列为#xff1a;空队列#xff0c;一个队列为#xff1a;非空队列 当我们要出队列时#xff1a;
将 size - …用队列实现栈 思路 栈的特点后进先出 队列的特点先进先出 使用两个队列实现栈 我们可以使用两个队列一个队列为空队列一个队列为非空队列 当我们要出队列时
将 size - 1个数据移动到空队列中再将最后一个数据出队列如此往复就可以完成4 3 2 1的出队列顺序 代码c语言
队列的各种功能
typedef int QDataType;
// 链式结构表示队列
typedef struct QListNode
{struct QListNode* _next;QDataType _data;
}QNode;// 队列的结构
typedef struct Queue
{QNode* _front;QNode* _rear;int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q) {assert(q);q-size 0;q-_front NULL;q-_rear NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data) {assert(q);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(QueuePush()::malloc());return;}newnode-_data data;newnode-_next NULL;//队列为NULLif (q-_front NULL){q-_front q-_rear newnode;}else{q-_rear-_next newnode;q-_rear q-_rear-_next;}q-size;
}
// 队头出队列
void QueuePop(Queue* q) {assert(q);assert(q-size ! 0);//单个节点if (q-_front q-_rear){free(q-_front);q-_front q-_rear NULL;}//多个节点else{QNode* next q-_front-_next;free(q-_front);q-_front next;}q-size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q) {assert(q);assert(q-_front);//队头不能为NULLreturn q-_front-_data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q) {assert(q);assert(q-_rear);//队尾不能为NULLreturn q-_rear-_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q) {return q-size;
}
// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q) {assert(q);return q-size 0;
}
// 销毁队列
void QueueDestroy(Queue* q) {assert(q);QNode* cur q-_front;while (cur){QNode* next cur-_next;free(cur);cur next;}q-_front q-_rear NULL;q-size 0;}
具体实现
//使用两个队列实现栈
typedef struct {Queue q1;Queue q2;} MyStack;//初始化栈
MyStack* myStackCreate() {//创建一个栈MyStack* newStk (MyStack*)malloc(sizeof(MyStack));//初始化栈(即初始化两个队列)QueueInit((newStk-q1));QueueInit((newStk-q2));return newStk;
}//入栈
void myStackPush(MyStack* obj, int x) {//假设法找不为NULL的队列Queue* noempty obj-q1;if(QueueSize(noempty) 0){noempty obj-q2;}//往不为NULL队列中插入QueuePush(noempty,x);
}//出栈
int myStackPop(MyStack* obj) {//假设法判断NULL队列非NULL队列Queue* empty obj-q1;Queue* noempty obj-q2;if(QueueSize(noempty) 0){noempty obj-q1;empty obj-q2;}//将size - 1个数据移动到NULL队列中while(QueueSize(noempty) 1){QueuePush(empty,QueueFront(noempty));QueuePop(noempty);}//出栈int pop QueueBack(noempty);QueuePop(noempty);return pop;}//获取栈顶元素
int myStackTop(MyStack* obj) {Queue* noempty obj-q1;if(QueueSize(noempty) 0){noempty obj-q2;}//获取栈顶数据也就是队尾的数据return QueueBack(noempty);}//判NULL
bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1) QueueEmpty(obj-q2);}//销毁栈
void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);}
用栈实现队列 思路
使用两个栈实现队列 固定两个栈1. 存数据栈pushst 2. 出数据栈popst
当我们要出数据时把存数据栈pushst导入到 出数据栈popst中在对栈顶取数据如此往复就可以实现 4 3 2 1 的出栈顺序 代码c语言
栈的各种功能
typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;// 初始化和销毁
void STInit(ST* pst)
{assert(pst);pst-a NULL;// top指向栈顶数据的下一个位置pst-top 0;// top指向栈顶数据//pst-top -1;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;}pst-a[pst-top] x;pst-top;
}void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}// 取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);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;
}
typedef struct {ST pushst;//用来存储数据ST popst;//用来导出数据} MyQueue;
具体实现
//用两个栈实现队列
MyQueue* myQueueCreate() {MyQueue* new (MyQueue*)malloc(sizeof(MyQueue));STInit(new-pushst);STInit(new-popst);return new;
}//入队列
void myQueuePush(MyQueue* obj, int x) {STPush(obj-pushst,x);//插入至数据栈pushst中}//查看队头元素
int myQueuePeek(MyQueue* obj) {//查看出数据栈popst中是否有数据有则直接查看栈顶数据没有就把存数据栈pushst导入到 出数据栈popst中if(STEmpty(obj-popst)){//把pushst数据全部导入popstwhile(!STEmpty(obj-pushst)){STPush(obj-popst,STTop(obj-pushst));STPop(obj-pushst);}}//返回出数据栈popst栈顶数据return STTop(obj-popst);}//出队列
int myQueuePop(MyQueue* obj) {//它会帮我们导数据到popst中popst栈顶的数据就是我们要删除的数据int pop myQueuePeek(obj);STPop(obj-popst);return pop;
}//判空
bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-pushst) STEmpty(obj-popst);//两个栈为NULL则队列为NULL}//销毁队列
void myQueueFree(MyQueue* obj) {STDestroy(obj-pushst);STDestroy(obj-popst);free(obj);
}
设计循环队列 思路
利用数组来创建循环队列
代码
typedef struct {int* a;int head;int rear;//指向最后一个数据的下一个空间int k;
} MyCircularQueue;//初始化循环队列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* new (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//多开一个空间用来解决数据为满与空的矛盾问题当然也可以在结构体多加个size解决new-a (int*)malloc(sizeof(int) * (k 1));new-head 0;new-rear 0;//尾数据的下一个位置new-k k;return new;
}//插入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//判断循环队列满没有满则不能继续插入if((obj-rear 1) % (obj-k 1) obj-head)//当尾数据指针 1 头指针时队列满return false;obj-a[obj-rear] value;obj-rear;obj-rear % obj-k 1;//循环return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//判断队列是否为空为空则不能继续删除if(obj-head obj-rear)//当尾指针 头指针时队列为空return false;obj-head;obj-head % obj-k 1; //循环return true;
}//返回队列头数据
int myCircularQueueFront(MyCircularQueue* obj) {if(obj-head obj-rear)return -1;return obj-a[obj-head];
}//返回队列尾数据即找尾指针指向的上一个地方
int myCircularQueueRear(MyCircularQueue* obj) {if(obj-head obj-rear)return -1;return obj-a[(obj-k obj-rear) % (obj-k 1)];//往前绕k-1去找rear之前的一个数据}//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//空return obj-head obj-rear;
}//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-rear 1) % (obj-k 1) obj-head;}//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}
