邢台网站建设策划,四川建设网有限责任公司是国企吗,安徽六安发现一例新冠阳性检测者,wordpress自动翻页http://blog.csdn.net/z84616995z/article/details/19204529 两个栈实现一个队列#xff1a; 原理方法#xff1a;用一个栈为主栈#xff0c;一个栈为辅助栈存放临时元素。 入队#xff1a;将元素依次压入主栈 出队#xff1a;先检测辅助栈是否为空#xff0c;如果非空 原理方法用一个栈为主栈一个栈为辅助栈存放临时元素。 入队将元素依次压入主栈 出队先检测辅助栈是否为空如果非空那么直接弹出辅助栈顶元素相当于出队。如果为空那么将主栈元素倒入到辅助栈中然后弹出辅助栈顶元素。达到先进先出的目的。 以下是代码 [cpp] view plain copy //两个个栈实现一个队列 /*#include iostream #include time.h #include windows.h using namespace std; #define MAX 10 struct stack { int Array[MAX]; int top; }; struct stack s1,s2; //初始化一个空栈 int Init_Stack() { s1.tops2.top -1;//top为-1表示空栈 return 1; } //入队 void enqueue(int Array[],int x) { if (s1.topMAX-1)//检测是否栈已满 { coutoverflow!endl; } else { s1.top; s1.Array[s1.top]x;//将元素压入主栈 } } //出队 int dequeue() { if (s1.top-1s2.top-1)//如果主栈和辅助栈都是空的那么就出现下溢。提示错误后返回 { coutunderflow!endl; return -1; } if (s2.top-1)//如果辅助栈为空那么就循环地将主栈元素倒入辅助栈 { for (int is1.top;i0;i--) { s1.top--;s2.top; s2.Array[s2.top]s1.Array[s1.top1]; } s1.top--; return s1.Array[s1.top1];//返回主栈最后一个元素作为出队元素 } else //如果辅助栈不空那么直接弹出辅助栈栈顶元素作为出队元素 { s2.top--; return s2.Array[s2.top1]; } } void main() { int x0; Init_Stack(); srand( (unsigned)time( NULL ) ); cout数组中的数据入队中。。。; for( int j0; j 100; j ) // 打印百分比 { cout.width(3); cout j %; Sleep(40); cout \b\b\b\b;//\b退格符号 } cout \n\n; coutArray; for (int i0;iMAX;i) { xrand()%100; coutx ; enqueue(s1.Array,x); } coutendl; cout所有数据入队完毕endl; coutendl; cout数组中的数据出队中。。。; for( j0; j 100; j ) // 打印百分比 { cout.width(3); cout j %; Sleep(40); cout \b\b\b\b;//\b退格符号 } cout \n\n; coutArray; for ( i0;iMAX;i) { coutdequeue() ; } coutendl; cout所有数据出队完毕endl; coutendl; enqueue(s1.Array, 56); coutdequeue()endl; coutdequeue()endl; coutdequeue()endl; enqueue(s1.Array, 65); enqueue(s1.Array, 10); enqueue(s1.Array, 32); coutdequeue()endl; coutdequeue()endl; enqueue(s1.Array, 2); coutdequeue()endl; } 运行时间为O(n),在进行倒入操作时需要循环倒入所以时间为n 两个队列实现一个栈 原理方法用一个队列为主队列一个队列为辅助队列存放临时元素。 入栈将元素依次压入主队列 出栈先将拥有n个元素的主队列的其中的n-1个元素倒入辅助队列然后将原主队列的最后剩下的一个元素弹出队列相当于出栈这个时候辅助队列和主队列进行交换继续进行刚才的出栈操作。 [cpp] view plain copy //两个队列实现一个栈 #include iostream #include time.h #include windows.h using namespace std; #define MAX 10 struct queue { int head;//声明队头指针 int tail;//声明队尾指针 int length;//声明队列当前含有的元素个数 int Array[MAX];//声明数组所能容纳的最大元素个数 }; struct queue q1,q2; //声明两个队列结构体全局变量 void Init_queue(struct queue q1)//初始化队列 { q1.headq1.tail1;//队列初始时是从数组Array[1]开始的所以其实Array[0]是数组最后一个元素而不是Array[MAX-1]这是需要注意的。 q1.length1; } //入栈 int push(int Array[],int x) { if (q1.headq1.tail1)//进行入队操作的前提判断是否队列已满 { cerroverflow!endl;//若已满那么提示错误后返回。 return -1; } else { if (q1.length0)//恢复队列中没有元素时的初始值q1.length1; { q1.length;q2.length; } q1.length;q2.length;//每次入队数组元素个数1 if (q1.tailq1.length)//队尾指针既然已经指向当前数组最后一个元素的下一个位置 { q1.tail0;//那么元素只能插入Array[0]最后一个元素原因在Init_queue函数注释中。 q1.Array[q1.tail]x; } else { q1.Array[q1.tail]x; q1.tail; if (q1.tailMAX)//若队尾指针指向数组最后一个元素的下一个位置 { q1.length--;q2.length--;//由于两个队列元素个数是从1开始的那么主和辅助队列元素个数已经超过MAX所以需要调整为MAX以便下次入队时插入到Array[0]这个位置 } } return q1.tail; } } //出栈 int pop() { int x0; if (q1.length0)//如果主队列里面有0个元素那么说明不能进行出队出栈操作直接返回错误提示 { cerrunderflowendl; return -1; } else { if (q1.tail0)//通常情况需要返回的是队头指针作为出队元素那么这里为什么返回队尾指针因为我们需要用两个队列实现一个栈那么有n个元素的主栈把n-1个元素传递给辅助队列后最后入队的也是将要出栈的元素肯定在主栈队尾。 { xq1.Array[q1.tail];//队尾指针指向0时其实指向的就是数组最后一位因为初始化是从1开始的直接返回Array[0] } else { xq1.Array[q1.tail-1];//队尾指针指向其它时由于队尾指针总是指向数组最后一个数据的下一位那么需要返回的是数组最后一个数据所以要-1. } while(q1.tail!q1.head)//队头和队尾相等时说明已经遍历了整个队列所以退出循环 { q2.Array[q2.tail]q1.Array[q1.head];//将主栈的数据传递给辅助栈 if (q2.tailMAX)//由于需要循环遍历队列所以当队尾等于数组所能容纳的最大元素个数时队尾指针自动调整到数组第一个位置。 { q2.tail0; } else { q2.tail; } if (q1.headMAX)//和上面的if-else类似。 { q1.head0; } else { q1.head; } } if (q1.tail0)//如果队尾指针等于0自动指向当前主队列的最后一个元素的下一个位置 { q1.tailq1.length;//这样在下次出队时能够返回队列的最后一个元素。 } else { q1.tail--;//如果队尾指针不等于0那么当前主队列队尾下标指向下一个需要出队的元素。 } swap(q1,q2);//原来的主队列转换为辅助队列原来的辅助队列转换为主队列。 q1.tailq2.tail;//由于转换后原主队列队尾下标变为辅助队列队尾下标所以需要将当前辅助队列队尾下标传递给主队列 q2.headq2.tail1;//辅助队列里的元素个数保持不变然后其指针恢复为初始状态。由于辅助队列只是起到一个临时保存队列中数据的作用所以每次主队列有元素出队就需要初始化辅助队列一下。 q1.length--;q2.length--;//每次出队后需要将辅助和主队列当前拥有的元素个数-1. return x;//主队列队尾元素出队相当于出栈 } } void swap(struct queue q1,struct queue q2)//辅助队列与主队列之间转换 { struct queue temp; tempq1; q1q2; q2temp; } void main() { int x0; Init_queue(q1); Init_queue(q2); srand( (unsigned)time( NULL ) ); cout数组中的数据入栈中。。。; for( int j0; j 100; j ) // 这个循环就是一个看起来很酷的小程序其实实际作用没有。^_^ { cout.width(3); cout j %; Sleep(40); cout \b\b\b\b;//\b退格符号 } cout \n\n; coutArray; for (int i0;iMAX;i)//对于开始q1和q2两个空栈来说设置q1为主栈q2为辅助栈 { xrand()%100; int tpush(q1.Array,x); if (t-1)//既然队列已满那么提示不能入栈后自动跳出循环。 { break; } if (q1.tail0) { coutq1.Array[q1.tail] ; } else { coutq1.Array[q1.tail-1] ; } } coutendl; cout所有数据入栈完毕endl; coutendl; cout数组中的数据出栈中。。。; for( j0; j 100; j ) // 打印百分比 { cout.width(3); cout j %; Sleep(40); cout \b\b\b\b;//\b退格符号 } cout \n\n; coutArray; for ( i0;iMAX;i) { coutpop() ; } coutendl; cout所有数据出栈完毕endl; coutendl; } 运行时间由于需要将主队列循环倒入到辅助队列中所以总时间为O(n).
