【数据结构与算法之线性结构】队列

叁歲伎倆 2024-03-25 12:36 111阅读 0赞

#### 【数据结构与算法之线性结构】队列 ####

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

*   *   *  【数据结构与算法之线性结构】队列
         *   *   *  1 队列的基本概念
                 *  2 队列的定义
                 *  3 队列的基本操作
                 *   *  入队列
                     *  出队列
                 *  4 双端队列
                 *  5 案例
                 *   *  打印符号三角形
                     *  用两个栈实现一个队列

###### 1 队列的基本概念 ######

队列Queue，是一种先进先出FIFO的线性表，与一般数组和链表不同，队列要求所有数据都只能从一端进，从另一端出。

数据进入的一端 → 队尾rear，数据离开的一端 → 队头front。

![在这里插入图片描述][7efe00c2808c482cb2f67cd4c1111a0c.png_pic_center]

###### 2 队列的定义 ######

用链表实现链队列。

节点类：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyQueueNode
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 10:59
     */
    
    public class MyQueueNode {
        
    
        int data; // 数据域
        MyQueueNode next; // 指针域，指向下一个节点
    
        public MyQueueNode(int data) {
        
            this.data = data;
            this.next = null;
        }
    }

队列类：

###### 3 队列的基本操作 ######

###### 入队列 ######

让指定元素从队列的尾部进入队列。

Java实现

public void enQueue(int data) {
        
        // data入队
        MyQueueNode node = new MyQueueNode(data);
        if (front == null && rear == null) {
        
            // 队列为空，队头队尾都指向node
            front = rear = node;
        } else {
        
            // 队列不为空
            rear.next = node;
            rear = node;
        }
    }

###### 出队列 ######

将队头元素从队列中取出。

Java 实现：

public int deQueue() {
        
        // 队头元素出队
        if (front == null) {
        
            // 队列为空，返回一个无效值
            return -1;
        }
        int data = front.data;
        front = front.next;
        if (front == null) {
        
            // 如果元素出队后，front为空了，那么rear也要置空
            rear = null;
        }
        return data;
    }

测试

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyQueue
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 11:00
     */
    
    public class MyQueue {
        
    
        private MyQueueNode front; // 队头
        private MyQueueNode rear; // 队尾
    
        public MyQueue() {
        
            front = null;
            rear = null;
        }
    
        public void enQueue(int data) {
        
            // data入队
            MyQueueNode node = new MyQueueNode(data);
            if (front == null && rear == null) {
        
                // 队列为空，队头队尾都指向node
                front = rear = node;
            } else {
        
                // 队列不为空
                rear.next = node;
                rear = node;
            }
        }
    
        public int deQueue() {
        
            // 队头元素出队
            if (front == null) {
        
                // 队列为空，返回一个无效值
                return -1;
            }
            int data = front.data;
            front = front.next;
            if (front == null) {
        
                // 如果元素出队后，front为空了，那么rear也要置空
                rear = null;
            }
            return data;
        }
    
        // 获取队列长度
        public int getQueueLength() {
        
            int length = 0;
            MyQueueNode p = front;
            while (p != null) {
        
                length++;
                p = p.next;
            }
            return length;
        }
    
        // 销毁队列
        public void destroyQueue() {
        
            rear = null;
            front = null;
        }
    
        public static void main(String[] args) {
        
    
            MyQueue queue = new MyQueue();
            queue.enQueue(1);
            queue.enQueue(2);
            queue.enQueue(3);
            queue.enQueue(4);
            System.out.println("当前队列长度为: " + queue.getQueueLength());
    
            System.out.println(queue.deQueue());
            System.out.println(queue.deQueue());
    
            queue.destroyQueue();
            System.out.println("当前队列长度为: " + queue.getQueueLength());
    
        }
    }

运行结果

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

###### 4 双端队列 ######

![在这里插入图片描述][23721d6047314d4c870483f959e61fdb.png_pic_center]

双端队列结合了队列和栈的优点，即从队列的两端都可以插入数据(入队)和删除数据(出队)。

###### 5 案例 ######

###### 打印符号三角形 ######

