六兄弟做网站,翻译做网站,旅游网站功能简介,网站名字做版权需要源代码吗#x1f4af;#x1f4af;#x1f4af; 本篇总结利用栈如何实现队列的相关操作#xff0c;不难观察#xff0c;栈和队列是可以相互转化的#xff0c;需要好好总结它们的特性#xff0c;构造出一个恰当的结构来实现即可#xff0c;所以本篇难点不在代码思维#xff0c;…
本篇总结利用栈如何实现队列的相关操作不难观察栈和队列是可以相互转化的需要好好总结它们的特性构造出一个恰当的结构来实现即可所以本篇难点不在代码思维而是对结构的理解。⏰1.用栈实现队列入队列出队列获取队头元素判断队列是否为空销毁队列⏰2.完整代码⏰1.用栈实现队列 思路 一个栈专门用来插入数据 一个栈专门用来出数据
比如如果栈里有5个数据而要根据队列的特性出队列肯定出的是队头数据也就是1而在栈里怎么才能将数据1删除掉呢
我们的做法是将栈1的数据全部导入到栈2去。这样由原来的数据就倒过来了那删除栈顶元素即可。
删除栈顶元素之后我们分析发现这时的栈2如果再进行删除就和队列的删除操作是一致的了不需要再导回去如果要再删除队头数据2直接让栈2删除即可。 所有我们发现经过一次导数据之后栈2就完全可以当成pop数据的。 那我们如果想插入数据该怎么插入呢 根据队列特性我们只能从队尾插入也就是元素5的后面插入数据。该怎么插呢将数据插入栈2里那可不行将数据插入栈2中后原来的顺序就乱了。所以我们将数据插入到栈1去比如我们要插入数据678.直接插入到栈1即可。 这样就不会影响栈2出数据的顺序了并且插入的顺序也不受出数据的影响。 唯一需要注意的是当栈2的数据都删除空了这时就需要将栈1的数据再导入到栈2中这样就能接着删除队列中的数据了。 所以我们可以直接定义两个栈一个栈用来插入数据一个栈用来删除数据。
typedef struct
{ ST pushst;ST popst;
} MyQueue;不过在定义之前我们需要写一个栈的数据结构因为C语言是没有自己的栈的。
typedef int STData;
typedef struct Stack
{int* a;int top;int capicty;
}ST;
void STInit(ST*ps);//初始化栈表
void STDestroy(ST* ps);//销毁栈表
void STpush(ST* ps,STData x);//压栈在栈顶压入一个元素
void STpop(ST* ps);//出栈在栈顶弹出一个元素。
STData STTop(ST* ps);//访问栈顶元素
int STSize(ST* ps);
int STEmpty(ST*ps);//
void STInit(ST* ps)//初始化栈表
{assert(ps);//判断结构体指针不为NULL//一上来可以给栈表初始化容量ps-a (STData*)malloc(sizeof(STData) * 4);if (ps-a NULL)//判断是否开辟成功{perror(malloc);}//初始话容量为4ps-capicty 4;ps-top 0;//top0 表示的是指向栈顶元素的下一个位置//top如果为-1则表示栈顶元素的位置
}
void STDestroy(ST* ps)//销毁栈表
{assert(ps);free(ps-a);ps-a NULL;ps-capicty 0;ps-top 0;}
void STpush(ST* ps, STData x)//压栈在栈顶压入一个元素--在压入之前也要考虑是否需要增容
{assert(ps);//断言判断if (ps-top ps-capicty){//增容STData* tmp (STData*)realloc(ps-a, sizeof(STData) * ps-capicty * 2);if (tmp NULL){perror(realloc);}ps-a tmp;ps-capicty * 2;}ps-a[ps-top] x;//将元素压入栈顶一开始top是0当元素进去后再让top指向该栈顶元素后一个位置ps-top;
}
int STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}void STpop(ST* ps)//出栈在栈顶弹出一个元素。
{assert(ps);//删除元素之前要检查栈表是否还有元素可删assert(!STEmpty(ps));//当栈表为NULL是断言ps-top--;}
int STSize(ST* ps)//计算栈表长度
{assert(ps);return ps-top;//top的长度就是栈表的长度
}
STData STTop(ST* ps)//访问栈顶元素
{assert(ps);return ps-a[ps-top - 1];
}接下来就是获取一个指向 MyQueue队列的指针。 MyQueue* myQueueCreate() //发现没有传入参数并且返回值是指向栈的指针说明里面是用malloc开辟的内存而不是在栈上开辟的
{MyQueue *q(MyQueue*)malloc(sizeof(MyQueue));if(qNULL){perror(malloc);}STInit(q-pushst);//一开始需要对两个栈进行初始化STInit(q-popst);return q;
}入队列
入队列即插入数据直接在push栈进行插入即可不用担心顺序什么的因为当pop栈没有数据时就会让push栈导数据过来这时的顺序就符合队列的要求了
void myQueuePush(MyQueue* obj, int x)
{//只管往pushst里插入即可不需要管其他STpush(obj-pushst,x);
}出队列
出队列呢就指望pop栈即可不过在出队列之前我们需要检查一下pop栈里是否为空如果为空就需要将push栈里的数据导过来如果不为空那就可以进行删除操作了。 int myQueuePop(MyQueue* obj)
{//需要讨论下当pop这个栈为空时需要将push栈中的数据导过来if(STEmpty(obj-popst)){while(!STEmpty(obj-pushst))//将push栈中的所有数据都导过去即可{STpush(obj-popst,STTop(obj-pushst));STpop(obj-pushst);//删除push栈里的这个数据}}//走到这里有两种情况可能push栈里的数据导光了也可能是pop栈里本来就有数据不为空int topSTTop(obj-popst);//将这个栈顶元素记录下来最后需要返回STpop(obj-popst);return top;
}
获取队头元素
获取队头数据这个操作与刚刚的删除操作基本一样只不过该操作不需要将数据删除直接返回栈顶元素即可所以大部分代码是一样的。
int myQueuePeek(MyQueue* obj)
{//这里跟pop数据很像,直接return 栈顶元素即可//需要讨论下当pop这个栈为空时需要将push栈中的数据导过来if(STEmpty(obj-popst)){while(!STEmpty(obj-pushst))//将push栈中的所有数据都导过去即可{STpush(obj-popst,STTop(obj-pushst));STpop(obj-pushst);}}//走到这里有两种情况可能push栈里的数据导光了也可能是pop栈里本来就有数据不为空return STTop(obj-popst);}判断队列是否为空
判断队列是否为空其实很简单因为该队列是由两个栈构成当两个栈都为空时则该队列肯定为空。 bool myQueueEmpty(MyQueue* obj)
{return STEmpty(obj-pushst)STEmpty(obj-popst);
}销毁队列
销毁队列也简单要想真正的释放该队列需要理解该队列的结构是如何构成的。 该队列是由两个栈构成栈是由数组构成。 释放空间从里到外释放先释放两个栈空间再释放队列空间。
void myQueueFree(MyQueue* obj)
{STDestroy(obj-pushst);STDestroy(obj-popst);free(obj);
}⏰2.完整代码 typedef int STData;
typedef struct Stack
{int* a;int top;int capicty;
}ST;
void STInit(ST*ps);//初始化栈表
void STDestroy(ST* ps);//销毁栈表
void STpush(ST* ps,STData x);//压栈在栈顶压入一个元素
void STpop(ST* ps);//出栈在栈顶弹出一个元素。
STData STTop(ST* ps);//访问栈顶元素
int STSize(ST* ps);
int STEmpty(ST*ps);//
void STInit(ST* ps)//初始化栈表
{assert(ps);//判断结构体指针不为NULL//一上来可以给栈表初始化容量ps-a (STData*)malloc(sizeof(STData) * 4);if (ps-a NULL)//判断是否开辟成功{perror(malloc);}//初始话容量为4ps-capicty 4;ps-top 0;//top0 表示的是指向栈顶元素的下一个位置//top如果为-1则表示栈顶元素的位置
}
void STDestroy(ST* ps)//销毁栈表
{assert(ps);free(ps-a);ps-a NULL;ps-capicty 0;ps-top 0;}
void STpush(ST* ps, STData x)//压栈在栈顶压入一个元素--在压入之前也要考虑是否需要增容
{assert(ps);//断言判断if (ps-top ps-capicty){//增容STData* tmp (STData*)realloc(ps-a, sizeof(STData) * ps-capicty * 2);if (tmp NULL){perror(realloc);}ps-a tmp;ps-capicty * 2;}ps-a[ps-top] x;//将元素压入栈顶一开始top是0当元素进去后再让top指向该栈顶元素后一个位置ps-top;
}
int STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}void STpop(ST* ps)//出栈在栈顶弹出一个元素。
{assert(ps);//删除元素之前要检查栈表是否还有元素可删assert(!STEmpty(ps));//当栈表为NULL是断言ps-top--;}
int STSize(ST* ps)//计算栈表长度
{assert(ps);return ps-top;//top的长度就是栈表的长度
}
STData STTop(ST* ps)//访问栈顶元素
{assert(ps);return ps-a[ps-top - 1];
}
typedef struct
{ ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate()
{MyQueue *q(MyQueue*)malloc(sizeof(MyQueue));if(qNULL){perror(malloc);}STInit(q-pushst);STInit(q-popst);return q;
}void myQueuePush(MyQueue* obj, int x)
{//只管往pushst里插入即可不需要管STpush(obj-pushst,x);
}int myQueuePop(MyQueue* obj)
{//需要讨论下当pop这个栈为空时需要将push栈中的数据导过来if(STEmpty(obj-popst)){while(!STEmpty(obj-pushst))//将push栈中的所有数据都导过去即可{STpush(obj-popst,STTop(obj-pushst));STpop(obj-pushst);}}//走到这里有两种情况可能push栈里的数据导光了也可能是pop栈里本来就有数据不为空int topSTTop(obj-popst);STpop(obj-popst);return top;
}int myQueuePeek(MyQueue* obj)
{//这里跟pop数据很像,直接return 栈顶元素即可//需要讨论下当pop这个栈为空时需要将push栈中的数据导过来if(STEmpty(obj-popst)){while(!STEmpty(obj-pushst))//将push栈中的所有数据都导过去即可{STpush(obj-popst,STTop(obj-pushst));STpop(obj-pushst);}}//走到这里有两种情况可能push栈里的数据导光了也可能是pop栈里本来就有数据不为空return STTop(obj-popst);}bool myQueueEmpty(MyQueue* obj)
{return STEmpty(obj-pushst)STEmpty(obj-popst);
}void myQueueFree(MyQueue* obj)
{STDestroy(obj-pushst);STDestroy(obj-popst);free(obj);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj myQueueCreate();* myQueuePush(obj, x);* int param_2 myQueuePop(obj);* int param_3 myQueuePeek(obj);* bool param_4 myQueueEmpty(obj);* myQueueFree(obj);
*/
