栈与队列part01-算法

2023-12-22 22:52:30

栈与队列

今日任务:
● 理论基础
● 232.用栈实现队列
● 225. 用队列实现栈

1.232.用栈实现队列

232. 用栈实现队列

class MyQueue {
    //使用两个栈实现先入先出队列

    //定义两个Stack集合//就已经拥有了这个集合的方法了push pop peek isEmpty等等
    //但是我们这里是实现队列的逻辑
    //用来入栈
    Stack <Integer> stackIn;
    //一个用来出栈
    Stack<Integer> stackOut;
    public MyQueue() {
        //初始化属性
        stackIn=new Stack<>();//负责进栈
        stackOut=new Stack<>();//负责出栈

    }
    
    public void push(int x) {
        //队列的进列操作是直接进
        //栈的入栈操作也是直接进
        stackIn.push(x);
    }
    
    public int pop() {
        //队列出列是先出(先进先出)
        //栈的出栈是后出(先进后出)
        //那么我们现在定义两个栈,一个用来入栈
        //一个用来入栈
        //将入栈的栈的元素一个一个出到作为出栈的栈里面
        //再从这个作为出栈的栈进行取出元素,此时取出的元素就是队列先进先出那个

        //把作为入栈的所有元素都移到作为出栈的那个栈里
        if(stackOut.isEmpty()){
            while(!stackIn.isEmpty()){
            //不为空就一直移到作为出栈的那个栈中
            stackOut.push(stackIn.pop());
            //存进作为出栈的栈里之后,别忘将作为入栈的栈顶元素去除
            //stackIn.pop();//这一步已经不用做了,上一步这样子的已经生效了(不像c)
            }
        }
        //现在作为出栈的栈里头就是队列出列顺序了
        //在进行移除之前,我们先将这个要被移除的元素保存下来,待会进行返回
        int result=stackOut.pop();
        //stackOut.pop();//不需要在移除了,上面那一步已经对集合生效了
        //进行返回
        return result;
    }
    
    public int peek() {
        //返回栈顶元素
        //此时我们应该同作为出栈的顺序是一样的,我们可以对作为出栈那个栈进行调用
        int result=this.pop();
        //但此时这个调用之后我们得将那个被移除的元素重新添加进行,作为返回
        stackOut.push(result);
        return result;
    }
    
    public boolean empty() {
        //获取是不是空,看两个栈是否都是空
        return stackIn.isEmpty()&&stackOut.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

2.225. 用队列实现栈

225. 用队列实现栈

class MyStack {
    //这里思路可以用两个队列实现栈(仿照用两个栈实现队列)//offer poll
    //但我们这里使用一个队列即可
    //入栈跟入队列一样
    //出栈就在队列出来数据之后再将数据入到队列里面
    Queue<Integer> queue;

    public MyStack() {
        //初始化成员属性
        queue=new LinkedList<>();
    }
    
    public void push(int x) {
        //同栈入栈一样
        queue.offer(x);
    }
    
    public int pop() {
        //先将队列的末端(出来的位置取出元素,放在队列的首端(进队列的位置)
        //以什么条件去取元素呢
        //就是我们先获取当前队列的长度,减去一(得到除了最底部不变的元素长度)
        //然后让这个长度去自减,但是要>=0
        int length=queue.size();
        length=length-1;
        //while(length>=0&&length--){
        while(length-->0){
            //取出队列元素,放进入队位置
            queue.offer(queue.poll());
        }
        return queue.poll();
    }
    
    public int top() {
        int result=this.pop();
        queue.offer(result);
        return result;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

文章来源:https://blog.csdn.net/Belle_Daisy/article/details/135161668
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。