Java之栈和队列详解

墨蓝 2023-09-27 14:01 58阅读 0赞

**目录**

一、栈的概念

二、栈的创建与实现方法

1、栈的创建和方法

2、栈的代码实现

3、栈的应用场景

三、队列的概念

四、队列的创建与实现

4.1 队列的创建与方法使用

4.2 队列的方法使用

4.3 队列的模拟实现

五、栈和队列的力扣刷题练习题目

总结：

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

## 一、栈的概念 ##

栈是一种特殊的线性表，只允许在一端进行插入和删除数据。进行数据插入和删除的一段称为栈顶，另一端称为栈底。

栈中数据的插入和删除操作遵循‘“**先进后出**”原则。

![a1108ee0dfe94ab5ae5c1e56142412dc.png][]

**栈在现实生活中的例子：**

在生活中我们可以看到栈的例子，比如手枪子弹匣，最先压入的子弹最后才打出枪口![4a7e531df4a349848fe089dffe95cae4.png][]

羽毛球的球桶也是如此：

![798e416510bc46efb39cb2519db60126.png][]

## 二、栈的创建与实现方法 ##

### 1、栈的创建和方法 ###

在创建和使用栈的过程中，需要创建一个空白的栈，对栈进行数据元素的压栈和出栈操作，判断栈中元素是否为空。由于Java语法已经定义了这些方法，因此我们在写代码时只需要直接调用这些方法即可。

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:center;width:205px;"><strong>方法</strong></td> 
   <td style="text-align:center;width:293px;"><strong>功能</strong></td> 
  </tr> 
  <tr> 
   <td style="width:205px;">Stack（）</td> 
   <td style="width:293px;">创建一个新的空白的栈</td> 
  </tr> 
  <tr> 
   <td style="width:205px;">push（a）</td> 
   <td style="width:293px;">将元素a插入栈中，实现压栈</td> 
  </tr> 
  <tr> 
   <td style="width:205px;">pop（）</td> 
   <td style="width:293px;">将栈顶元素进行出栈</td> 
  </tr> 
  <tr> 
   <td style="width:205px;">peek（）</td> 
   <td style="width:293px;">获取栈顶元素</td> 
  </tr> 
  <tr> 
   <td style="width:205px;">int size()</td> 
   <td style="width:293px;">获取栈中元素的个数</td> 
  </tr> 
  <tr> 
   <td style="width:205px;">boolean&nbsp; emply</td> 
   <td style="width:293px;">判断栈中元素是否为空</td> 
  </tr> 
 </tbody> 
</table>

### 2、栈的代码实现 ###

2.1 创建一个栈并实现压栈

import java.util.Stack;
    public class Test {
        public static void main(String[] args) {
            Stack<Integer> stack = new Stack<>();//创建一个空白的栈
            stack.push(1); //进行压栈
            stack.push(2);
            stack.push(3);
            stack.push(4);
            stack.push(5);
            System.out.println(stack.size());//获取栈中元素个数
        }
    }

2.2 调用出栈和判断栈中元素是否为空的方法

