欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

使用两个栈实现队列

程序员文章站 2022-07-13 09:56:08
...

使用两个栈实现队列

参考文章

栈的队列的特点

栈和队列都是用来保存数据的,无论底层是使用数组还是链表来实现,其基本原理是不变的,那就是栈的特点的先进后出,队列的特点是先进先出。

栈的常用方法

  • isEmpty()

    • 判断栈是否为空
  • size()

    • 返回栈中元素的个数
  • push()

    • 向栈中插入数据
  • pop()

    • 从栈中弹出数据并返回
  • peek()

    • 返回栈顶的数据

使用栈实现队列

首先我们来考虑如何使用两个栈来实现队列。队列的特点是先进先出,如果向队列中保存”hollis”的顺序是h、o、l、l、i、s,那么取出元素的数序也应该是h、o、l、l、i、s。

使用两个栈实现队列

而对于栈来说,如果你想要让一个元素能够第一个被弹出,就要保证他永远位于栈的顶部。也就是说,如果你希望出站的顺序是h、o、l、l、i、s,那么入站顺序需要时silloh。

使用两个栈实现队列

我们现在已经有的数据结构是栈,如果按照h、o、l、l、i、s的顺序向一个栈中保存数据的话,这些元素在栈中的顺序应该是s、i、l、l、o、h。也就是他正常的弹出顺序应该是silloh,但是我们想要的弹出顺序是hollis。 那么如何解决这个问题呢,就需要另外一个栈来配合,两个栈互相倒换。具体如何操作呢?

使用两个栈实现队列

有一种方案是这样的:两个栈严格区分开来使用,一个专门用来做插入(插入栈),一个专门用来做弹出(弹出栈)。这样在做插入的时候什么都不需要做,直接调用插入栈的push方法就可以了。但是在弹出的时候就要麻烦一点,先判断在弹出栈中是否包含数据,++如果包含,直接从顶部弹出,如果不包含,把插入栈中的元素挨个导入到弹出栈中。然后再从栈顶将第一个元素弹出。++

说起来好像挺绕的,没关系。接着往下看,我们先来定义一下这个队列:

class MyQueue {
       stack<int> in;
       stack<int> out;
}

接下来,我们通过一张图来模拟下如何使用两个栈来实现队列的插入操作。

使用两个栈实现队列

上图中可以看出来,插入还是比较简单的,只需要往插入栈中push就可以了,代码实现如下:

void push(int x) {
   in.push(x);
}

插入的时候简单了,那么弹出的时候可能就要经过一番操作了。再来一张图,看看如何使用两个栈来实现队列的弹出操作。 简单介绍下过程:队列中原有三个数据,插入顺序是HOL,进行以下三个操作:
1. 弹出H,
2. 插入L,
3. 弹出O。

使用两个栈实现队列

从上面的图中可以看到,当我们尝试弹出H的时候,由于stack-out为空,需要把stack-in栈中的数据pop出来,并push进入stack-out,然后再从stack-out的栈顶就能直接弹出H了。 当我们尝试弹出O的时候,因为stack-out中包含数据,那么就直接从stack-out中往外弹数据就可以了。

代码实现如下:

int pop() {
   if (!out.empty()) {
       int temp = out.top();
       out.pop();
       return temp;
   }
   else {
       if (in.empty()) {
           return -1;
       }
       else {
           while (!in.empty()) {
               out.push(in.top());
               in.pop();
           }
           int temp = out.top();
           out.pop();
           return temp;
       }
   }
}
相关标签: 逻辑