数据结构java版之队列

数据结构java版之队列

目录

一、简要介绍与队列相关知识

1.什么是队列

2.普通队列和双端队列

3.关于队列一些 *** 作的实现

4.循环队列

二、力扣上相关题目解析

1.设计循环队列

2.用队列实现栈

3.用栈实现队列

---

一、简要介绍与队列相关知识

队列的基本概念：

1.什么是队列

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

2.普通队列和双端队列

3.关于队列一些 *** 作的实现

①普通队列

Queue(一般多使用返回特殊值的处理，更加方便）

错误处理抛出异常返回特殊值入队列add(e)offer(e)出队列remove()poll()队首元素element()peak(）

简单代码示例：

import java.util.*;

public class Test {
    public static void main(String[] args) {
        Queue queue = new linkedList<>();
        queue.offer(1);
        queue.offer(2);
        System.out.println("该队列队头元素为：");
        System.out.println(queue.peek());
        System.out.println("出队元素为");
        System.out.println(queue.poll());
    }
}

②双端队列

Deque(一般多使用返回特殊值的处理，更加方便）

import java.util.*;

public class Test {
    public static void main(String[] args) {
        Deque queue = new linkedList<>();
      queue.offerFirst(2);
      queue.offerLast(1);
        System.out.println("该队列队头元素为：");
        System.out.println(queue.peek());
        System.out.println("出队元素为");
       System.out.println(queue.poll());
    }
}

 用单链表实现队列： 

 代码：

class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val=val;
    }
}
//实质上是一个尾插法
public class MyQueue {
    public Node head;
    public Node last;
    public void offer(int val){
        Node node=new Node(val);
        if(head==null){
            head=node;
            last=node;
        }
        last.next=node;
        last=last.next;
    }
    //出队
    public int poll(){
        if(isEmpty()){
            throw new RuntimeException("队列为空！");
        }int oldVal=head.val;
        this.head=head.next;
        return oldVal;
    }
    public boolean isEmpty(){
        return this.head==null;
    }
    //查看栈顶元素
    public int peek( ){
        if(isEmpty()) {
            throw new RuntimeException("队列为空！");
        }
        return head.val;
    }
    }

4.循环队列

①循环队列的引入

---

 

 

二、力扣上相关题目解析 1.设计循环队列

622. 设计循环队列 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/design-circular-queue/解题思路：见一中循环队列及下图 

代码：

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=(this.rear+1)%elem.length;
        return true;
    }
    //出队 *** 作
    public boolean deQueue() {
        if(isEmpty()) return false;
        //不用管原数，会被新入队的数直接替代
        front=(this.front+1)% elem.length;
        return true;
    }
//得到队头元素
    public int Front() {
     if(isEmpty()) {
         throw new RuntimeException("队列为空");//OJ上改为return -1;
     }
        return this.elem[front];
    }
//得到队尾元素
    public int Rear() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空");//OJ上改为return -1;
        }
        int index=0;
        if(rear==0){
            index=elem.length-1;
        }else{index=rear-1;}
        return this.elem[index];
    }

    public boolean isEmpty() {
     return front==rear;
    }

    public boolean isFull() {
        //判断rear下一个是front就是满了
    if((this.rear+1)% elem.length==front){
        return true;
    }
    return false;
    }
}

2.用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/implement-stack-using-queues/

 解题思路：

①入栈的时候，入到不为空的队列，刚开始都为空指定入到一个队列

②出栈的时候，找到不为空的队列，出size-1个元素到另一个队列，剩下的这个元素就是出栈的元素

代码如下：

class MyStack {
    //创建两个队列
    private Queue qu1;
    private Queue qu2;

    public MyStack() {
        //初始化两个队列
        qu1 = new linkedList<>();
        qu2 = new linkedList<>();
    }

    public void push(int x) {
        //哪个队列不为空，入到哪个队列里，均为空，随便入一个队列，此处入的是qu1
        if (!qu1.isEmpty()) {
            qu1.offer(x);
        } else if (!qu2.isEmpty()) {
            qu2.offer(x);
        } else {
            qu1.offer(x);
        }
    }
    public int pop() {
        if (empty()) return -1;
        if (!qu1.isEmpty()) {
            int size = qu1.size();
            for (int i = 0; i < size - 1; i++) {
                //需要拿一个中间值接收一下暂时出队的元素
                //将出队元素放入另一个队中
                int val = qu1.poll();
                qu2.offer(val);
            }
            return qu1.poll();
        }
        if (!qu2.isEmpty()) {
            int size = qu2.size();
            for (int i = 0; i < size - 1; i++) {
                //需要拿一个中间值接收一下暂时出队的元素
                //将出队元素放入另一个队中
                int val = qu2.poll();
                qu1.offer(val);
            }
            return qu2.poll();
        }
        return -1;
    }
    //得到队头元素
    public int top() {
        if (empty()) return -1;
        if (!qu1.isEmpty()) {
            //因为后续部分要用到val,所以必须拿出pop中局部变量的位置到前面
            int val = -1;
            int size = qu1.size();
            for (int i = 0; i < size; i++) {
                //需要拿一个中间值接收一下暂时出队的元素
                //将出队元素放入另一个队中
                val = qu1.poll();
                qu2.offer(val);
            }
            return val;
        }
        if (!qu2.isEmpty()) {
            int val = -1;
            int size = qu2.size();
            for (int i = 0; i < size; i++) {
                //需要拿一个中间值接收一下暂时出队的元素
                //将出队元素放入另一个队中
                val = qu2.poll();
                qu1.offer(val);
            }
            return val;
        }
        return -1;
    }
 
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty(); 
    }
}

3.用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/implement-queue-using-stacks/解题思路：

 代码如下：

class MyQueue {
    public Stackstack1;
    public Stackstack2;
    public MyQueue() {
        stack1=new Stack();
        stack2=new Stack();
    }
    //出队第一个栈
    public void push(int x) {
 stack1.push(x);
    }
    public int pop() {
if(empty()) return -1;
if(stack2.isEmpty()){
    while(!stack1.isEmpty()){
    stack2.push(stack1.pop());
}
}
   return stack2.pop();
}
    
    public int peek() {
if(empty()) return -1;
if(stack2.isEmpty()){
    while(!stack1.isEmpty()){
    stack2.push(stack1.pop());
}
}
   return stack2.peek();
}
    
    public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
    }
}