队列 – 那啥快看

Java链表实现队列

Java链表实现队列示意图

代码

public class LinkedQueue {
    // 设置两个结点node，front指向队首元素，rear指向队尾
    Node front;//队头指针，指向队头节点
    Node rear;//队尾指针，指向队尾节点

    int size = 0;//记录队列长度


    //构造函数
    public LinkedQueue() {
        front = rear = null;
    }

    public boolean isEmpty() {
        return size == 0 ? true : false;
    }

    //添加元素
    public boolean addQueue(Object ele) {
        if (size == 0) {
            front = new Node(null, ele);
            rear = front;
            size++;
            return true;
        }
        Node s = new Node(null, ele);
        rear.setNext(s);
        rear = s;
        size++;
        return true;
    }


    /**
     * 删除元素,出队列
     * @return
     */
    public boolean deleteQueue() {
        if (isEmpty()) {
            System.out.println("当前队列为空");
            return false;
        }

        front = front.next;
        size--;
        return true;

    }


    public static void main(String[] args) {
        LinkedQueue queue = new LinkedQueue();
        queue.addQueue(1);
        queue.addQueue(2);
        queue.addQueue(3);
        queue.deleteQueue();
        System.out.println(queue.size);
    }


}

/**
 * 首先链表底层是一个个结点
 */
class Node {

    Node next;
    Object element;

