笔试常考: 队列实现栈 and 栈实现队列 and 验证栈序列

超、凢脫俗 2024-03-25 23:47 38阅读 0赞

**目录**

一.浅谈栈和队列

1.栈

2.队列

二.Java中的栈和队列

1.Java中的栈

2.Java中的队列

3.双端队列

1.LinkedList

2.ArrayDeque

三.队列来实现栈

1.双队列实现栈

1.问题分析

2.代码实现

2.单队列实现栈

1.问题分析

2.代码实现

四.栈实现队列

1.双栈实现队列

1.问题分析

2.代码实现

五.验证栈序列

1.题目描述

2.问题分析

3.代码实现

--------------------

## 一.浅谈栈和队列 ##

### 1.栈 ###

我们都熟知栈是一种**先进后出**的数据结构,数据只能从一段进入,从这一段出去

如下图就是抽象的栈结构,数据只能从右端进入,从右端出去,例如只能弹出5(也就是最后插入的元素),要进入6元素,只能在5的后面

![0a6c5ec894ef4f46ba4c3ff38f8d0d3a.png][]

### 2.队列 ###

我们都熟知队列是一种**先进后出**的数据结构,数据从一段进出,并从另一端出去

如下图就是抽象的队列结构,数据只能从左端出,从右端进入,例如只能先弹出1(也就是最先进入队列的元素),也只能在右端插入新数据6

![83fa5c299d704f2688403d62a1c46076.png][]

## 二.Java中的栈和队列 ##

### 1.Java中的栈 ###

Java API中有专门的栈的API,如图,但是这个类用来实现栈的效率十分低,因为Vector是一个线程安全的类,因此在具体的使用中,我们不建议创建Stack的对象.推荐的我们放在了第三个:**双端队列**

![515d221209ed45afa0af8147aaaf5ccf.png][]

### 2.Java中的队列 ###

Java中没有命名为Queue的类,但是相应的接口,我们不可以直接创建Queue的对象,因为Queue是接口不是类,但是有实现Queue接口的队列,**具体看第三个:双端队列**

![35961303226d4cc0aca2f3d63e8298a3.png][]

### 3.双端队列 ###

双端队列虽然叫队列,但他同样也可以实现栈的功能,因此一种API既可以实现栈,也可以实现队列,都有具体的实现方法

我们都知道队列和栈有两种实现的方式,**线性表(数组)和链表**,同样的双端队列也有两种实现的方式

#### 1.LinkedList ####

LinkedList底层使用**链表**来实现的,现在我们来具体介绍一下实现队列和栈的功能的API

![2acdfccbde214a66b7dbd1fefeee6931.png][]

**栈**

>     LinkedList<Integer> stack = new LinkedList<>();
>     stack.push(1);
>     stack.push(2);
>     stack.push(3);
>     stack.push(4);
>     System.out.println(stack);//[4, 3, 2, 1]
>     System.out.println(stack.pop());//4
>     System.out.println(stack.peek());//3

从以上方法可以看出,LinkedList的确可以实现栈的功能,只需要使用push和pop方法即可

**队列**

>     LinkedList<Integer> queue = new LinkedList<>();
>     queue.offer(1);
>     queue.offer(2);
>     queue.offer(3);
>     queue.offer(4);
>     System.out.println(queue);//[1, 2, 3, 4]
>     System.out.println(queue.poll());//1
>     System.out.println(queue.peek());//2

从以上方法可以看出,LinkedList的确可以实现队列的功能,只需要使用offer和poll方法即可

**总结: 按我的理解就是当执行offer方法的时候,就是在链表的尾部插入数据,执行push方法的时候,就是在链表的头部插入数据,当执行poll方法的时候,就是在链表的头部删除数据,执行pop方法的时候,就是在链表的尾部删除数据,peek方法就是取出链表头部的数据,我们可以使用peekLast取出链表尾部的数据**

#### 2.ArrayDeque ####

LinkedList底层使用**数组**来实现的,现在我们来具体介绍一下实现队列和栈的功能的API

![8d038f16401c4be9a0b11d5258e05eb9.png][]

具体方法调用和LinkedList一模一样,只是new对象不同,这里不做更多的介绍

>     ArrayDeque<Integer> queue = new ArrayDeque<>();

## 三.队列来实现栈 ##

力扣上专门的题目,在这里可以作参考:[力扣][Link 1]

### 1.双队列实现栈 ###

#### 1.问题分析 ####

我们都知道栈最后入栈的元素最先出栈,而队列最先入栈的元素最后出栈.

用队列来实现栈,我们需要考虑的就是如何将最先入队列的元素置入队列的尾端,最后入队列的元素置入队列的首端(正好符合栈的出栈序列),也就是说原本的\{1,2,3,4\}顺序,现在需要以\{4,3,2,1\}顺序存储到队列中.我们可以用双队列来执行

*  将元素1入队列![9ddcdcd1206140328cf20c4623be947d.png][]
 *  将元素2入队列![dd99335e3567417899dcad2f6e0677b7.png][]

![084c5ee39e1442e5bec82697dfb15bcc.png][]

*  将元素3入队列

