手把手教你Java实现栈和队列

柔情只为你懂 2023-10-09 19:17 7阅读 0赞

![e79531dbeadb451590483308c7c2fb7b.jpeg][]

**目录**

一、栈(Stack)

1、概念

2、栈的使用

3、栈的模拟实现

4、栈的应用场景

2. 队列(Queue)

1、概念

2、队列的使用

3、队列模拟实现

4、循环队列

三、双端队列 (Deque)

五、栈和队列的互相实现

用队列实现栈：

用栈实现队列：

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

## 一、**栈****(Stack)**  ##

### 1、**概念**  ###

**栈** ：一种特殊的线性表，其 **只允许在固定的一端进行插入和删除元素操作** 。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO （ Last In First Out ）的原则。

**压栈** ：栈的插入操作叫做进栈 / 压栈 / 入栈， **入数据在栈顶**。

**出栈** ：栈的删除操作叫做出栈。 **出数据在栈顶**。

![99901d3d4cda42008d0bc6a5317a485a.png][]

栈的push 和 pop操作大概可以用下面这张图来进行表示：

![eb1c0d7e3190422c8f574dae4cac8c8c.png][]

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

![d70350268b11404582144f3ffab7c196.png][]

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

### **2、栈的使用** ###

在Java中，关于栈的常用的方法有以下几个：

![4973c236f730495eacc4478e6f541498.png][]

我们可以用代码来感受一下这些方法的使用：

public static void main(String[] args) {
            Stack<Integer> s = new Stack();
            s.push(1);
            s.push(2);
            s.push(3);
            s.push(4);
            System.out.println(s.size()); // 获取栈中有效元素个数---> 4
            System.out.println(s.peek()); // 获取栈顶元素---> 4
            s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
            System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
            if(s.empty()){
                System.out.println("栈空");
            }else{
                System.out.println(s.size());
            }
        }

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

### **3、栈的模拟实现** ###

![806cdbce04834691b8667bd7c0f563d7.png][]

从上图中可以看到， Stack 继承了 Vector ， Vector 和 ArrayList 类似，都是动态的顺序表，不同的是 Vector 是线程安全的。

那么现在，我们可以运用目前所学过的知识来模拟一下栈中的各个方法：

**push方法**

public int push(int e){
            ensureCapacity();
            array[size++] = e;
            return e;
        }

**pop方法**

public int pop(){
            int e = peek();
            size--;
            return e;
        }

**peek方法**

public int peek(){
            if(empty()){
                throw new RuntimeException("栈为空，无法获取栈顶元素");
            }
            return array[size-1];
        }

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

### **4、栈的应用场景** ###

**1. 改变元素的序列**

现在，我们来看这样一道题：

![7125b8bcb4d149339b20f1ffe7fc32f5.png][]

我们可以根据栈的先进后出的特性来对其进行分析

我们可以发现，A选项中是先将1入栈再出栈，再将234依次入栈后出栈所得到的结果

B选项是先将1入栈，再将234轮流入栈出栈，最后将1出栈得到的结果

C选项是不可能做到的，因为如果按照31的顺序出栈，那么2必然先比1出栈

D选项则是先把12入栈，再将34轮流进行出栈入栈的操作后，再将12出栈

根据这道例题，我们发现可以运用栈来改变元素的序列

**2. 将递归转化为循环**

假设现在有这么一道oj题：要求我们逆序打印链表

那么递归的写法是这个样子的：

// 递归方式
        void printList(Node head){
            if(null != head){
                printList(head.next);
                System.out.print(head.val + " ");
            }
        }

而如果我们使用栈，那么代码就会演变成这样:

void printList(Node head){
            if(null == head){
                return;
            }
            Stack<Node> s = new Stack<>();
    // 将链表中的结点保存在栈中
            Node cur = head;
            while(null != cur){
                s.push(cur);
                cur = cur.next;
            }
            // 将栈中的元素出栈
            while(!s.empty()){
                System.out.print(s.pop().val + " ");
            }
        }

综上，我们可以得知：通过栈的实现，我们可以将递归转化成循环

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

## **2.** **队列****(Queue)**  ##

### **1、概念**  ###

**队列** ：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为 **队尾（Tail/Rear）**  出队列：进行删除操作的一端称为 **队头（Head/Front）**

![f58c75ec97ed45eca9e9bf253fdb8787.png][]

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

### **2、队列的使用**  ###

在 Java 中， **Queue是个接口，底层是通过链表实现** 的。

![41a3676c89e64b94bc4086a6a9b997ef.png][]

那么在Java中，常见的队列的方法有以下几种：

![6afdc03a46ae476892232e4c711b067c.png][]

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

public static void main(String[] args) {
            Queue<Integer> q = new LinkedList<>();
            q.offer(1);
            q.offer(2);
            q.offer(3);
            q.offer(4);
            q.offer(5); // 从队尾入队列
            System.out.println(q.size());
            System.out.println(q.peek()); // 获取队头元素
            q.poll();
            System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
            if(q.isEmpty()){
                System.out.println("队列空");
            }else{
                System.out.println(q.size());
            }
        }

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

### **3、队列模拟实现** ###

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种： **顺序结构 和 链式结构** 。

![76c3fcd13cfd4d6ca8c0bdbbf3d36401.png][]

