潮州哪里有做网站,网络服务包含哪些服务,触摸屏网站开发,wordpress 群目录
【1】用队列实现栈
思路分析
易错总结
Queue.cQueue.h手撕队列
声明栈MyStack
创建初始化栈myStackCreate
压栈myStackPush
出栈返回栈顶元素myStackPop
返回栈顶元素myStackTop
判断栈空否myStackEmpty
释放空间myStackFree
MyStack总代码…目录
【1】用队列实现栈
思路分析
易错总结
Queue.cQueue.h手撕队列
声明栈MyStack
创建初始化栈myStackCreate
压栈myStackPush
出栈返回栈顶元素myStackPop
返回栈顶元素myStackTop
判断栈空否myStackEmpty
释放空间myStackFree
MyStack总代码
【2】用栈实现队列
思路分析
易错总结
Stack.hStack.c手撕栈
声明队列MyQueue
创建初始化队列myQueueCreate
入队列myQueuePush
返回队头元素myQueuePeek
出队列返回队头元素myQueuePop
判断队列空否myQueueEmpty
释放空间myQueueFree
MyQueue总代码 昨天导游考试考完啦希望明年是导游小唐当然代码我们不能忘敲代码
【1】用队列实现栈 请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。 实现 MyStack 类 void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。 思路分析 压栈把元素放到不为空的队列里面。两者若都为空随便放一个出栈把不为空的队列里面元素1全部导入另外一个为空队列里面Pop最后元素。
易错总结
创建的临时变量出了作用域就销毁了所以需要malloc才可。类型匹配的问题假设法的使用销毁的时候要先销毁队列开辟的空间不然会造成野指针。匿名结构体耦合性- 优先级高于 Queue.cQueue.h手撕队列
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.htypedef int QDataType;
//创建队列节点
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;
//两个指针维护链表队列
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
//接口的实现
void QueueInit(Queue* pq);//初始化
void QueueDestroy(Queue* pq);//空间释放
void QueuePush(Queue* pq, QDataType x);//放元素到队列尾
void QueuePop(Queue* pq);//出元素到队头
QDataType QueueFront(Queue* pq);//队列头的元素
QDataType QueueBack(Queue* pq);//队列尾的元素
bool QueueEmpty(Queue* pq);//判断队列是否是否为NULL
int QueueSize(Queue* pq);//队列里面的元素个数
//不需要头节点初始化
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}
QNode* Createnode(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));newnode-val x;newnode-next NULL;return newnode;
}
//Push元素
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//创建节点QNode* newnode Createnode(pq,x);if (pq-phead NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}
//Pop元素
void QueuePop(Queue* pq)
{assert(pq);assert(pq-phead);//为NULL的判断QNode* cur pq-phead;pq-phead pq-phead-next;free(cur);cur NULL;//为一个节点的判断if (pq-phead NULL){pq-ptail NULL;}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;
}
//判断是否为NULL
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;//return pq-size 0
}
//队员元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
//空间释放
void QueueDestroy(Queue* pq)
{assert(pq);while (pq-phead){QNode* cur pq-phead;pq-phead pq-phead-next;free(cur);cur NULL;}pq-phead NULL;pq-ptail NULL;pq-size 0;
}
在之前的博文里面我们详细的阐述了单链表实现【队列】的实现。这里就不在过多解释了。这里我们来用【两个队列】实现一个【栈】
声明栈MyStack
//匿名结构体
typedef struct {Queue Q1;Queue Q2;
} MyStack;//结构体类型
//一级指针修改结构体变量
struct {Queue Q1;Queue Q2;
} MyStack;//结构体变量
创建初始化栈myStackCreate
//初始化
MyStack* myStackCreate() {//MyStack mystack;出了作用域就销毁了MyStack*obj(MyStack*)malloc(sizeof(MyStack));QueueInit(obj-Q1);QueueInit(obj-Q2);return obj;
}
压栈myStackPush
//放元素
void myStackPush(MyStack* obj, int x) {assert(obj);//找不为NULL的队列依次插入if(!QueueEmpty(obj-Q1))//!0{QueuePush(obj-Q1, x);//尾插}else// 0{QueuePush(obj-Q2, x);}//两个0 随便进一个
}
出栈返回栈顶元素myStackPop
//出元素
int myStackPop(MyStack* obj) {assert(obj);//判断为空/非空------假设法Queue*nonemptyobj-Q1;Queue*emptyobj-Q2;if(QueueEmpty(obj-Q1))//0true与上面逻辑相反//出了作用域就销毁了姐姐❌{nonemptyobj-Q2;emptyobj-Q1;//创建}while(QueueSize(nonempty)1)//队列里面的元素个数 1{int x QueueFront(nonempty);//队列头的元素QueuePush(empty, x);//放元素到队列尾QueuePop(nonempty);//出元素到队头}int BackQueueFront(nonempty);//队列尾的元素QueuePop(nonempty);return Back;
}
返回栈顶元素myStackTop
//栈顶元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(obj-Q1)) {return QueueBack(obj-Q1);}else{return QueueBack(obj-Q2);}
}
判断栈空否myStackEmpty
//判空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-Q1) QueueEmpty(obj-Q2);//
}
释放空间myStackFree
void myStackFree(MyStack* obj) {QueueDestroy(obj-Q1);QueueDestroy(obj-Q2);free(obj);objNULL;
}
MyStack总代码
typedef struct {Queue Q1;Queue Q2;
} MyStack;
//一级指针修改结构体变量//初始化
MyStack* myStackCreate() {//MyStack mystack;出了作用域就销毁了MyStack*obj(MyStack*)malloc(sizeof(MyStack));QueueInit(obj-Q1);QueueInit(obj-Q2);return obj;
}//放元素
void myStackPush(MyStack* obj, int x) {assert(obj);//找不为NULL的队列依次插入if(!QueueEmpty(obj-Q1))//!0{QueuePush(obj-Q1, x);//尾插}else// 0{QueuePush(obj-Q2, x);}//两个0 随便进一个
}//出元素
int myStackPop(MyStack* obj) {assert(obj);//判断为空/非空------假设法Queue*nonemptyobj-Q1;Queue*emptyobj-Q2;if(QueueEmpty(obj-Q1){nonemptyobj-Q2;emptyobj-Q1;//创建}while(QueueSize(nonempty)1)//队列里面的元素个数 1{int x QueueFront(nonempty);//队列头的元素QueuePush(empty, x);//放元素到队列尾QueuePop(nonempty);//出元素到队头}int BackQueueFront(nonempty);//队列尾的元素QueuePop(nonempty);return Back;
}//栈顶元素
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);objNULL;
}
【2】用栈实现队列 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty 实现 MyQueue 类 void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false 思路分析 一个栈S1用来专门入数据Push另外一个栈S2用来专门出数据PopS2为空的时候才能把S1的数据导入S2 直到S1为空S2不为空的时候直接出数据即可队列出数据的顺序性质 栈导入另外一个栈出数据的顺序
易错总结
创建的临时变量出了作用域就销毁了所以需要malloc才可。类型匹配的问题销毁的时候要先销毁队列开辟的空间不然会造成野指针。匿名结构体耦合性- 优先级高于!STempty(obj-stackpush))//!0 flase---true开始导 直到0 true 结构体和结构体指针 Stack.hStack.c手撕栈
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);
STDatatype STTop(ST* pst);
bool STempty(ST* pst);
int STSize(ST* pst);void STInit(ST* pst)
{assert(pst);pst-a 0;pst-top 0;pst-capacity 0;
}void Createcapacity(ST* pst)
{if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : 2 * pst-capacity;STDatatype* tmp (STDatatype*)realloc(pst-a, sizeof(ST) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}
}void STPush(ST* pst, STDatatype x)
{assert(pst);Createcapacity(pst);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;
}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top 0;pst-capacity 0;
}
同样我们之前用数组实现了【栈】这里我们在来用两个栈实现【队列】 。
声明队列MyQueue
typedef struct {ST stackpush;ST stackpop;
} MyQueue;
创建初始化队列myQueueCreate
MyQueue* myQueueCreate() {MyQueue*obj(MyQueue*)malloc(sizeof(MyQueue));STInit(obj-stackpush);STInit(obj-stackpop);return obj;
}
入队列myQueuePush
//入队列
void myQueuePush(MyQueue* obj, int x) {STPush(obj-stackpush, x);
}
返回队头元素myQueuePeek
//取出队列的数据 --所以可以先实现这个
int myQueuePeek(MyQueue* obj) {if(STempty(obj-stackpop))//0 true为空导数据{while(!STempty(obj-stackpush))//0//!0 flase---true开始导 直到0 true ---false{int xSTTop(obj-stackpush);STPush(obj-stackpop,x);STPop(obj-stackpush);}}return STTop(obj-stackpop);
}
出队列返回队头元素myQueuePop
//出队列 为NULL就导数据/出队列 不为NULL出队列
int myQueuePop(MyQueue* obj) {int backmyQueuePeek(obj);STPop(obj-stackpop);return back;
}判断队列空否myQueueEmpty
bool myQueueEmpty(MyQueue* obj) {return STempty(obj-stackpush) STempty(obj-stackpop);
}
释放空间myQueueFree
void myQueueFree(MyQueue* obj) {STDestroy(obj-stackpush);STDestroy(obj-stackpop);free(obj);objNULL;
}
MyQueue总代码
typedef struct {ST stackpush;ST stackpop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue*obj(MyQueue*)malloc(sizeof(MyQueue));STInit(obj-stackpush);STInit(obj-stackpop);return obj;
}
//入队列
void myQueuePush(MyQueue* obj, int x) {STPush(obj-stackpush, x);
}//取出队列的数据 --所以可以先实现这个
int myQueuePeek(MyQueue* obj) {if(STempty(obj-stackpop))//0 true为空导数据{while(!STempty(obj-stackpush))//0//!0 flase---true开始导 直到0 true ---false{int xSTTop(obj-stackpush);STPush(obj-stackpop,x);STPop(obj-stackpush);}}return STTop(obj-stackpop);
}//出队列 为NULL就导数据/出队列 不为NULL出队列
int myQueuePop(MyQueue* obj) {int backmyQueuePeek(obj);STPop(obj-stackpop);return back;
}//
bool myQueueEmpty(MyQueue* obj) {return STempty(obj-stackpush) STempty(obj-stackpop);
}void myQueueFree(MyQueue* obj) {STDestroy(obj-stackpush);STDestroy(obj-stackpop);free(obj);objNULL;
}
不要对比代码怎么想怎么写调试很重要调式按照自己预期的去走读代码最后上编译器编译出错运行的问题执行错误逻辑的问题
✔✔✔✔✔最后感谢大家的阅读若有错误和不足欢迎指正
【数组栈】实现-CSDN博客
单链表实现【队列】-CSDN博客