![e4a575fa446e4d8c9ac02b1af182b59c.png][]

![99c9f2271fe34b7b969d8b6c13193850.png][]

*  将元素4入队列

![18e1d831c09c433fb03da3ef141fabdb.png][]

![0966a726afc64ecc9b1431fcd93856aa.png][]

以上便可以用双队列达到了栈的效果,但是我们这样每次数据保存的在队列的位置不确定,我们不妨每次将queue1和queue2的引用进行交换,使得每次queue1引用指向的队列就是我们存放数据的队列.

#### 2.代码实现 ####

class MyStack {
        //存储元素的队列
         private LinkedList<Integer> queue1 = new LinkedList<>();
         //辅助队列
         private LinkedList<Integer> queue2 = new LinkedList<>();
    
        public MyStack() {
    
        }
    
        public void push(int x) {
            queue2.offer(x);
            while(!empty()){
             queue2.offer(queue1.pop());   
            }
            LinkedList<Integer> temp=queue1;
            queue1=queue2;
            queue2=temp;
          
        }
    
        public int pop() {
            if (empty()) {
                return -1;
            }
            return queue1.poll();
        }
    
        public int top() {
            if (empty()) {
                return -1;
            }
            return queue1.peek();
        }
    
        public boolean empty() {
            return queue1.isEmpty();
        }
    
    }

### 2.单队列实现栈 ###

#### 1.问题分析 ####

经历了上面的双队列实现栈,我们其实可以很容易的想到如何使用单队列实现栈的功能,我们只需要每次入队列指定的元素,然后将队列之前的元素重新入队列,便可以实现栈的功能,接下来看演示

*  将元素1入队列![2d228b86a7174b329729fda0c9c3af26.png][]
 *  将元素2入队列![ce7f67396ac34d329396e3ac9d04b9ca.png][]![6929435e030644b1af9e4ccf3c597d8f.png][]
 *  将元素3入队列![ce3a493277834626a58e8c64de06fd7e.png][]![353df98674c549aba34b9ce5e0c8c8b5.png][]
 *  将元素4入队列![1c1a953928b54155a8d267cb65e611a7.png][]

![e001e038860e43028ec97547715490d9.png][]

#### 2.代码实现 ####

class MyStack {
        private LinkedList<Integer> queue = new LinkedList<>();
        public MyStack() {
    
        }
        
        public void push(int x) {
            queue.offer(x);
            int size=queue.size();
            for(int i=0;i<size-1;++i){
                queue.offer(queue.poll());
            }
    
    
        }
        
        public int pop() {
            return queue.poll();
    
        }
        
        public int top() {
           return queue.peek();
        }
        
        public boolean empty() {
           return queue.size()==0;
        }
    }

## 四.栈实现队列 ##

力扣上专门的题目,在这里可以作参考:[力扣][Link 2]

### 1.双栈实现队列 ###

#### 1.问题分析 ####

可能很多人会想单队列能够实现栈,单栈一定也能够实现队列,其实我们只能用双栈来实现队列,这是因为栈的特殊性,所以我们这里来讨论双栈实现队列的思路

因为队列的先进先出的,所以这里栈一定要把先进的元素放在栈的顶部,这样才能够满足队列的结构,也就是说我们要把栈的结构倒转过来,这时候一定需要另一个栈的辅助,比如入栈的顺序为\{1,2,3,4\},这个时候放入到栈中的顺序应该为\{4,3,2,1\},这样出栈的顺序满足出队列的先进先出的原则.接下里我们使用演示的方式看看如何实现这个功能

*  将元素1入队列![fc77d0a670624d9a85b3122eccc452a7.png][]
 *  将元素2入队列![3fe7a04917a54486a28becd96d90411f.png][]![5de24db152334dfca5d2833779ecdbc4.png][]![a86b11e213854a6ca5bab59f3a5dca96.png][]
 *  将元素3入队列![98bb2508dcf4465485c27dbf019f4f34.png][]![0abb88d8cbd343a783ac457c6ee22a1b.png][]![220064c3dad242f48b9d3c8b43dbc842.png][]
 *  将元素4入队列

![aedce173c34d4985809c532fa119b4ad.png][]

![6605545399614607914468feb3874cef.png][] ![5371ba00671c4c9589e6845cdc904bfe.png][]

#### 2.代码实现 ####

class MyQueue {
        LinkedList<Integer> stack1=new LinkedList<>();
        LinkedList<Integer> stack2=new LinkedList<>();
    
    
        public MyQueue() {
    
        }
    
        public void push(int x) {
           while(!stack1.isEmpty()){
               stack2.push(stack1.pop());
           }
           stack1.push(x);
           while(!stack2.isEmpty()){
               stack1.push(stack2.pop());
           }
    
        }
    
        public int pop() {
            int val=stack1.pop();
            return val;
        }
    
        public int peek() {        
         return stack1.peek();
        }
    
        public boolean empty() {
            return stack1.isEmpty();
    
        }
    }

## 五.验证栈序列 ##

### 1.题目描述 ###

> 给定 `pushed` 和 `popped` 两个序列，每个序列中的 **值都不重复**，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 `true`；否则，返回 `false` 。

