边学边记——Java数据结构☞栈和队列

落日映苍穹つ 2023-09-30 16:05 38阅读 0赞

**目录**

一.栈（stack）

1.概念

(1).定义

(2).特点

(3).操作

2.使用

3.栈的模拟实现

4.概念区分（栈，虚拟机栈，栈帧）

二.队列（queue）

1.概念

(1).定义

(2).特点

(3).操作

2.使用

3.注意

4.Deque（接口）——双端队列

5.模拟实现

(1).单链表队列的模拟实现

(2).循环队列的模拟实现

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

> Java中的栈和队列——java.util.\*包下定义的。

## 一.栈（stack） ##

### 1.概念 ###

#### (1).定义 ####

> 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

#### (2).特点 ####

> 先进后出（后进先出）——栈中的数据元素遵守先进后出（后进先出：LIFO Last In First Out）的原则。

#### (3).操作 ####

*  元素入栈的过程——压栈（push）
 *  元素出栈的过程——弹栈/弹出（pop）
 *  观察栈顶元素是什么，但是不改变栈的结构——peek（偷偷看的意思）

### 2.使用 ###

![3082013a2f9d4c818f49ca4cf4c3af5b.png][]

<table> 
 <tbody> 
  <tr> 
   <td><strong>方法</strong></td> 
   <td><strong>功能</strong></td> 
  </tr> 
  <tr> 
   <td>Stack()</td> 
   <td>构造一个空的栈</td> 
  </tr> 
  <tr> 
   <td>E push(E e)</td> 
   <td>将e入栈，并返回e</td> 
  </tr> 
  <tr> 
   <td>E pop()</td> 
   <td>将栈顶元素出栈并返回</td> 
  </tr> 
  <tr> 
   <td>E peek()</td> 
   <td>获取栈顶元素</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>获取栈中有效元素个数</td> 
  </tr> 
  <tr> 
   <td>boolean empty()</td> 
   <td>检测栈是否为空</td> 
  </tr> 
 </tbody> 
</table>

### 3.栈的模拟实现 ###

//元素类型固定为long类型
    //使用数组（顺序表）实现栈
    //使用尾插：压栈
    //使用尾删：弹栈
    //不考虑扩容问题
    public class MyStack {
        private final long[] array=new long[100];
        private int size=0;
    
        public int size(){
            return size;
        }
    
        public boolean isEmpty(){
            return size()==0;
        }
    
        //入栈，压栈
        public void push(long x){
            array[size++]=x;
        }
    
        //出栈
        public long pop(){
            if(isEmpty()){
                throw new RuntimeException("栈是空的");
            }
            return array[--size];
        }
    
        //查看栈顶元素
        public long peek(){
            if(isEmpty()){
                throw new RuntimeException("栈是空的");
            }
            return array[size-1];
        }
    
        public static void main(String[] args) {
            //测试
            MyStack stack=new MyStack();
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
            System.out.println(stack.peek());   //4
            stack.pop();
            System.out.println(stack.peek());   //3
        }
    }

### 4.概念区分（栈，虚拟机栈，栈帧） ###

*  栈：结构，是一种理论。
 *  虚拟机栈（有时候也简称为 栈）：使用栈这种理论，在虚拟机中记录方法调用时的数据。
 *  栈帧（frame）：是用来支持虚拟机进行方法调用和方法执行的数据结构，它是虚拟机运行时数据区中的虚拟机栈的栈元素。

**这里整理了几道关于栈的题目，可以配合练习：**

[LeetCode20.有效的括号][LeetCode20.]

[LeetCode150.逆波兰表达式求值][LeetCode150.]

[牛客网JZ31.栈的压入，弹出序列][JZ31.]

## 二.队列（queue） ##

### 1.概念 ###

#### (1).定义 ####

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

#### (2).特点 ####

> 队列遵守先进先出（FIFO——First In First Out) 的原则。

#### (3).操作 ####

*  将元素放入队列——入队列（offer）
 *  将元素从队列取出——出队列（poll）
 *  查看队首元素但不改变结构——peek

### 2.使用 ###

Java中，队列的含义被泛化了。——java.util.Queue 接口

![0df2d84225d54bedbae3600e3ab1cfec.png][]

<table> 
 <tbody> 
  <tr> 
   <td><strong>方法</strong></td> 
   <td><strong>功能</strong></td> 
  </tr> 
  <tr> 
   <td>boolean offer(E e)</td> 
   <td>入队列</td> 
  </tr> 
  <tr> 
   <td>E poll()</td> 
   <td>出队列</td> 
  </tr> 
  <tr> 
   <td>peek()</td> 
   <td>获取队头元素</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>获取队列中有效元素个数</td> 
  </tr> 
  <tr> 
   <td>boolean isEmpty()</td> 
   <td>检测队列是否为空</td> 
  </tr> 
 </tbody> 
</table>

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

### 3.注意 ###

队列的方法：注意区别，一般我们使用offer(e)，poll()，peek()。

![5b8a2e70e35e45d796e04f7226fef567.png][]

### 4.Deque（接口）——双端队列 ###

> Deque（接口）——双端队列，不允许中间插入和删除元素，允许从两头分别进出。

Deque=Stack+Queue

java.util.Deque 接口既可以当队列使，也可以当栈使。

其继承自java.util.Queue。

![71fd31ba121f4eae99ac28651249a5f2.png][]

