数据结构——栈和队列的相互模拟

栈只能一端进行插入和删除具有先进后出的特点队列一端进行插入一端进行删除具有先进先出的特点1.两个栈来模拟一个队列此时我们将第一个栈称为S1将第二个栈称为S2。思路入队栈的插入是只有一端进行插入。队列的插入也是只有一端进行插入。所以在宏观视觉上栈的插入和队列的插入没有什么区别。所以我们此时在进行插入是时候只需在S1这个栈上进行插入即可。出队因为队列只能一端进行插入而另一端进行删除具有先进先出的特点。而栈是只有一端进行插入和删除具有先进后出的特点。此时我们拥有两个栈在S1这个栈中已经拥有数据元素我们想要实现队列的删除效果需要将S1中的数据元素插入到S2中此时在最开始插入的数据本应在S1的栈底此时就在了S2的栈顶进行删除只需删除S2中的元素即可。具体思路是如此但是仍然有瑕疵如果S2中还有没有被删除完全的元素S1有新插入的元素并且我们还要删除元素呢那么此时我们我们就不能让S1中的数据先插入到S2当中因为相较于S1中的数据此时S2中的数据是先插入S1的只不过我们将其放置到了S2中而已为了满足队列的先进先出特特点我们此时必须先删除S2中的数据。也就意味着每次删除的时候我们必须先去判断S2是否为空不空则直接从S2中出一个数如果S2的空了则说明剩余数据全部均在S1中此时只需要将S1中的数据全部插入到S2中此时S2中有数据在S2上进行删除即可。图文解释假设一开始我们在S1中先插入了 45 然后是 56 最后是67此时我要删除数据就需要先将S1中的数据放置到S2中再进行删除 shan删除完45之后此时S2中剩下了 56 67 如果此时我再进行对S1的插入并且删除的话我仍然只能先删S2中的值当S2中的值完全没有的时候再将S1中的值全部插入到S2中代码实现1.结构体定义typedef struct TwoStack_toQueue { std::stackint S1; //std::-表示用C标准库里面的东西 //stack-表示栈 //int-表示栈里面存的数据是int 型 //S1:表示入队栈 //S2表示出队栈 std::stackint S2; }TwoStack_toQueue;入队bool TSQ_Push(TwoStack_toQueue* ptsq, int val) { //插入规则无脑的向S1插入 ptsq-S1.push(val); //通过指针找到入队栈S1 调用系统自带的插入函数 将val这个值进行插入 return true;出队bool TSQ_Pop(TwoStack_toQueue* ptsq) { if (!ptsq-S2.empty()) { ptsq-S2.pop(); return true; } //判断S2是否为空 如果不为空 直接删除 while (!ptsq-S1.empty()) //将S1中的全部的数据按照栈插入放置到S2中 { int tmp ptsq-S1.top(); //获取栈顶元素值 获取栈顶元素只具有将其值获取出来 没有其他权限 //将获取出的值初始化给tmp ptsq-S1.pop(); //删除S1中的栈顶元素值 不然每次获取的栈顶元素都是一个值 ptsq-S2.push(tmp); //将获取的值插入到S2中 } ptsq-S2.pop(); //删除S2中的栈顶元素值 return true; }2.两个队列来模拟一个栈队列:一端进行插入和一端进行删除具有先进先出的特点站栈只能在一端进行插入和删除具有先进后出的特点假设此时有两个队列分别为Q1 Q2思路入栈因为栈的插入就是一端进行插入队列也是一端进行插入他们的区别只在于删除所以宏观视觉上两个没有什么区别此时只需在Q1中持续插入即可出栈栈具有在同一端插入和删除具有先进后出的特点队列在一端插入一段删除具有先进后出的特点为了满足栈的先进后出的特点如果Q1非空此时就意味着我们要删除的值就在Q1的队尾将除了队尾元素外的其他元素全部按照队列插入插入到Q2中最后再删除Q1中的值。如果Q1空了此时就意味着我们要删除的值一定在Q2的队尾将除了队尾元素外的其他元素全部按照队列插入插入到Q1中最后再删除Q1中的值图文表示在队列Q1中插入值 12 23 34Q1非空所以此时我们要删除的值就是34也就是队尾元素将除了队尾元素外全部按照队列插入到Q2中直接删除34即可继续删除Q1空了此时我们要删除的元素就是23也就是Q2的队尾元素将除了队尾元素外将其他元素按照队列插入到Q1中。删除元素即可代码表示入栈bool TQS_Push(TwoQueue_toStack* ptqs, int val) { //插入规则无脑的向Q1插入 ptqs-Q1.push(val); return true; }出栈bool TQS_Pop(TwoQueue_toStack* ptqs) { if (!ptqs-Q1.empty()) { int Size_Q1 ptqs-Q1.size(); //获取队列有几个元素 for (int i 0; i Size_Q1 - 1; i) //因为我们要将除了队尾元素外其他的元素全部按照队列插入到Q2 所以循环只能是size-1 { ptqs-Q2.push(ptqs-Q1.front()); ptqs-Q1.pop(); } ptqs-Q1.pop(); return true; } int Size_Q2 ptqs-Q2.size(); for (int i 0; i Size_Q2 - 1; i) { ptqs-Q1.push(ptqs-Q2.front()); ptqs-Q2.pop(); } ptqs-Q2.pop(); return true; }