public class Queue {
        // 双向链表节点
        public static class ListNode{
            ListNode next;
            ListNode prev;
            int value;
            ListNode(int value){
                this.value = value;
            }
        }
        ListNode first; // 队头
        ListNode last; // 队尾
        int size = 0;
        // 入队列---向双向链表位置插入新节点
        public void offer(int e){
            ListNode newNode = new ListNode(e);
            if(first == null){
                first = newNode;
    // last = newNode;
            }else{
                last.next = newNode;
                newNode.prev = last;
    // last = newNode;
            }
            last = newNode;
            size++;
        }
        // 出队列---将双向链表第一个节点删除掉
        public int poll(){
    // 1. 队列为空
    // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
    // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
            int value = 0;
            if(first == null){
                return null;
            }else if(first == last){
                last = null;
                first = null;
            }else{
                value = first.value;
                first = first.next;
                first.prev.next = null;
                first.prev = null;
            }
            --size;
            return value;
        }
        // 获取队头元素---获取链
        public int peek(){
            if(first == null){
                return null;
            }
            return first.value;
        }
        public int size() {
            return size;
        }
        public boolean isEmpty(){
            return first == null;
        }
    }

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

### **4、循环队列**  ###

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。

环形队列的结构如下图所示：

![f06f6b722ee74b0baa8dec57d67ccb9a.png][]

**数组下标循环的小技巧**

1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

![e606a2b7d3c54af180fc09d2b61f2bf7.png][]

2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset)%array.length

![a6d9a059f24c407983087968c450d7e4.png][]

**如何区分空与满**

> 1.  通过添加  size  属性记录 
> 
> 2.  保留一个位置 
> 
> 3.  使用标记

![66bfe115897148848bd2384d22637e35.png][]

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

## **三、双端队列 (Deque)** ##

双端队列（ deque ）是指允许两端都可以进行入队和出队操作的队列， deque  是  “double ended queue”  的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

![d65b65f72bd6472380f78347ac2195c5.png][]

Deque是一个接口，使用时必须创建LinkedList的对象。

![df28a07a5ea041a8b9da609eb7f63222.png][]

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
    Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

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

## **五、栈和队列的互相实现** ##

#### **用队列实现栈：** ####

class MyStack {
        Queue<Integer> queue1;
        Queue<Integer> queue2;
    
        public MyStack() {
            queue1 = new LinkedList<Integer>();
            queue2 = new LinkedList<Integer>();
        }
        
        public void push(int x) {
            queue2.offer(x);
            while (!queue1.isEmpty()) {
                queue2.offer(queue1.poll());
            }
            Queue<Integer> temp = queue1;
            queue1 = queue2;
            queue2 = temp;
        }
        
        public int pop() {
            return queue1.poll();
        }
        
        public int top() {
            return queue1.peek();
        }
        
        public boolean empty() {
            return queue1.isEmpty();
        }
    }

#### **用栈实现队列：** ####

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

[e79531dbeadb451590483308c7c2fb7b.jpeg]: https://img-blog.csdnimg.cn/e79531dbeadb451590483308c7c2fb7b.jpeg
[99901d3d4cda42008d0bc6a5317a485a.png]: https://img-blog.csdnimg.cn/99901d3d4cda42008d0bc6a5317a485a.png
[eb1c0d7e3190422c8f574dae4cac8c8c.png]: https://img-blog.csdnimg.cn/eb1c0d7e3190422c8f574dae4cac8c8c.png
[d70350268b11404582144f3ffab7c196.png]: https://img-blog.csdnimg.cn/d70350268b11404582144f3ffab7c196.png
[4973c236f730495eacc4478e6f541498.png]: https://img-blog.csdnimg.cn/4973c236f730495eacc4478e6f541498.png
[806cdbce04834691b8667bd7c0f563d7.png]: https://img-blog.csdnimg.cn/806cdbce04834691b8667bd7c0f563d7.png
[7125b8bcb4d149339b20f1ffe7fc32f5.png]: https://img-blog.csdnimg.cn/7125b8bcb4d149339b20f1ffe7fc32f5.png
[f58c75ec97ed45eca9e9bf253fdb8787.png]: https://img-blog.csdnimg.cn/f58c75ec97ed45eca9e9bf253fdb8787.png
[41a3676c89e64b94bc4086a6a9b997ef.png]: https://img-blog.csdnimg.cn/41a3676c89e64b94bc4086a6a9b997ef.png
[6afdc03a46ae476892232e4c711b067c.png]: https://img-blog.csdnimg.cn/6afdc03a46ae476892232e4c711b067c.png
[76c3fcd13cfd4d6ca8c0bdbbf3d36401.png]: https://img-blog.csdnimg.cn/76c3fcd13cfd4d6ca8c0bdbbf3d36401.png
[f06f6b722ee74b0baa8dec57d67ccb9a.png]: https://img-blog.csdnimg.cn/f06f6b722ee74b0baa8dec57d67ccb9a.png
[e606a2b7d3c54af180fc09d2b61f2bf7.png]: https://img-blog.csdnimg.cn/e606a2b7d3c54af180fc09d2b61f2bf7.png
[a6d9a059f24c407983087968c450d7e4.png]: https://img-blog.csdnimg.cn/a6d9a059f24c407983087968c450d7e4.png
[66bfe115897148848bd2384d22637e35.png]: https://img-blog.csdnimg.cn/66bfe115897148848bd2384d22637e35.png
[d65b65f72bd6472380f78347ac2195c5.png]: https://img-blog.csdnimg.cn/d65b65f72bd6472380f78347ac2195c5.png
[df28a07a5ea041a8b9da609eb7f63222.png]: https://img-blog.csdnimg.cn/df28a07a5ea041a8b9da609eb7f63222.png