首页 > 试题广场 >

请利用两个栈s1和s2来模拟一个队列。

[问答题]

请利用两个栈s1s2来模拟一个队列。己知栈的三个运算定义如下。PU3H(ST,x):元素xST栈;PoP(ST,x)ST栈项元素出栈,赋给变量xSempty(ST):判ST栈空否。那么如何用栈的运算来实现该队列的三个运算:enqueue:插入一个元素入队列;dequeue:删除一个元素出队列;queue_empty:判队列为空。(请写明算法的思想及必要的注释)

class MyQueue {
    private Stack<Integer> s1 = new Stack<>();//s1 入队的栈
    private Stack<Integer> s2 = new Stack<>();//s2 出队的栈
    //每次入到s1的栈,如果s2不是空的,那么把s2里面的元素全部倒进s1,再入
    public void enqueue(int x){
        if (s1.empty()) {
            while(!s2.empty()){
                s1.push(s2.pop());
            }
        }
        s1.push(x);
    }
    //每次出s2的栈顶元素,如果s2是空的,那么把s1里面的元素全部倒过来s2,再出
    public int dequeue(){
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    public boolean empty(){
        return s1.empty() && s2.empty();
    }
}

发表于 2022-02-27 11:41:06 回复(0)
class MyQueue {
	//初始化两个队列
    private Stack<Integer> s1;//s1入队的栈
    private Stack<Integer> s2;//s2出队的栈
    //入队列指定到s1
    //出队列,每次出s2的栈顶元素,如果s2是空的,那么把s1里面的元素全部倒过来s2,再出
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    public void push(int x){
        s1.push(x);
    }
    public int pop(){
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                int x = s1.pop();
                s2.push(x);
            }
        }
            return s2.pop();
        }
    public int peek(){
            if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                int x = s1.pop();
                s2.push(x);
            }
          }
            return s2.peek();
       }
        
        public boolean empty(){
            return s1.empty() && s2.empty();
        }
    }

发表于 2022-01-09 16:54:55 回复(0)