亲宝软件园·资讯

展开

Java 栈和队列

Word码鸭 人气:0

栈和队列的本质是相同的,都只能在线性表的一端进行插入和删除。因此,栈和队列可以相互转换。

用栈实现队列—力扣232题

题目要求:仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作

使用双栈来实现队列,我们就可以让一个栈储存具体元素,另一个栈做辅助 

上图可以看到,新元素进栈时,要确保该栈为空。进入栈的元素按顺序存到辅助栈中,等新元素进入栈之后,再将辅助栈中的元素按顺序出到该栈中。这样操作之后,栈中元素存放的顺序就和队列的一样啦

代码实现:

 
//双栈模拟队列
public class MyQueue{
    //实际存储元素的栈
    private Stack<Integer> s1 = new Stack<>();
    //辅助栈
    private Stack<Integer> s2 = new Stack<>();
 
    public MyQueue() {
 
    }
 
    //将元素 x 推到队列的末尾
    public void push(int x) {
        if (s1.empty()){//栈为空,直接放入x
            s1.push(x);
        }else {
            //此时不为空
            //先把s1所有元素弹出放入s2
            while (!s1.empty()){
                s2.push(s1.pop());//s2放入的值就是s2弹出的值
                //以下两句和上一句相同
//                int val = s1.pop();
//                s2.push(val);
            }
            //将新元素直接放入s1,此时新元素就处在s1的栈顶
            s1.push(x);
            //再次将s2的所有值依次弹出放入s1
            while (!s2.empty()){
                s1.push(s2.pop());
            }
        }
 
    }
 
    //从队列的开头移除并返回元素
    public int pop() {
       return s1.pop();
    }
 
    //返回队列开头的元素
    public int peek() {
        return s1.peek();
    }
 
    //判断队列是否为空
    public boolean empty() {
        return s1.empty();
    }
}

用队列实现栈—力扣225题 

题目要求:仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作

1. 双队列实现栈

使用双队列实现栈, q1是存储元素的队列,保证q2添加元素之后永远为空队列(新元素直接入q2),保证新元素处在队首。这样的话,新元素入队之后,另外一个队列的元素依次出队然后入队,这样就实现了一个栈。

代码实现:

public class MyStack {
    //q1是存储元素的队列
    private Queue<Integer> q1 = new LinkedList<>();
    //q2是辅助队列
    //添加元素后保证q2永远为空
    private Queue<Integer> q2 = new LinkedList<>();
    public MyStack () {
 
    }
 
    //将元素 x 压入栈顶
    public void push(int x) {
        //新入队元素直接入q2,成为q2队首
        q2.offer(x);
        //将q1中的所有元素依次出队,入q2
        while (!q1.isEmpty()){
            q2.offer(q1.poll());
        }
 
        //q1为空,q2为存储元素的队列,互换引用指向
        //互换之后,q1任然是存储元素的队列,q2为空
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
 
    // 移除并返回栈顶元素
    public int pop() {
        return q1.poll();
    }
 
    //返回栈顶元素
    public int top() {
        return q1.peek();
    }
 
    //判断栈是否为空
    public boolean empty() {
        return q1.isEmpty();
    }
}
 

2.一个队列实现栈

先将元素入队,再将之前的元素依次出队再入队即可!也就是说,保证新元素在队首

代码实现:

public class MyStack {
    private Queue<Integer> queue = new LinkedList<>();
    public MyStack() {
    }
 
    public void push(int x) {
        //记录之前元素的个数
        int size = queue.size();
        //将新元素入队
        queue.offer(x);
        //将之前的元素依次出队再入队,新元素就在队首位置
        for (int i = 0; i < size; i++) {
            queue.offer(queue.poll());
        }
 
    }
 
    public int pop() {
        return queue.poll();
    }
 
    public int top() {
        return queue.peek();
    }
 
    public boolean empty() {
        return queue.isEmpty();
    }
}

这几个例题实践目的是更加熟悉的掌握和了解栈和队列,实际应用中是不推荐的哦。

加载全部内容

相关教程
猜你喜欢
用户评论