当前位置: 首页 > article >正文

Java:数据结构-队列(Queue)

一 队列

队列是一种先进先出的数据结构,队列中的元素按照进入的顺序排列,第一个插入的元素最先被移除。

1.队列的使用 :

Queue是一个接口,底层是通过链表实现的。

我们可以通过双链表模拟实现一个Queue

1.入队列(向双向链表位置插入新的节点)

public class MyQueue {
    static class ListNode{
        public ListNode prev;
        public ListNode next;
        public int val;
        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head=null;
    public ListNode last=null;
    public int usedSize=0;

    //
    public void offer(int val){
        ListNode node=new ListNode(val);
        if(isEmpty()){
            head=last=node;
        }else {
            last.next=node;
            node.prev=last;
            last=last.next;
        }
        usedSize++;
    }

2.出队列(将队列中的第一个节点移除) 

public class MyQueue {
    static class ListNode{
        public ListNode prev;
        public ListNode next;
        public int val;
        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head=null;
    public ListNode last=null;
    public int usedSize=0;

public boolean isEmpty(){
        return usedSize==0;
    }
    public int pop() {
        if (isEmpty()) {

        }
        head = head.next;
        int val1 = head.val;
        if(head!=null){
            head.prev = null;
        }
        usedSize--;
        return val1;
    }
}

3.查询队列的节点

由于队列的规则为先进先出,所以查询的队列为首节点。

public class MyQueue {
    static class ListNode{
        public ListNode prev;
        public ListNode next;
        public int val;
        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head=null;
    public ListNode last=null;
    public int usedSize=0;

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

2.循环队列

模拟实现的方法:

1. 通过添加 size 属性记录

2. 保留一个位置

3. 使用标记

循环队列是一个环形队列,我们可以使用舍弃一个位置的方法来实现一个循环队列(保留一个位置)

. - 力扣(LeetCode)

public class MyCircleQueue {
    public int front;
    public int last;
    public int[] elem;
    public MyCircleQueue(int k){
        elem=new int[k+1];
    }
    public boolean enQueue(int value){
        if (isFull()){
            return false;
        }
        elem[last]=value;
        last=(last+1)%elem.length;
        return true;
    }
    public boolean deQueue(){
        if(isEmpty()){
            return false;
        }
        front=(front+1)%elem.length;
        return true;
    }
    public int Last(){
        if (isEmpty()){
            return -1;
        }
        int index=(last==0)?elem.length-1:last-1;
        return elem[index];
    }
    public int Front(){
        if (isEmpty()){
            return -1;
        }
        return front;
    }


    public boolean isEmpty(){
        return last==front;
    }
    public boolean isFull(){
        return (last+1)%elem.length==front;
    }
}

二 双端队列 (Deque) 

两端都可以进,可以出。 

三 栈和队列的互相实现

1.用队列实现栈

. - 力扣(LeetCode)

class MyQueue {
    public Queue<Integer> qu1;
    public Queue<Integer> qu2;
    public  MyQueue() {
        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);
        }
    }

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

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

    }

    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

2.用栈实现队列 

. - 力扣(LeetCode)

class MyQueue {
    public ArrayDeque<Integer> s1;
    public ArrayDeque<Integer> s2;
    public MyQueue() {
        s1=new ArrayDeque<>();
        s2=new ArrayDeque<>();
    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        if(empty()){
            return -1;
        }
        if(s2.isEmpty()){
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        }
        return s2.pop();
    }
    
    public int peek() {
        if(empty()){
            return -1;
        }
        if(s2.isEmpty()){
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

希望能对大家有所帮助!!!! 


http://www.kler.cn/a/348850.html

相关文章:

  • SpringBoot教程(三十二) | SpringBoot集成Skywalking链路跟踪
  • 施耐德EcoStruxure Machine SCADA Expert(EMSE)文件管理功能-上(二十)
  • 76.【C语言】perror函数介绍
  • ssh连接慢的问题或zookeeper远程连接服务超时
  • uniapp学习(005-1 详解Part.1)
  • 百度地图怎么上传店铺定位?
  • 前端继承:原理、实现方式与应用场景
  • 中国海油携手科大讯飞共建“海能”人工智能模型,助力能源行业焕新
  • 近邻算法:深入理解与广泛应用
  • protobuf的简介、安装与使用
  • 文献阅读(222) VVQ协议死锁
  • Redis学习笔记:简单动态字符串
  • Kafka原理剖析之「Purgatory(炼狱 | 时间轮)」
  • HTML+CSS总结【量大管饱】
  • Gin中如何自定义Model
  • 面腾讯后台开发,二面挂掉了,,,
  • Netty基础
  • 2024.10月15日- Vue前置基础
  • django urlconf反向解析
  • 插件生成XML