力扣:[力扣][Link 3]

### 2.问题分析 ###

对于一个序列,因为我们可以在入栈的同时进栈,所以出栈的可以有多种顺序,例如对A,B,C,D入栈,出栈的顺序不一定是D,C,B,A,因为随时可以出栈,比如入栈一个出栈一个,出栈的顺序就为:A,B,C,D

因此判断是否为栈序列,我们判断栈顶元素是否为popped的元素,如果不是将pushed的元素进行入栈,直到栈顶元素为popped的元素,然后对入栈的pushed元素依次进行出栈,直到栈顶的元素不为popped的出栈序列

### 3.代码实现 ###

public boolean validateStackSequences(int[] pushed, int[] popped) {
            LinkedList<Integer> stack = new LinkedList<>();
            int i=0;
            for(int val:pushed){
                stack.push(val);
                while(!stack.isEmpty()&&stack.peek()==popped[i]){
                    stack.pop();
                    i++;
                }
            }
            return stack.isEmpty();
    
        }

[0a6c5ec894ef4f46ba4c3ff38f8d0d3a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/08ec18fd53fc4aae9d8614a78b067975.png
[83fa5c299d704f2688403d62a1c46076.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/cfcf6dc2990c45d383dac6444dc11d93.png
[515d221209ed45afa0af8147aaaf5ccf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f5845e90de6c4848b306137f1e98b515.png
[35961303226d4cc0aca2f3d63e8298a3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/468e2fc8f68248c48343b571f84863e8.png
[2acdfccbde214a66b7dbd1fefeee6931.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/147bf3ce6bfb46c8ba5660e887855c21.png
[8d038f16401c4be9a0b11d5258e05eb9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/343e5881c6a5476280f2b01b98fb85f4.png
[Link 1]: https://leetcode.cn/problems/implement-stack-using-queues/
[9ddcdcd1206140328cf20c4623be947d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8d171c5575bd4629a60a0221e707d6c8.png
[dd99335e3567417899dcad2f6e0677b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/311b1a0de2ca48f9ae2740a33f3a00ec.png
[084c5ee39e1442e5bec82697dfb15bcc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/376cb00ebd4c4aa9a5d413e5a7b8ae8f.png
[e4a575fa446e4d8c9ac02b1af182b59c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a4a48b9301ff445c982821fd77b17027.png
[99c9f2271fe34b7b969d8b6c13193850.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/75bfd8805733424a86b43588515a115f.png
[18e1d831c09c433fb03da3ef141fabdb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b650979f8bca44f09bd6b5d8269c2825.png
[0966a726afc64ecc9b1431fcd93856aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e745fdabb6c7467a82878b5e4148c39d.png
[2d228b86a7174b329729fda0c9c3af26.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0c44f5fd7b2b41c68b48e87398c5f4ad.png
[ce7f67396ac34d329396e3ac9d04b9ca.png]: https://img-blog.csdnimg.cn/ce7f67396ac34d329396e3ac9d04b9ca.png
[6929435e030644b1af9e4ccf3c597d8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/20ea18e2542a4e48ae06ecb6dec9c848.png
[ce3a493277834626a58e8c64de06fd7e.png]: https://img-blog.csdnimg.cn/ce3a493277834626a58e8c64de06fd7e.png
[353df98674c549aba34b9ce5e0c8c8b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a447847232a94314a93a3d829a2814eb.png
[1c1a953928b54155a8d267cb65e611a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0b32ad2abb2e464a884393f3095b0481.png
[e001e038860e43028ec97547715490d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/21daf7ab365c47a298e14816cdafd914.png
[Link 2]: https://leetcode.cn/problems/implement-queue-using-stacks/
[fc77d0a670624d9a85b3122eccc452a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7b4760930b464724a118606fbf6dc79c.png
[3fe7a04917a54486a28becd96d90411f.png]: https://img-blog.csdnimg.cn/3fe7a04917a54486a28becd96d90411f.png
[5de24db152334dfca5d2833779ecdbc4.png]: https://img-blog.csdnimg.cn/5de24db152334dfca5d2833779ecdbc4.png
[a86b11e213854a6ca5bab59f3a5dca96.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b1d1e8b7356d454290a7887097ce3931.png
[98bb2508dcf4465485c27dbf019f4f34.png]: https://img-blog.csdnimg.cn/98bb2508dcf4465485c27dbf019f4f34.png
[0abb88d8cbd343a783ac457c6ee22a1b.png]: https://img-blog.csdnimg.cn/0abb88d8cbd343a783ac457c6ee22a1b.png
[220064c3dad242f48b9d3c8b43dbc842.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2789841cf74d4e6e811b8ac6fcc4f61c.png
[aedce173c34d4985809c532fa119b4ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/dc9efa7b7ba44d6fa7404c270e19c01e.png
[6605545399614607914468feb3874cef.png]: https://img-blog.csdnimg.cn/6605545399614607914468feb3874cef.png
[5371ba00671c4c9589e6845cdc904bfe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/099822bb372b41179a0ee9a0e191830b.png
[Link 3]: https://leetcode.cn/problems/validate-stack-sequences/