虫子 栈转队列 队列转栈 内核必备，基本算法，linux二次发育，项目远见
【摘要】 用栈实现队列 题目 队结构体 队初始化 入“队” 出“队”并取出队元素 返回队头 判断队空 队列销毁 队列代码（接口代码去我之前文章取） 算法开启小码农栈血脉 ==队列接口见 算法开启小码农队列血脉== 用队列实现栈 题目 栈结构体 栈初始化 入“栈” 出“栈”并取栈顶元素 取栈顶元素 判断栈空 栈销毁 用栈实现队列 题目 队结构体typedef struct { ST PushST...
用栈实现队列
题目
队结构体
typedef struct {
ST PushST;//入队栈
ST PopST;//出队栈
} MyQueue;
队初始化
MyQueue* myQueueCreate() {
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&q->PushST);//初始化入队栈
StackInit(&q->PopST);//初始化出队栈
return q;
}
入“队”
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->PushST,x);
}
出“队”并取出队元素
int myQueuePop(MyQueue* obj) {
//如果出队栈为空就从入队栈里面全导过来
if(StackEmpty(&obj->PopST))
{
//导数据
while(!StackEmpty(&obj->PushST))
{
//入队栈栈顶元素拿出来给出队栈
StackPush(&obj->PopST,StackTop(&obj->PushST));
//栈把入队栈的栈顶元素pop掉
StackPop(&obj->PushST);
}
}
//这时就说明都倒完了，所以开始pop掉出队栈元素
int tmp = StackTop(&obj->PopST);
StackPop(&obj->PopST);
return tmp;
}
返回队头
int myQueuePeek(MyQueue* obj) {
//如果出队栈为空就从入队栈里面全导过来
if(StackEmpty(&obj->PopST))
{
//导数据
while(!StackEmpty(&obj->PushST))
{
//入队栈栈顶元素拿出来给出队栈
StackPush(&obj->PopST,StackTop(&obj->PushST));
//栈把入队栈的栈顶元素pop掉
StackPop(&obj->PushST);
}
}
//就是出队函数那样只取队头而已
return StackTop(&obj->PopST);
}
判断队空
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->PushST) && StackEmpty(&obj->PopST);
}
队列销毁
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->PushST);
StackDestroy(&obj->PopST);
free(obj);
}
队列代码（接口代码去我之前文章取） 算法开启小码农栈血脉
typedef struct {
ST PushST;//入队栈
ST PopST;//出队栈
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&q->PushST);//初始化入队栈
StackInit(&q->PopST);//初始化出队栈
return q;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->PushST,x);
}
int myQueuePop(MyQueue* obj) {
//如果出队栈为空就从入队栈里面全导过来
if(StackEmpty(&obj->PopST))
{
//导数据
while(!StackEmpty(&obj->PushST))
{
//入队栈栈顶元素拿出来给出队栈
StackPush(&obj->PopST,StackTop(&obj->PushST));
//栈把入队栈的栈顶元素pop掉
StackPop(&obj->PushST);
}
}
//这时就说明都倒完了，所以开始pop掉出队栈元素
int tmp = StackTop(&obj->PopST);
StackPop(&obj->PopST);
return tmp;
}
int myQueuePeek(MyQueue* obj) {
//如果出队栈为空就从入队栈里面全导过来
if(StackEmpty(&obj->PopST))
{
//导数据
while(!StackEmpty(&obj->PushST))
{
//入队栈栈顶元素拿出来给出队栈
StackPush(&obj->PopST,StackTop(&obj->PushST));
//栈把入队栈的栈顶元素pop掉
StackPop(&obj->PushST);
}
}
//就是出队函数那样只取队头而已
return StackTop(&obj->PopST);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->PushST) && StackEmpty(&obj->PopST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->PushST);
StackDestroy(&obj->PopST);
free(obj);
}
==队列接口见 算法开启小码农队列血脉==
用队列实现栈
题目
栈结构体
typedef struct {
Queue q1;
Queue q2;//两个队列
} MyStack;
栈初始化
MyStack* myStackCreate() {
MyStack* st = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&st->q1);
QueueInit(&st->q2);
return st;
}
入“栈”
void myStackPush(MyStack* obj, int x) {
if(!QueueErase(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else//两个都为空时push给q2
{
QueuePush(&obj->q2,x);
}
}
出“栈”并取栈顶元素
int myStackPop(MyStack* obj) {
Queue* emptyQ = &obj->q1;
Queue* nonemptyQ = &obj->q2;//假设q2空，q1非空
//不是我们就互换位置
if(!QueueErase(emptyQ))
{
nonemptyQ = &obj->q1;
emptyQ = &obj->q2;
}
//非空队长大于一时朝空队里面挪动数据
while(QueueSize(nonemptyQ)>1)
{
//把非队空的对头数拿出push给对空的
QueuePush(emptyQ,QueueFront(nonemptyQ));
//然后把非队空的对头数pop掉
QueuePop(nonemptyQ);
}
//因为要返回栈顶数据所以存完再pop
int tmp = QueueFront(nonemptyQ);
//此时非空队就只还有一个数据，pop掉就行
QueuePop(nonemptyQ);
return tmp;
}
取栈顶元素
int myStackTop(MyStack* obj) {
//谁不为空就去谁队尾数据
if(!QueueErase(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
判断栈空
bool myStackEmpty(MyStack* obj) {
return QueueErase(&obj->q1)&&QueueErase(&obj->q2);
}
栈销毁
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
typedef struct {
Queue q1;
Queue q2;//两个队列
} MyStack;
MyStack* myStackCreate() {
MyStack* st = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&st->q1);
QueueInit(&st->q2);
return st;
}
void myStackPush(MyStack* obj, int x) {
if(!QueueErase(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else//两个都为空时push给q2
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
Queue* emptyQ = &obj->q1;
Queue* nonemptyQ = &obj->q2;//假设q2空，q1非空
//不是我们就互换位置
if(!QueueErase(emptyQ))
{
nonemptyQ = &obj->q1;
emptyQ = &obj->q2;
}
//非空队长大于一时朝空队里面挪动数据
while(QueueSize(nonemptyQ)>1)
{
//把非队空的对头数拿出push给对空的
QueuePush(emptyQ,QueueFront(nonemptyQ));
//然后把非队空的对头数pop掉
QueuePop(nonemptyQ);
}
//因为要返回栈顶数据所以存完再pop
int tmp = QueueFront(nonemptyQ);
//此时非空队就只还有一个数据，pop掉就行
QueuePop(nonemptyQ);
return tmp;
}
int myStackTop(MyStack* obj) {
//谁不为空就去谁队尾数据
if(!QueueErase(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
return QueueErase(&obj->q1)&&QueueErase(&obj->q2);
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）