import java.util.Stack;
    public class Test {
        public static void main(String[] args) {
            Stack<Integer> stack = new Stack<>();
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
            stack.push(5);
            System.out.println(stack.size());//---->栈中元素个数为5
            stack.pop();//栈顶元素5出栈，此时栈顶元素为4
            System.out.println(stack.pop());//输出此时出栈元素 --->4
            System.out.println(stack.peek());//获取栈顶元素---->3
            if(stack.empty()){
                System.out.println("空栈");
            }else{
                System.out.println(stack.size());//---->栈中元素个数为3
            }
        }

### 3、栈的应用场景 ###

1.  若进栈序列为  1,2,3,4  ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）答案选C

A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1

2. 一个栈的初始状态为空。现将元素 1 、 2 、 3 、 4 、 5 、 A 、 B 、 C 、 D 、 E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。答案选 B

A: 12345ABCDE B: EDCBA54321 C:12345ABCDE D:ABCDE12345

## 三、队列的概念 ##

**队列** ：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。

入队列：进行插入操作的一端称为 **队尾**  出队列：进行删除操作的一端称为 **队头**

**队列具有“先进先出”的原则。队尾插入数据，队头删除数据。**

![7ec0eb707b4c4b1581c865df8cbed5b4.png][]

## 四、队列的创建与实现 ##

### 4.1 队列的创建与方法使用 ###

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过对线性表的学习了解到常见的空间类型有两种：**顺序结构 和 链式结构**。因为队列存储数据是采用“**先进先出**”原则，如果采用数组的话，对数据进行删除就使用头删，时间复杂度为o(n)，此时队列如果使用链式结构就比较合适。

![701dc4c758754633a6d9af203acfd011.png][]

### 4.2 队列的方法使用 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:206px;"><strong>方法</strong></td> 
   <td style="width:292px;"><strong>功能</strong></td> 
  </tr> 
  <tr> 
   <td style="width:206px;">E.offer(e)</td> 
   <td style="width:292px;">将数据元素e入队列</td> 
  </tr> 
  <tr> 
   <td style="width:206px;">E.poll()</td> 
   <td style="width:292px;">删除队首元素，将队首元素出队列</td> 
  </tr> 
  <tr> 
   <td style="width:206px;">peek()</td> 
   <td style="width:292px;">获取队首元素</td> 
  </tr> 
  <tr> 
   <td style="width:206px;">E.size()</td> 
   <td style="width:292px;">获取队列的元素个数</td> 
  </tr> 
  <tr> 
   <td style="width:206px;">boolean isEmpty()</td> 
   <td style="width:292px;">判断队列是否为空</td> 
  </tr> 
 </tbody> 
</table>

import java.util.LinkedList;
    public class Demo {
        public static void main(String[] args) {
            LinkedList<Integer> quene = new LinkedList<>();//采用链表来实例化一个新的队列
            quene.offer(1);//入队列
            quene.offer(2);
            quene.offer(3);
            quene.offer(4);
            quene.offer(5);
            System.out.println(quene.size());//---->队列中数据元素个数有5个
            quene.poll();//元素1出队列
            Integer a = quene.peek();//获取队列的队首，此时队首为2
            System.out.println(a);//----->2
            if(quene.isEmpty()){
                System.out.println("队列空");
            }else{
                System.out.println(quene.size());//---->4
            }
        }
    }

### 4.3 队列的模拟实现 ###

队列的模拟实现可采用顺序结构或者链式结构，上面我们已经说过队列采用链式结构比顺序结构效果较好，因此我们这里用双向链表来模拟实现队列。

####  ####

4.3.1 双向链表的创建

public class Quene {
      /*
      创建一个双向链表*/
        public static  class ListNode{
            public int value;
            ListNode next;
            ListNode prev;
            public ListNode(int value) {
                this.value = value;
            }
            ListNode head; //定义队列的队头
            ListNode font; //定义队列的队尾
            int usesize = 0; //定义队列的数据元素个数
        }
    }

4.3.2 队列的入队

// 队列的入队
          public void offer(int e){
              ListNode listNode = new ListNode(e);
              if(first == null){ //队列为空时，队列的队头和队尾都为新节点
                  first = listNode;
                  last = listNode;
              }else{
                  last.prev=listNode; //队列非空时，新节点为队尾
                  listNode.next = last;
                  last=listNode;
              }
              usesize++;
          }

4.3.3 队列的出队

// 队列的出队
           public int poll(){
              /*队列出队有以下情况：
                1、队列为空时
                2、队列只有一个元素
                3、队列有多个元素时*/
               int a=0;
               if(first == null){
                   System.out.println("队列为空");
                   return -1;
               } else if (first == last){
                   first = null;
                   last = null;
               }else {
                   a = first.value;
                   first=first.next;//删除队首节点，队首节点后移一个
                  first.prev.next=null;
                  first.prev=null;
                }
               usesize--;
               return a;
               }

4.3.4 获取队首value值

// 获取队首value值
          public int peek(){
              if(first == null){
                  System.out.println("队列为空");
                  return -1;
              }else{
                return first.value;
              }
          }

4.3.5 双向链表模拟实现队列的完整代码

public class Quene {
      /*
      创建一个双向链表*/
        public static  class ListNode{
            public int value;
            ListNode next;
            ListNode prev;
            public ListNode(int value) {
                this.value = value;
            }
            ListNode first; //定义队列的队头
            ListNode last; //定义队列的队尾
            int usesize = 0; //定义队列的数据元素个数
    
          // 队列的入队
          public void offer(int e){
              ListNode listNode = new ListNode(e);
              if(first == null){ //队列为空时，队列的队头和队尾都为新节点
                  first = listNode;
                  last = listNode;
              }else{
                  last.prev=listNode; //队列非空时，新节点为队尾
                  listNode.next = last;
                  last=listNode;
              }
              usesize++;
          }
          // 队列的出队
           public int poll(){
              /*队列出队有以下情况：
                1、队列为空时
                2、队列只有一个元素
                3、队列有多个元素时*/
               int a=0;
               if(first == null){
                   System.out.println("队列为空");
                   return -1;
               } else if (first == last){
                   first = null;
                   last = null;
               }else {
                   a = first.value;
                   first=first.next;//删除队首节点，队首节点后移一个
                  first.prev.next=null;
                  first.prev=null;
                }
               usesize--;
               return a;
               }
               // 获取队首value值
          public int peek(){
              if(first == null){
                  System.out.println("队列为空");
                  return -1;
              }else{
                return first.value;
              }
          }
          }
        }

## 五、栈和队列的力扣刷题练习题目 ##

**（1）** **[有效的括号匹配][Link 1]**

**（2）** **[最小栈][Link 2]**

**（3）[用队列实现栈][Link 3]**

**（4）[用栈实现队列][Link 4]**

##  ##

## 总结： ##

**栈和队列是数据结构知识的基础知识，因此我们在学习数据结构的时候需要牢牢记住栈和队列的实现原理以及如何去调用他们各自对应的方法，大家在学习栈和队列的时候可以多敲敲代码来加深理解**

[a1108ee0dfe94ab5ae5c1e56142412dc.png]: https://img-blog.csdnimg.cn/a1108ee0dfe94ab5ae5c1e56142412dc.png
[4a7e531df4a349848fe089dffe95cae4.png]: https://img-blog.csdnimg.cn/4a7e531df4a349848fe089dffe95cae4.png
[798e416510bc46efb39cb2519db60126.png]: https://img-blog.csdnimg.cn/798e416510bc46efb39cb2519db60126.png
[7ec0eb707b4c4b1581c865df8cbed5b4.png]: https://img-blog.csdnimg.cn/7ec0eb707b4c4b1581c865df8cbed5b4.png
[701dc4c758754633a6d9af203acfd011.png]: https://img-blog.csdnimg.cn/701dc4c758754633a6d9af203acfd011.png
[Link 1]: https://leetcode.cn/problems/valid-parentheses/
[Link 2]: https://leetcode.cn/problems/min-stack/
[Link 3]: https://leetcode.cn/problems/implement-stack-using-queues/
[Link 4]: https://leetcode.cn/problems/implement-queue-using-stacks/