提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  大数据

当前栏目

数据结构之队列（Queue）

队列数据结构队列 Queue
2023-09-11 14:20:20 时间

目录

1.队列（Queue）之概念

2.队列（Queue）之模拟实现

3.队列（Queue）之使用

4.队列（Queue）之循环队列

5.队列（Queue）之双端队列(Deque)

6.力扣中的练习题

6.1 用队列实现栈

6.2 用栈实现队列

6.3 最小栈

1.队列（Queue）之概念

定义：队列是一种特殊的线性表，它只允许在一端进行插入（队尾）数据操作，在另一端进行删除（队头）数据操作。

队列具有先进先出的特点

队列的实现也是有两种方式

数组实现，链表实现

2.队列（Queue）之模拟实现

以单链表实现，并且做一点改动

 先写一个上面这样结构的单链表

    static class Node {
        public int val;
        public Node next;
        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;//队列头
    public Node tail;//队列尾

（1）入队offer()

    public void offer(int val) {
        Node node = new Node(val);
        if (head == null) {
            head = node;
            tail = node;
        }else {
            tail.next = node;
            tail = tail.next;
        }
    }

（2）出队poll()

  public int poll() {
        if(head == null) {
            return -1;
        }
        int oldVal = head.val;
        if (head.next == null) {
            head = tail = null;
        }else {
            head = head.next;
        }
        return oldVal;
    }

（3）查看当前对头元素peek()

    public int peek() {
        if(head == null) {
            return -1;
        }
        return head.val;
    }

3.队列（Queue）之使用

    public static void main(String[] args) {
        java.util.Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(5);
        queue.offer(7);
        queue.offer(45);
        System.out.println(queue.size());
        System.out.println(queue.peek());
        queue.poll();
        System.out.println(queue.poll());
    }

 

4.队列（Queue）之循环队列

先看顺序队列中元素的入队出队操作，因为队列元素出队是在对头，

那也就是，队列中所有元素的移动都是在向前移动，而这样向前移动就会出现这样的问题

 所以，相对来说 对于队列最好的方法是使用链表实现，否则就会造成假溢出

那么java中对于假溢出解决的办法是使用循环队列

正常情况下，顺序队列中会发生假溢出，也就是开辟的数组空间还有剩余空间，却因为rear越界表现为溢出，

使用循环队列，就是将队列的首尾相连，这样rear移动到LENGTH时，就会再从0开始循环

1. 那么如何区分队列的空与满 因为当rear== front时，既表示空又表示满

 （1）最直接的方法就是计数

（2）牺牲一个存储空间 front前面不存数据，当rear在front前面的时候就是满了（尾在头前就是满了）

（3） 是设置一个标志变量flag，当front == rear,且flag = 0时为队列空，当front == rear,且flag= 1时为队列满

 看一个练习题

链接622. 设计循环队列 - 力扣（LeetCode）

题目要求  分析一下

入队和出队除了要考虑队满和队空的条件，还要考虑，当这一圈转完，到下一圈，不能时不能只加加，还要模个数组长度，得出第二圈的下标

上代码

class MyCircularQueue {
    public int[] elem;
    public int front;//队头下标
    public int rear;//队尾下标

    public MyCircularQueue(int k) {
        this.elem = new int[k+1];
    }
    //入队
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        this.elem[rear] = value;
        rear = (rear+1) % elem.length;
        return true;
    }
    //出队
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front+1) % elem.length;//如果是K到0那就要%
        return true;
    }
    //从队首获取元素
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elem[front];
    }
    //获取队尾元素
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        int index = (rear == 0) ? elem.length-1 : rear-1; 
        return elem[index];
    }
    
    public boolean isEmpty() {
        return rear == front;
    }
    
    public boolean isFull() {
        return (rear+1) % elem.length == front;
    }
}

 

5.队列（Queue）之双端队列(Deque)

双端队列（Deque）是指在两端都可以进行入队和出队的操作的队列

不过需要注意的是，不能将一个数据，在一端进行入队和出队操作，不然这样就成了栈

 

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

        Deque<Integer> myQueue2 = new LinkedList<>();

6.力扣中的练习题

6.1 用队列实现栈

链接  225. 用队列实现栈 - 力扣（LeetCode）

题目要求

 分析一下

 

 上代码

class MyStack {
    Queue<Integer> qu1;
    Queue<Integer> qu2;
    public int usedSize;
    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }
    
    public void push(int x) {
        if(!qu1.isEmpty()) {
            qu1.offer(x);
        } else if(!qu2.isEmpty()) {
            qu2.offer(x);
        } else {
            qu1.offer(x);
        }
        usedSize++;
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(!qu1.isEmpty()) {
            int curSize = qu1.size();
            for(int i = 0; i < curSize-1; i++) {
                qu2.offer(qu1.poll());
            }
            usedSize--;
            return qu1.poll();
        }else {
            int curSize = qu2.size();
            for(int i = 0; i < curSize-1; i++) {
                qu1.offer(qu2.poll());
            }
            usedSize--;
            return qu2.poll();
        }

    }
    
    public int top() {
          if(empty()) {
            return -1;
        }
        if(!qu1.isEmpty()) {
            int curSize = qu1.size();
            int ret = -1;
            for(int i = 0; i < curSize; i++) {
                ret = qu1.poll();
                qu2.offer(ret);
            }
            return ret;
        }else {
            int curSize = qu2.size();
            int ret = -1;
            for(int i = 0; i < curSize; i++) {
                 ret = qu2.poll();
                qu1.offer(ret);
            }
            return ret;
        }
    }
    
    public boolean empty() {
        return usedSize == 0;
    }
}

 

6.2 用栈实现队列

链接  232. 用栈实现队列 - 力扣（LeetCode）

题目要求

 分析一下

 上代码

class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(s2.empty()) {
            //将s1中所有元素倒过来
            while(!s1.empty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    public int peek() {
        if(empty()) {
            return -1;
        }
        if(s2.empty()) {
            //将s1中所有元素倒过来
            while(!s1.empty()) {
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}

6.3 最小栈

链接  155. 最小栈 - 力扣（LeetCode）

题目要求

分析一下

 上代码

class MinStack {
    private Stack<Integer> s;//普通栈
    private Stack<Integer> minStack;//最小栈

    public MinStack() {
        s = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        s.push(val);
        if(minStack.empty()) {
            //最小栈为null，直接放
            minStack.push(val);
        }else {
            int peekV = minStack.peek();
            if(val <= peekV) {
                minStack.push(val);
            }
        }
    }
    
    public void pop() {
            int popV = s.pop();
            int peekVMinS = minStack.peek();
            if(popV == peekVMinS) {
                minStack.pop();
            }
    }
    
    public int top() {
            return s.peek();
    }
    
    public int getMin() {
            return minStack.peek();
    }
}

相关文章