### 5.模拟实现 ###

#### (1).单链表队列的模拟实现 ####

import java.util.Queue;
    
    //元素类型是long类型
    public class MyQueue {
        static class Node{
            long value;
            Node next;
    
            Node(long value){
                this.value=value;
                this.next=null;
            }
        }
    
        private Node head;
        private Node last;
        private int size;
    
        public MyQueue() {
            this.head =this.last =null;
            this.size = 0;
        }
    
        //入队列
        public void offer(long e){
            Node node=new Node(e);
            if(this.last!=null){
                this.last.next=node;
                this.last=node;
            }else {
                this.head=this.last=node;
            }
            this.size++;
        }
    
        //出队列
        public long poll(){
            if(size==0){
                throw new RuntimeException("队列是空的");
            }
    
            long e=this.head.value;
            this.head=this.head.next;
            if(this.head==null){
                this.last=null;
            }
            size--;
            return e;
        }
    
        //查看队头元素
        public long peek(){
            if(size==0){
                throw new RuntimeException("队列是空的");
            }
            return this.head.value;
        }
    
        public int size(){
            return this.size;
        }
    
        public boolean isEmpty(){
            return size()!=0;
        }
    
        public static void main(String[] args) {
            //测试
            MyQueue queue = new MyQueue();
    
            queue.offer(1);
            queue.offer(2);
            queue.offer(3);
            queue.offer(4);
    
            System.out.println(queue.peek());   // 1
            queue.offer(5);
    
            System.out.println(queue.peek());   // 1
    
            System.out.println(queue.poll());   // 1
            System.out.println(queue.poll());   // 2
            System.out.println(queue.poll());   // 3
            System.out.println(queue.poll());   // 4
            System.out.println(queue.poll());   // 5
    
            queue.offer(6);
            System.out.println(queue.peek());   // 6
            System.out.println(queue.poll());   // 6
        }
    
    }

#### (2).循环队列的模拟实现 ####

![05dc7ec7fdf345829bef679514aa9b50.png][]

public class MyCircularQueue {
        private int[] array;
        private int size;
        private int headIndex;
        private int lastIndex;
    
        public MyCircularQueue(int k) {
            this.array=new int[k];
            this.size = 0;
            this.headIndex=0;
            this.lastIndex=0;
        }
    
        public boolean isEmpty(){
            return size==0;
        }
    
        public boolean isFull(){
            return size==array.length;
        }
    
        //尾插
        public boolean enQueue(int value){
            if(isFull()){
                return false;
            }
    
            array[lastIndex]=value;
            lastIndex=(lastIndex+1)%array.length;
            size++;
    
            return true;
        }
    
        //头删
        public boolean deQueue(){
            if(isEmpty()){
                return false;
            }
    
            headIndex+=1;
            if(headIndex==array.length){
                headIndex=0;
            }
            size--;
    
            return true;
        }
    
        //查看队头元素
        public int Front(){
            if(isEmpty()){
                return -1;
            }
            return array[headIndex];
        }
    
        //查看队尾元素
        public int Rear(){
            if(isEmpty()){
                return -1;
            }
            int index=lastIndex;
            index=(index-1+array.length)%array.length;
            return array[index];
        }
    
        //断言检测
        private static void assertTrue(boolean condition) {
            if (!condition) {
                throw new RuntimeException("断言失败");
            }
        }
    
        public static void main(String[] args) {
            MyCircularQueue q = new MyCircularQueue(6);
            assertTrue(q.enQueue(6));
            assertTrue(q.Rear() == 6);
            assertTrue(q.Rear() == 6);
            assertTrue(q.deQueue());
            assertTrue(q.enQueue(5));
            assertTrue(q.Rear() == 5);
            assertTrue(q.deQueue());
            assertTrue(q.Front() == -1);
            assertTrue(!q.deQueue());
            assertTrue(!q.deQueue());
            assertTrue(!q.deQueue());
    
            q.enQueue(4);
            q.enQueue(3);
            q.enQueue(2);
            q.enQueue(1);
            q.enQueue(0);
            q.enQueue(-1);
        }
    }

如有建议或想法，欢迎一起讨论学习~

[3082013a2f9d4c818f49ca4cf4c3af5b.png]: https://img-blog.csdnimg.cn/3082013a2f9d4c818f49ca4cf4c3af5b.png
[LeetCode20.]: https://blog.csdn.net/lil_ghost_/article/details/127411652?spm=1001.2014.3001.5501
[LeetCode150.]: https://blog.csdn.net/lil_ghost_/article/details/127412194?spm=1001.2014.3001.5501
[JZ31.]: https://blog.csdn.net/lil_ghost_/article/details/127412808?spm=1001.2014.3001.5501
[0df2d84225d54bedbae3600e3ab1cfec.png]: https://img-blog.csdnimg.cn/0df2d84225d54bedbae3600e3ab1cfec.png
[5b8a2e70e35e45d796e04f7226fef567.png]: https://img-blog.csdnimg.cn/5b8a2e70e35e45d796e04f7226fef567.png
[71fd31ba121f4eae99ac28651249a5f2.png]: https://img-blog.csdnimg.cn/71fd31ba121f4eae99ac28651249a5f2.png
[05dc7ec7fdf345829bef679514aa9b50.png]: https://img-blog.csdnimg.cn/05dc7ec7fdf345829bef679514aa9b50.png