使用队列实现堆栈


难度级别 易得奖学金
经常问 贝宝
设计 队列

实现以下功能 使用标准操作的数据结构 队列,

  1. push(x)–>将元素x推入堆栈
  2. pop()–>删除堆栈顶部的元素
  3. top()–>返回堆栈顶部的元素
  4. empty()–>返回堆栈是否为空

例子

输入:
stack.push(1);
stack.push(2);
stack.top(); //返回2
stack.pop(); //返回2
stack.empty(); //返回false
输出:
2
2
false

使用队列实现堆栈的算法

可以使用2个队列(例如q1和q2)来实现堆栈。

推(x)

将x推入q1的末尾,并将其保留在top变量的堆栈顶部。
伪代码

void push(int x) {
    q1.add(x);
    top = x;
}

时间复杂度= O(1)

最佳()

堆栈的顶部始终保持在top变量中,因此只需返回顶部即可。
伪代码

int top() {
    return top;
}

时间复杂度= O(1)

空的()

如果队列q1为空,则堆栈为空。
伪代码

boolean empty() {
    return q1.isEmpty();
}

时间复杂度= O(1)

流行音乐()

队列q1的后部包含堆栈的顶部,令q1的大小为n

  1. 将队列q1的(n – 1)个元素移到队列q2。
  2. 另外,将栈顶保持为要传输的当前变量。
  3. 现在,q1仅包含1个位于堆栈顶部的元素。
  4. 删除此元素并将其存储在某个变量中(例如ele)。
  5. 将所有元素从队列q2移动到队列q1。
  6. 返回ele。

时间复杂度= O(N) 
其中n是队列中元素的数量。

考虑一个例子,
q1 = 3-> 5-> 7-> 1-> 2
q2 =空

弹出一个元素。

  1. 将(n – 1)从q1转移到q2
    q1 = 2和q2 = 3-> 5-> 7-> 1
  2. 删除元素并将其存储在q1中。
    q1 =空且q2 = 3-> 5-> 7-> 1且ele = 2
  3. 将所有元素从q2移到q1。
    q1 = 3-> 5-> 7-> 1和q2 = null
  4. 返回ele。

请参阅下图以进行澄清。

使用队列实现堆栈

伪代码

int pop() {
    int n = q1.size();
    for (int i = 0; i < n - 1; i++) {
        int curr = q1.remove();
        q2.add(curr);
        top = curr;
    }
    int ele = q1.remove();
    n = q2.size();
    for (int i = 0; i < n; i++) {
        q1.add(q2.remove());
    }
    return ele;
}

时间复杂度= O(N)

使用队列实现堆栈的JAVA代码

import java.util.Queue; 
import java.util.LinkedList;
public class StackUsingQueues {
    // Two queues to implement stack
    private static Queue<Integer> q1 = new LinkedList<>();
    private static Queue<Integer> q2 = new LinkedList<>();
    // Stores the top element of stack
    private static int top;

    private static void push(int x) {
        // Add element at rear of q1
        q1.add(x);
        // update top as current element
        top = x;
    }

    private static int top() {
        // Top stores the top of stack
        return top;
    }

    private static int pop() {
        int n = q1.size();
        // Shift (n - 1) elements from q1 to q2 and update top as curr
        // element transferred
        for (int i = 0; i < n - 1; i++) {
            int curr = q1.remove();
            q2.add(curr);
            top = curr;
        }
        // q1 contains only 1 element which is top of stack
        // store the element in ele and remove it from q1
        int ele = q1.remove();
        n = q2.size();
        // Again transfer back the elements from q2 to q1
        for (int i = 0; i < n; i++) {
            q1.add(q2.remove());
        }
        // return ele, this is the top of stack
        return ele;
    }
    
    private static boolean empty() {
        // If q1 is empty then stack is empty
        return q1.isEmpty();
    }
    
    public static void main(String[] args) {
        // Example
        push(1);
        push(2);
        System.out.println(top());
        System.out.println(pop());
        System.out.println(empty());
    }
}

使用队列实现堆栈的C ++代码

#include <bits/stdc++.h>
using namespace std;

// Two queues to implement stack
queue<int> q1;
queue<int> q2;
// Stores the top element of stack
int Top;

void push(int x) {
    // Add element at rear of q1
    q1.push(x);
    // update top as current element
    Top = x;
}

int top() {
    // Top stores the top of stack
    return Top;
}

bool empty() {
    // If q1 is empty then stack is empty
    return q1.empty();
}

int pop() {
    int n = q1.size();
    // Shift (n - 1) elements from q1 to q2 and update top as curr
    // element transferred
    for (int i = 0; i < n - 1; i++) {
        int curr = q1.front();
        q1.pop();
        q2.push(curr);
        Top = curr;
    }
    // q1 contains only 1 element which is top of stack
    // store the element in ele and remove it from q1
    int ele = q1.front();
    q1.pop();
    n = q2.size();
    // Again transfer back the elements from q2 to q1
    for (int i = 0; i < n; i++) {
        q1.push(q2.front());
        q2.pop();
    }
    // return ele, this is the top of stack
    return ele;
}

int main() {
    // Example
    push(1);
    push(2);
    cout<<top()<<endl;
    cout<<pop()<<endl;
    if (empty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    return 0;
}
2
2
false

编号1    参考2