符号三角形特点：仅由+ 和 - 两种符号构成，同号下面是 + ，异号下面是 - ，输入第一行，打印出符合规则的符号三角形。如下图

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

【经典队列问题】利用队列先进先出的特性，先将第1行的n个符号入队，再依次将符号取出，在取出第i个符号时，判断它是否和i - 1个符号相同，如果相同，则将 + 入队，如果不同，- 入队，在第 1 行的n 个符号全部出队后，第2行的n - 1个符号也已经全部进入队列。重复操作，一共会打印n 行，即此可以打印出题目需要的符号三角形。

节点类：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyQueueNode
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 10:59
     */
    
    public class MyQueueNode {
        
    
        char data; // 数据域
        MyQueueNode next; // 指针域，指向下一个节点
    
        public MyQueueNode(char data) {
        
            this.data = data;
            this.next = null;
        }
    }

自定义队列类：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyQueue
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 11:00
     */
    
    public class MyQueue {
        
    
        private MyQueueNode front; // 队头
        private MyQueueNode rear; // 队尾
    
        public MyQueue() {
        
            front = null;
            rear = null;
        }
    
        public void enQueue(char data) {
        
            // data入队
            MyQueueNode node = new MyQueueNode(data);
            if (front == null && rear == null) {
        
                // 队列为空，队头队尾都指向node
                front = rear = node;
            } else {
        
                // 队列不为空
                rear.next = node;
                rear = node;
            }
        }
    
        public char deQueue() {
        
            // 队头元素出队
            if (front == null) {
        
                // 队列为空，返回一个无效值
                return ' ';
            }
            char data = front.data;
            front = front.next;
            if (front == null) {
        
                // 如果元素出队后，front为空了，那么rear也要置空
                rear = null;
            }
            return data;
        }
    
        // 获取队列长度
        public int getQueueLength() {
        
            int length = 0;
            MyQueueNode p = front;
            while (p != null) {
        
                length++;
                p = p.next;
            }
            return length;
        }
    
        // 销毁队列
        public void destroyQueue() {
        
            rear = null;
            front = null;
        }
    
        public static void main(String[] args) {
        
    
            MyQueue queue = new MyQueue();
            queue.enQueue('1');
            queue.enQueue('2');
            queue.enQueue('3');
            queue.enQueue('4');
            System.out.println("当前队列长度为: " + queue.getQueueLength());
    
            System.out.println(queue.deQueue());
            System.out.println(queue.deQueue());
    
            queue.destroyQueue();
            System.out.println("当前队列长度为: " + queue.getQueueLength());
    
        }
    }

测试

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: PrintCharacterTriangle
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 11:17
     */
    
    public class PrintCharacterTriangleTest {
        
    
        public static void printCharacterTriangle(String firstLine) {
        
            MyQueue queue = new MyQueue();
            int count = firstLine.length();
    
            for (int i = 0; i < count; i++) {
        
                queue.enQueue(firstLine.charAt(i)); // 第一行各元素入队
            }
    
            for (int i = 0; i < count; i++) {
        
                for (int j = 0; j < i; j++) {
        
                    // 控制形状
                    System.out.print(" "); // 第一行空0格，第二行空1格，第三行空2格，第四行空3格
                }
                char a = queue.deQueue();
                System.out.print(a + " ");
    
                for (int j = 0; j < count - i - 1; j++) {
        
                    char b = queue.deQueue();
                    System.out.print(b + " ");
    
                    if (a == b) {
        
                        queue.enQueue('+');
                    } else {
        
                        queue.enQueue('-');
                    }
    
                    a = b;
                }
    
                System.out.println();
            }
        }
    
        public static void main(String[] args) {
        
    
            String firstLine = "+--+++--+";
            printCharacterTriangle(firstLine);
    
        }
    
    }

运行结果

![在这里插入图片描述][4080ae183bf24cdf8cc090f121769204.png_pic_center]

###### 用两个栈实现一个队列 ######

无论怎样实现队列，最核心的一点都是要满足队列先进先出的特性。

要想用栈实现，就必须通过某种方式将先进后出转化为先进先出，从而模拟队列。