    public Node(Node next, Object element) {
        this.next = next;
        this.element = element;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Object getElement() {
        return element;
    }

    public void setElement(Object element) {
        this.element = element;
    }

}

public class LinkedQueue {

// 设置两个结点node，front指向队首元素，rear指向队尾

Node front;//队头指针，指向队头节点

Node rear;//队尾指针，指向队尾节点

int size = 0;//记录队列长度

//构造函数

public LinkedQueue() {

front = rear = null;

}

public boolean isEmpty() {

return size == 0 ? true : false;

}

//添加元素

public boolean addQueue(Object ele) {

if (size == 0) {

front = new Node(null, ele);

rear = front;

size++;

return true;

}

Node s = new Node(null, ele);

rear.setNext(s);

rear = s;

size++;

return true;

}

/**

* 删除元素,出队列

* @return

public boolean deleteQueue() {

if (isEmpty()) {

System.out.println("当前队列为空");

return false;

}

front = front.next;

size--;

return true;

}

public static void main(String[] args) {

LinkedQueue queue = new LinkedQueue();

queue.addQueue(1);

queue.addQueue(2);

queue.addQueue(3);

queue.deleteQueue();

System.out.println(queue.size);

}

/**

* 首先链表底层是一个个结点

class Node {

Node next;

Object element;

public Node(Node next, Object element) {

this.next = next;

this.element = element;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

public Object getElement() {

return element;

}

public void setElement(Object element) {

this.element = element;

}

Java阻塞队列的实现方式总结

阻塞队列与普通队列的区别

阻塞队列与普通队列的区别在于，当队列是空的时，从队列中获取元素的操作将会被阻塞，或者当队列是满时，往队列里添加元素的操作会被阻塞。试图从空的阻塞队列中获取元素的线程将会被阻塞，直到其他的线程往空的队列插入新的元素。同样，试图往已满的阻塞队列中添加新元素的线程同样也会被阻塞，直到其他的线程使队列重新变得空闲起来，如从队列中移除一个或者多个元素，或者完全清空队列。

阻塞队列的使用场景

最常见的就是省产消费者模式，生产者和消费者速度不一致造成的队列为空或者队列过大的情况。

Java 阻塞队列实现方式

方法一：wait()和notify()方式

public class BlockingQueue {
 
  private List queue = new LinkedList();
  private int  limit = 10;
 
  public BlockingQueue(int limit){
    this.limit = limit;
  }
 
 
  public synchronized void enqueue(Object item)
  throws InterruptedException  {
    while(this.queue.size() == this.limit) {
      wait();
    }
    if(this.queue.size() == 0) {
      notifyAll();
    }
    this.queue.add(item);
  }
 
 
  public synchronized Object dequeue()
  throws InterruptedException{
    while(this.queue.size() == 0){
      wait();
    }
    if(this.queue.size() == this.limit){
      notifyAll();
    }
 
    return this.queue.remove(0);
  }
 
}

public class BlockingQueue {

private List queue = new LinkedList();

private int limit = 10;

public BlockingQueue(int limit){

this.limit = limit;

}

public synchronized void enqueue(Object item)

throws InterruptedException {

while(this.queue.size() == this.limit) {

wait();

}

if(this.queue.size() == 0) {

notifyAll();

}

this.queue.add(item);

}

public synchronized Object dequeue()

throws InterruptedException{

while(this.queue.size() == 0){

wait();

}

if(this.queue.size() == this.limit){

notifyAll();

}

return this.queue.remove(0);

}

在enqueue和dequeue方法内部，只有队列的大小等于上限（limit）或者下限（0）时，才调用notifyAll方法。如果队列的大小既不等于上限，也不等于下限，任何线程调用enqueue或者dequeue方法时，都不会阻塞，都能够正常的往队列中添加或者移除元素。

方法二：阻塞队列类实现

使用ArrayBlockingQueue实现

public class BlockingQueueTest {
 
    public static void main(String[] args) {
        final BlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(3); //缓冲区允许放3个数据
 
        for(int i = 0; i < 2; i ++) {
            new Thread() { //开启两个线程不停的往缓冲区存数据
 
                @Override
                public void run() {
                    while(true) {
                        try {
                            Thread.sleep((long) (Math.random()*1000));
                            System.out.println(Thread.currentThread().getName() + "准备放数据"
                                    + (queue.size() == 3?"..队列已满，正在等待":"..."));
                            queue.put(1);
                            System.out.println(Thread.currentThread().getName() + "存入数据，" 
                                    + "队列目前有" + queue.size() + "个数据");
                        } catch (InterruptedException e) {
                            // TODO Auto-generated catch block
                            e.printStackTrace();
                        } 
                    }
                }
 
            }.start();
        }
 
        new Thread() { //开启一个线程不停的从缓冲区取数据
 
            @Override
            public void run() {
                while(true) {
                    try {
                        Thread.sleep(1000);
                        System.out.println(Thread.currentThread().getName() + "准备取数据"
                                + (queue.size() == 0?"..队列已空，正在等待":"..."));
                        queue.take();
                        System.out.println(Thread.currentThread().getName() + "取出数据，" 
                                + "队列目前有" + queue.size() + "个数据");
                    } catch (InterruptedException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    } 
                }
            }
        }.start();
    }
 
}

public class BlockingQueueTest {

public static void main(String[] args) {

final BlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(3); //缓冲区允许放3个数据

for(int i = 0; i < 2; i ++) {

new Thread() { //开启两个线程不停的往缓冲区存数据

@Override

public void run() {

while(true) {

try {

Thread.sleep((long) (Math.random()*1000));

System.out.println(Thread.currentThread().getName() + "准备放数据"

+ (queue.size() == 3?"..队列已满，正在等待":"..."));

queue.put(1);

System.out.println(Thread.currentThread().getName() + "存入数据，"

+ "队列目前有" + queue.size() + "个数据");

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}.start();

}

new Thread() { //开启一个线程不停的从缓冲区取数据

@Override

public void run() {

while(true) {

try {

Thread.sleep(1000);

System.out.println(Thread.currentThread().getName() + "准备取数据"

+ (queue.size() == 0?"..队列已空，正在等待":"..."));

queue.take();

System.out.println(Thread.currentThread().getName() + "取出数据，"

+ "队列目前有" + queue.size() + "个数据");

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}.start();

}

几种常用的阻塞队列

ArrayBlockingQueue ：一个由数组结构组成的有界阻塞队列。
LinkedBlockingQueue ：一个由链表结构组成的有界阻塞队列。
PriorityBlockingQueue ：一个支持优先级排序的无界阻塞队列。
DelayQueue：一个使用优先级队列实现的无界阻塞队列。
SynchronousQueue：一个不存储元素的阻塞队列。
LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。
LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。

基于java链表实现队列

本文实现了基于java链表实现队列。分享给大家供大家参考，具体如下：

1.Queue接口

public interface Queue<E> {
  //获取队列中元素个数
  int getSize();
 
  //队列中元素是否为空
  boolean isEmpty();
 
  //入队列
  void enqueue(E e);
 
  //出队列
  public E dequeue();
 
  //获取队首元素
  public E getFront();
}

public interface Queue<E> {

//获取队列中元素个数

int getSize();

//队列中元素是否为空

boolean isEmpty();

//入队列

void enqueue(E e);

//出队列

public E dequeue();

//获取队首元素

public E getFront();

}

2.实现类LinkedListQueue

public class LinkedListQueue<E> implements Queue<E> {
 
  //将Node节点设计成私有的类中类
  private class Node<E> {
    public E e;
    public Node next;
 
    //两个参数的构造函数
    public Node(E e, Node next) {
      this.e = e;
      this.next = next;
    }
 
    //一个参数的构造函数
    public Node(E e) {
      this.e = e;
      this.next = null;
    }
 
    //无参构造函数
    public Node() {
      this(null, null);
    }
 
    @Override
    public String toString() {
      return e.toString();
    }
  }
 
  private Node<E> head, tail;
 
  private int size;
 
 
  //显示初始化
  public LinkedListQueue() {
    head = null;
    tail = null;
    size = 0;
  }
 
  //获取队列中节点个数
  @Override
  public int getSize() {
    return size;
  }
 
  //队列中是否为空
  @Override
  public boolean isEmpty() {
    return size == 0;
  }
 
  //链表尾部进队操作
  @Override
  public void enqueue(E e) {
    if (tail == null) {
      tail = new Node(e);
      head = tail;
    } else {
      tail.next = new Node(e);
      tail = tail.next;
    }
    size++;
  }
 
  //链表头部出队操作
  @Override
  public E dequeue() {
    if (isEmpty()) {
      throw new IllegalArgumentException("链表为空");
    }
 
    Node<E> retNode = head;
    head = head.next;
    retNode.next = null;
    if (head == null) {//当链表只有一个元素时
      tail = null;
    }
 
    size--;
    return retNode.e;
  }
 
  //获取队首元素
  @Override
  public E getFront() {
    if (isEmpty()) {
      throw new IllegalArgumentException("链表为空");
    }
    return head.e;
  }
 
 
  //为了便于测试，重写object类toString()方法
  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append("Queue: front ");
    Node<E> cur = head;
    while (cur != null) {
      res.append(cur + "->");
      cur = cur.next;
    }
    res.append("NULL tail");
    return res.toString();
  }
 
}

100

101

102

103

104

105

106

107

108

109

110

public class LinkedListQueue<E> implements Queue<E> {

//将Node节点设计成私有的类中类

private class Node<E> {

public E e;

public Node next;

//两个参数的构造函数

public Node(E e, Node next) {

this.e = e;

this.next = next;

}

//一个参数的构造函数

public Node(E e) {

this.e = e;

this.next = null;

}

//无参构造函数

public Node() {

this(null, null);

}

@Override

public String toString() {

return e.toString();

}

private Node<E> head, tail;

private int size;

//显示初始化

public LinkedListQueue() {

head = null;

tail = null;

size = 0;

}

//获取队列中节点个数

@Override

public int getSize() {

return size;

}

//队列中是否为空

@Override

public boolean isEmpty() {

return size == 0;

}

//链表尾部进队操作

@Override

public void enqueue(E e) {

if (tail == null) {

tail = new Node(e);

head = tail;

} else {

tail.next = new Node(e);

tail = tail.next;

}

size++;

}

//链表头部出队操作

@Override

public E dequeue() {

if (isEmpty()) {

throw new IllegalArgumentException("链表为空");

}

Node<E> retNode = head;

head = head.next;

retNode.next = null;

if (head == null) {//当链表只有一个元素时

tail = null;

}

size--;

return retNode.e;

}

//获取队首元素

@Override

public E getFront() {

if (isEmpty()) {

throw new IllegalArgumentException("链表为空");

}

return head.e;

}

//为了便于测试，重写object类toString()方法

@Override

public String toString() {

StringBuilder res = new StringBuilder();

res.append("Queue: front ");

Node<E> cur = head;

while (cur != null) {

res.append(cur + "->");

cur = cur.next;

}

res.append("NULL tail");

return res.toString();

}

3.测试函数

//测试用例
public static void main(String[] args) {
   LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();
   for (int i = 0; i < 10; i++) {
	queue.enqueue(i);
	System.out.println(queue);
 
	if (i % 3 == 2) {//每添加3个元素出队列一个
		queue.dequeue();
		System.out.println(queue);
	}
   }
}

//测试用例

public static void main(String[] args) {

LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();

for (int i = 0; i < 10; i++) {

queue.enqueue(i);

System.out.println(queue);

if (i % 3 == 2) {//每添加3个元素出队列一个

queue.dequeue();

System.out.println(queue);

}

标签：队列

Java链表实现队列

Java链表实现队列示意图

代码

Java阻塞队列的实现方式总结

阻塞队列与普通队列的区别

阻塞队列的使用场景

Java 阻塞队列实现方式

方法一：wait()和notify()方式

方法二：阻塞队列类实现

几种常用的阻塞队列

基于java链表实现队列

1.Queue接口

2.实现类LinkedListQueue

3.测试函数

4.结果