数据结构-队列

数据结构-队列 数据结构-队列

数据结构本身和语言无关，为了方便理解本文使用java语言举例说明，介绍队列是什么？队列特性和队列使用场景

---

文章目录

• 数据结构-队列
• 一、队列是什么
• 二、java实现队列
• • 1.实现类
  • 2.测试
  • 3.测试结果：
• 特性
• 应用场景
• 总结

---

一、队列是什么

队列也是一种线性结构，像一根管道一样，数据从一头进入从另一头出来，是有序的，也是我们经常说的先进先出。

二、java实现队列 1.实现类

package com.luodea.datastructure;



public class Queue {

    
    private Node startNode = new Node(true);

    
    private Node tailNode = new  Node(false);

    
    private final Object push = new Object();

    
    private final Object pop = new Object();

    public Queue() {
        startNode.setNextNode(tailNode);
        tailNode.setPreNode(startNode);
    }

    
    public void push(M value){
        if (value ==null){
            return;
        }
        
        synchronized (push){
            Node nextNode = startNode.getNextNode();
            Node mNode = new Node(value);
            mNode.setNextNode(nextNode);
            mNode.setPreNode(startNode);
            nextNode.setPreNode(mNode);
            startNode.setNextNode(mNode);
        }
    }

    
    public M pop(){
        Node preNode = tailNode.getPreNode();
        if (preNode.isStartNode){
            return null;
        }
        
        synchronized (pop) {
            Node preNode1 = preNode.getPreNode();
            tailNode.setPreNode(preNode1);
            preNode1.setNextNode(tailNode);
            preNode.setPreNode(null);
            preNode.setNextNode(null);
            return preNode.getValue();
        }
    }

    
    public static class Node {

        
        private Node preNode;

        
        private Node nextNode;

        
        private final T value;

        
        private final  boolean isStartNode;


        public Node(T value) {
            this.isStartNode = false;
            this.value = value;
        }

        public Node(boolean isStartNode) {
            this.value = null;
            this.isStartNode = isStartNode;
        }

        
        public void setPreNode(Node preNode) {
            this.preNode = preNode;
        }

        
        public void setNextNode(Node nextNode) {
            this.nextNode = nextNode;
        }

        
        public Node getPreNode() {
            return preNode;
        }

        
        public Node getNextNode() {
            return nextNode;
        }

        
        public T getValue() {
            return value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o){
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Node node = (Node) o;
            return value.equals(node.value);
        }

        @Override
        public int hashCode() {
            return this.value.hashCode();
        }
    }
}

2.测试

     public static void main(String[] args) {
       final   Queue stringQueue = new Queue();

        
        new Thread(new Runnable() {
            public void run() {
                stringQueue.push("value-1");
                stringQueue.push("value-2");
                stringQueue.push("value-3");
                stringQueue.push("value-4");
                stringQueue.push("value-5");
            }
        }).start();

        
        new Thread(new Runnable() {
            public void run() {
                System.out.println(stringQueue.pop());
                System.out.println(stringQueue.pop());
                System.out.println(stringQueue.pop());
                System.out.println(stringQueue.pop());
                System.out.println(stringQueue.pop());
                System.out.println(stringQueue.pop());
                System.out.println(stringQueue.pop());
                System.out.println(stringQueue.pop());
                System.out.println(stringQueue.pop());
            }
        }).start();
    }

3.测试结果：

value-1
value-2
value-3
value-4
value-5
null
null
null
null

测试发现最先进入队列的数据最先出来

特性

队列内数据有序，保持先进先出的特性，和栈的特性刚好相反

应用场景

队列在程序中应用非常广泛。高并发下可以用来实现线程竞争等待队列。消息中间消息存储队列件如RabbitMQ，ActiveMQ等

---

总结

队列在开中经常使用，我们必须掌握其原理和实现。