【实现思路】在入队列时，将元素压入stack1，在出队列时，判断stack2是否为空，如果stack2不为空，则直接取出stack2的栈顶元素，如果stack2为空，则将stack1中的元素逐一弹出，并压入stack2，再取出stack2的栈顶元素。

Java实现：

栈类：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyStack
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 9:27
     */
    
    public class MyStack {
        
    
        int[] stack; // 数组实现栈
        int top; // 栈顶索引
        int capacity; // 栈的容量
    
        public MyStack(int capacity) {
        
            stack = new int[capacity]; // 动态初始化栈，长度为capacity
            top = 0; // 栈顶索引为0，说明此时栈空
            this.capacity = capacity; // 初始化栈的容量
        }
    
        public MyStack() {
        
            stack = new int[100];
            top = 0;
            this.capacity = 100;
        }
    
        public int getCount() {
        
            return top;
        }
    
        public boolean isEmpty() {
        
            if (top == 0) {
        
                return true;
            }
            return false;
        }
    
        public void push(int elem) {
        
            // 元素入栈
            if (top == capacity) {
        
                // 扩容
                increaseCapacity();
            }
            stack[top] = elem;
            top++;
        }
    
        public void increaseCapacity() {
        
            // 增加栈的容量
            // 初始化一个新栈，容量是原栈容量的2倍
            int[] stackTmp = new int[stack.length * 2];
            System.arraycopy(stack, 0, stackTmp, 0, stack.length);
            stack = stackTmp;
        }
    
        public int pop() {
        
            // 出栈
            if (top == 0) {
        
    //            System.out.println("栈中没有数据");
                return ' '; // 返回一个无效值
            }
            top--;
            return stack[top];
        }
    
        public static void main(String[] args) {
        
    
            MyStack stack = new MyStack(3);
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
            stack.push(5);
    
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
        }
    }

栈队列类：

import java.nio.channels.Pipe;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: StackQueue
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 11:44
     */
    
    public class StackQueue {
        
    
        MyStack stack1 = new MyStack();
        MyStack stack2 = new MyStack();
    
        public void enQueue(int elem) {
        
            stack1.push(elem);
        }
    
        public int deQueue() {
        
            if (!stack2.isEmpty()) {
        
                return stack2.pop();
            } else {
        
                while (!stack1.isEmpty()) {
        
                    stack2.push(stack1.pop());
                }
    
                return stack2.pop();
            }
        }
    
        public boolean isEmptyQueue() {
        
            if (stack1.isEmpty() && stack2.isEmpty()) {
        
                return true;
            }
    
            return false;
        }
    
        public int getCount() {
        
            return stack1.getCount() + stack2.getCount();
        }
    
        public static void main(String[] args) {
        
    
            StackQueue queue = new StackQueue();
            queue.enQueue(1);
            queue.enQueue(2);
            queue.enQueue(3);
            queue.enQueue(4);
            queue.enQueue(5);
    
            System.out.println("当前队列元素数为 : " + queue.getCount());
            System.out.println(queue.deQueue());
            System.out.println(queue.deQueue());
            System.out.println("当前队列元素数为 : " + queue.getCount());
            System.out.println(queue.deQueue());
            System.out.println(queue.deQueue());
            System.out.println(queue.deQueue());
            System.out.println("队列为空了吗? " + queue.isEmptyQueue());
    
        }
    
    }

运行结果

![在这里插入图片描述][8d79699e01d74bd4b0ea9d967413c7c7.png_pic_center]

[7efe00c2808c482cb2f67cd4c1111a0c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2505df05f0bf4ce89cd925fa9b981a43.png
[bac32678c9b041088a8bc54fc778f135.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/89326ab242c043ec84b2dd7c177f15ec.png
[23721d6047314d4c870483f959e61fdb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/aa5a4aa52758412f95bd5000f54764df.png
[e545216a5ada4e1795bfba57448baff3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b7b0612321e8476f97777e66110abd2e.png
[4080ae183bf24cdf8cc090f121769204.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/90ed92bbd4cb4b16ba0effb651aac1a7.png
[8d79699e01d74bd4b0ea9d967413c7c7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1ea08c62ef8845739dad522bb4d7825d.png