队列实现栈以及栈实现队列

实现堆栈和堆栈实现队列

https://labuladong.gitee.io/algo/2/20/49/

看完这篇文章，你不仅可以学习算法例程，还可以去LeetCode获取以下问题：

22.用堆栈实现队列(简单)

25.用队列实现堆栈(简单)

———

队列是先入先出的数据结构，栈是先入后出的数据结构。图像是这样的：

事实上，这两种数据结构的底层都是通过数组或链表来实现的，但是它们的特性受到API的限制。那么今天我们来看看如何利用“栈”的特性实现一个“队列”，如何利用“队列”实现一个“栈”。

一、用栈实现队列

首先，队列的API如下：

类MyQueue {

/* *将元素添加到队列末尾*/

公共void push(int x)；

/* *删除团队领导的元素并返回*/

public int pop()；

/* *返回团队负责人元素*/

public int peek()；

/* *确定队列是否为空*/

public boolean empty()；

}

我们可以通过使用两个堆栈S1 s1、s2来实现队列的功能(放置堆栈时可能更容易理解):

类MyQueue {

私有StackInteger s1、S2；

public Myqueue(){ 0

s1=新堆栈()；

s2=新Stack()；

}

//.

}

当调用push对元素进行排队时，只需将元素压入s1。例如，push中的三个元素分别是1、2和3，因此底层结构如下：

/* *将元素添加到队列末尾*/

公共void push(int x){ 0

S1 . push(x)；

}

如果此时使用peek查看队列头的元素会怎么样？说队列头的元素应该是1是合理的，但是在s1中，1被压在栈底，现在轮到s2扮演中转的角色：当s2为空时，s1的所有元素都可以被取出并添加到s2中，然后s2中的元素按照先进先出的顺序排列。

/* *返回团队负责人元素*/

public int peek(){ 0

if (s2.isEmpty())

//将s1元素压入s2

while(！s1.isEmpty())

S2 . push(S1 . pop())；

返回S2 . peek()；

}

同样，对于pop操作，只需操作s2。

/* *删除团队领导的元素并返回*/

public int pop(){ 0

//首先调用peek，确保s2不为空。

peek()；

返回S2 . pop()；

}

最后，如何判断队列是否为空？如果两个堆栈都为空，则意味着队列为空：

/* *确定队列是否为空*/

public boolean empty(){ 0

返回S1 . isempty()；S2 . isempty()；

}

到目前为止，已经用栈结构实现了一个队列，核心思想是用两个栈相互协作。

值得一提的是，这些操作的时间复杂度是多少？有趣的是peek操作，调用时可能会触发while循环。这种情况下，时间复杂度为O(N)，但大多数情况下，虽然不会触发循环，时间复杂度为O(1)。因为pop操作调用peek，所以它的时间复杂度和peek一样。

在这种情况下，可以说它们最差的时间复杂度是O(N)，因为有一个while循环，可能需要将元素从s1移动到s2。

但是它们的平均时间复杂度为O(1)，应该这样理解：一个元素最多只能传输一次，也就是说peek操作平均了每个元素的时间复杂度。

是 O(1)。

二、用队列实现栈

如果说双栈实现队列比较巧妙，那么用队列实现栈就比较简单粗暴了，只需要一个队列作为底层数据结构。首先看下栈的 API：

class MyStack {
    
    /** 添加元素到栈顶 */
    public void push(int x);
    
    /** 删除栈顶的元素并返回 */
    public int pop();
    
    /** 返回栈顶元素 */
    public int top();
    
    /** 判断栈是否为空 */
    public boolean empty();
}

先说pushAPI，直接将元素加入队列，同时记录队尾元素，因为队尾元素相当于栈顶元素，如果要top查看栈顶元素的话可以直接返回：

class MyStack {
    QueueInteger q = new LinkedList();
    int top_elem = 0;
    /** 添加元素到栈顶 */
    public void push(int x) {
        // x 是队列的队尾，是栈的栈顶
        q.offer(x);
        top_elem = x;
    }
    
    /** 返回栈顶元素 */
    public int top() {
        return top_elem;
    }
}

我们的底层数据结构是先进先出的队列，每次pop只能从队头取元素；但是栈是后进先出，也就是说popAPI 要从队尾取元素：

解决方法简单粗暴，把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出了：

/** 删除栈顶的元素并返回 */
public int pop() {
    int size = q.size();
    while (size  1) {
        q.offer(q.poll());
        size--;
    }
    // 之前的队尾元素已经到了队头
    return q.poll();
}

这样实现还有一点小问题就是，原来的队尾元素被提到队头并删除了，但是top_elem变量没有更新，我们还需要一点小修改：

/** 删除栈顶的元素并返回 */
public int pop() {
    int size = q.size();
    // 留下队尾 2 个元素
    while (size  2) {
        q.offer(q.poll());
        size--;
    }
    // 记录新的队尾元素
    top_elem = q.peek();
    q.offer(q.poll());
    // 删除之前的队尾元素
    return q.poll();
}

最后，APIempty就很容易实现了，只要看底层的队列是否为空即可：

/** 判断栈是否为空 */
public boolean empty() {
    return q.isEmpty();
}

很明显，用队列实现栈的话，pop操作时间复杂度是 O(N)，其他操作都是 O(1)?。?

个人认为，用队列实现栈是没啥亮点的问题，但是用双栈实现队列是值得学习的。

从栈s1搬运元素到s2之后，元素在s2中就变成了队列的先进先出顺序，这个特性有点类似「负负得正」，确实不太容易想到。

希望本文对你有帮助。

＿＿＿＿＿＿＿＿＿＿＿＿＿