【数据结构】学习了栈和队列，那么如何用栈实现队列，用队列实现栈的功能呢？

超、凢脫俗 2023-10-04 18:35 29阅读 0赞

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

`大家好，我是卷心菜，可以叫我菜菜，大二学生一枚。本篇主要讲解数据结构：栈、队列以及两者之间的转换。如果您看完文章有所收获，可以三连支持博主哦~，嘻嘻。`

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

#### 文章目录 ####

*  一、什么是栈
 *   *  1、基本概念
     *  2、栈的模型
 *  二、什么是队列
 *   *  1、基本概念
     *  2、队列的模型
 *  三、用队列实现栈
 *  四、用栈实现队列

## 一、什么是栈 ##

### 1、基本概念 ###

*  `栈`，我们可以理解为妈妈做的韭菜饼，先做好一块，然后又做好一块放到上一个韭菜饼的上面，直到摊完所有的韭菜饼。我们就可以清楚的知道，妈妈先摊好的韭菜饼在最底下，按照顺序吃，只能先吃最后摊完的韭菜饼。`“先摊完的饼最后吃，最后摊完的饼先吃”`，引入到数据结构，就是我们经常说的入栈和出栈。

![在这里插入图片描述][52c3a23189464839abfd07db6b4ca0fe.png_pic_center]

*  栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
 *  栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（push），删除则称为退栈（pop）。栈也称为先进后出表。
 *  栈可以用来在函数调用的时候存储断点，我们在使用递归的时候，就用到了栈~

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

### 2、栈的模型 ###

![在这里插入图片描述][c2326f9ace424dd78293dc5dcf54ca56.png]

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

## 二、什么是队列 ##

### 1、基本概念 ###

*  `“队列”`，我们可以把队列比作一个教室，教室有一个规定：进了教室必须学够5个小时，到了5个小时，必须离开。也就是说，先进教室的人一定先学够5个小时，也一定先出教室。引入到数据结构，就是大家通常所说的入队列和出队列。

![在这里插入图片描述][361922b984ec4d94b9ef2e48d0833dd0.png_pic_center]

*  跟栈一样，队列也是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
 *  队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

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

### 2、队列的模型 ###

![在这里插入图片描述][9611061600c24ebbbeb9947c0436d341.png]

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

## 三、用队列实现栈 ##

为了讲解用队列实现栈的功能，就从这道力扣题开始：  
![在这里插入图片描述][80f45625efc14709bbd06e7c64595947.png]  
在前面的讲解中，我们知道，栈是先进后出，队列是先进先出，该如何实现功能的转换呢？看代码，我们不用两个队列，用一个队列就可以实现：

public class One {
        
        Queue<Integer> q1 = null;
        //用LinkedList模拟队列，它符合先进先出的队列
        public One() {
        
            q1 = new LinkedList<>();
        }
        public void push(int x) {
        
        	//在将 x 放入队列之前，先计算队列中有多少个元素
            int n = q1.size();
            //offer()方法就相当于入队列
            q1.offer(x);
            for (int i = 0; i < n; i++) {
        
            	//poll()相当于将队列头的元素取走
                q1.offer(q1.poll());
            }
        }
        public int pop() {
        
        	//poll()取走队列的第一个元素
            return q1.poll();
        }
        public int top() {
        
        	//peek()查看队列的第一个元素，但是不移除
            return q1.peek();
        }
        public boolean empty() {
        
        	//查看队列中是否为空
            return q1.isEmpty();
        }

图片显示一下元素入队列的整个过程：  
![在这里插入图片描述][a15b9caedc524e83b8a95424ca33d0ca.png]

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

## 四、用栈实现队列 ##

还是老方法，我依旧从看一道力扣题开始实现这个功能：  
![在这里插入图片描述][dad47256b1134727a8e75ee4d9d02fe8.png]  
从代码中分析整个过程：

public class Two {
        
    	//这里我用到了两个栈
        public Stack<Integer> s1 = null;
        public Stack<Integer> s2 = null;
        public Two() {
        
            s1 = new Stack<>();
            s2 = new Stack<>();
        }
        //只要你给我s1这个栈放入元素，我就要
        public void push(int x) {
        
            s1.push(x);
        }
        //当我栈s2空了的时候，我再从栈s1中拿走所有的元素放入栈s2中，从而实现了栈转队列
        public int pop() {
        
        	//这里一定要判断栈s2是不是空的，不是空的就不能让其它元素入栈
            if (s2.isEmpty()) {
        
                while (!s1.isEmpty()) {
        
                    s2.push(s1.pop());
                }
            }
            return s2.pop();
        }
        public int peek() {
        
            if (s2.isEmpty()) {
        
                while (!s1.isEmpty()) {
        
                    s2.push(s1.pop());
                }
            }
            return s2.peek();
        }
        public boolean empty() {
        
            if (s1.isEmpty() && s2.isEmpty())
                return true;
            return false;
        }
    }

图片显示一下元素出栈的整个过程：

![在这里插入图片描述][e31225d3047940e591097d1e483ad682.png]

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

`感谢阅读，一起进步，嘻嘻~`

[52c3a23189464839abfd07db6b4ca0fe.png_pic_center]: https://img-blog.csdnimg.cn/52c3a23189464839abfd07db6b4ca0fe.png#pic_center
[c2326f9ace424dd78293dc5dcf54ca56.png]: https://img-blog.csdnimg.cn/c2326f9ace424dd78293dc5dcf54ca56.png
[361922b984ec4d94b9ef2e48d0833dd0.png_pic_center]: https://img-blog.csdnimg.cn/361922b984ec4d94b9ef2e48d0833dd0.png#pic_center
[9611061600c24ebbbeb9947c0436d341.png]: https://img-blog.csdnimg.cn/9611061600c24ebbbeb9947c0436d341.png
[80f45625efc14709bbd06e7c64595947.png]: https://img-blog.csdnimg.cn/80f45625efc14709bbd06e7c64595947.png
[a15b9caedc524e83b8a95424ca33d0ca.png]: https://img-blog.csdnimg.cn/a15b9caedc524e83b8a95424ca33d0ca.png
[dad47256b1134727a8e75ee4d9d02fe8.png]: https://img-blog.csdnimg.cn/dad47256b1134727a8e75ee4d9d02fe8.png
[e31225d3047940e591097d1e483ad682.png]: https://img-blog.csdnimg.cn/e31225d3047940e591097d1e483ad682.png