java有几种方式实现队列

这篇文章将为大家详细讲解有关java中几种实现队列的方式，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

成都创新互联公司是一家专业提供水城企业网站建设,专注与成都网站制作、做网站、HTML5建站、小程序制作等业务。10年已为水城众多企业、政府机构等服务。创新互联专业网络公司优惠进行中。

在计算机操作系统里，有各种队列在安静地工作着。打印作业在打印队列中等待打印。当在键盘上敲击时，也有一个存储键入内容的队列。同样，如果使用文字处理程序敲击一个键，而计算机又暂时要做其它的事，敲击的内容不会丢失，它会排在队列中等待，直到文字处理程序有时间来读取它。利用队列保证了键入内容在处理时其顺序不会改变。

队列的两个基本操作是inserting(插入)一个数据项，即把一个数据项放入队尾，另一个是removing(移除)一个数据项，即移除队头的数据项。这类似于电影爱好者排队买票时先排到队尾，然后到达队头买票后离开队列。

栈中的插入和移除数据项方法的命名是很标准，称为push和pop。队列的方法没有标准化的命名。"插入"可以称为put、add或enque，而"删除"可以叫delete、get或deque。插入数据项的队尾，也可以叫作back、tail或end。而移除数据项的队头，也可以叫head。下面将使用insert、remove、front和rear。

队列有3种实现方式，实现方式为：

1、使用两个栈来实现一个队列。

也可以使用两个实现好的栈来实现一个队列（这个问题可能面试笔试的时候回被问到）。

实现方法是：

创建两个栈s1,s2。入队的时候就只压栈到s1中。

出队分两种情况：1.当s2不为空的使用，就弹出栈顶元素作为出队元素。

2.当s2等于空，则先将s1中的元素全部弹出到s2中，再从s2中弹出栈顶元素作为出队元素。

①入队：

public synchronized void put(E data) {//使用同步处理，保证线程安全
s1.push(data);
}

②出队:

public synchronized E pop() {
if(!s2.isEmpty()) {
return s2.pop();
}else {
s2.push(s1.pop());
return s2.pop();
}
}

③.详细代码实现：

package com.wp.datastruct;
 
import java.util.Stack;
 
/**
 * 利用两个栈来模拟队列操作
 * 入队操作就只是想栈s1中添加，
 * 出栈操作分为两部分：
 * 1.当s2中不为空的时候，就直接弹出s2中的栈顶数据
 * 2.当s2中为空的时候，就先把s1中的数据全部弹出到s2中然后将栈顶数据出栈
 * 
 * */
public class MyQueue3 {
Stack s1 = new Stack<>();
Stack s2 = new Stack<>();
public synchronized void put(E data) {//使用同步处理，保证线程安全
s1.push(data);
}
public synchronized E pop() {
if(!s2.isEmpty()) {
return s2.pop();
}else {
s2.push(s1.pop());
return s2.pop();
}
}
public synchronized boolean isEmpty() {
return s1.isEmpty() && s2.empty();
}
}

2、基于链表来实现队列：

首先添加一个节点类，作为队列中的节点元素

public class Node {//链表中的一个节点
Node next = null;
int data;
//构造函数，用于添加链表时候使用
public Node(int d) {
this.data = d;
};
}

再新建一个类作为我们的队列，在该类中实现队列的入队和出队以及求队列的长度和判断队列是否为空等方法

①入队操作：

首先通过函数参数传入要入队的数据，根据传入的参数，新增一个节点Node，在入队方法中判断该队列是否为空，若该队列为空（head==tail）,则该入队的节点既是队头也是队尾。若队列不为空，则将尾节点tail的next指针指向该元素，然后将tail节点指向该节点。

public void put(Integer data) {
Node newNode = new Node(data);//构造一个新节点
if(head == null && tail == null) {//队列为空
head = newNode;
tail = newNode;
}else {
tail.next = newNode;
tail = newNode;
}
}

②出队操作：

若队列为空，则返回空。若队列不为空，则返回该队列的头结点，然后将头结点的下一个元素重新作为头节点

public Integer pop() {
if(this.isEmpty()) {
return null;
}
int data = head.data;
head = head.next;
return data;
}

③判断队列空和对列长度很简单，直接贴代码，不再多说。

public int size() {
int count = 0;
Node tmp = head;
while(tmp != null) {
count++;
tmp = tmp.next;
}
return count;
}

④详细代码实现：

package com.wp.datastruct;
 
/**
 * 利用链表来实现队列
 * */
public class MyQueue {
Node head = null;//队列头
Node tail = null;//队列尾
/**
* 入队操作：
* 若该队列尾空，则入队节点既是头结点也是尾节点
* 若队列不为空，则先用tail节点的next指针指向该节点
* 然后将tail节点指向该节点
* */
public void put(Integer data) {
Node newNode = new Node(data);//构造一个新节点
if(head == null && tail == null) {//队列为空
head = newNode;
tail = newNode;
}else {
tail.next = newNode;
tail = newNode;
}
}
/**
* 判断队列是否为空：当头结点等于尾节点的时候该队列就为空
* */
public boolean isEmpty() {
return head == tail;
}
/**
* 出队操作：
* 若队列为空，则返回null
* 否则，返回队列的头结点，并将head节点指向下一个
* */
public Integer pop() {
if(this.isEmpty()) {
return null;
}
int data = head.data;
head = head.next;
return data;
}
public int size() {
int count = 0;
Node tmp = head;
while(tmp != null) {
count++;
tmp = tmp.next;
}
return count;
}
 
}

3、使用linkedList来实现队列

该方法是使用java中的linkedList集合来实现一个队列，通过调用linkedList中的方法来实现队列的入队出队，判空等操作

首先new一个类来作为我们的队列，该类中包含两个属性，一个是size：用来统计该队列的长度，另一个是LinkedList对象，

代表我们的队列。

private LinkedList list = new LinkedList<>();
private int size = 0;//用于统计队列的长度

①入队操作：

应为linkedList集合中已经实现好了添加删除操作，在这里我们只需要简单的调用方法就可以实现队列的相关操作了，非常简单而且容易理解。

public synchronized void put(E data) {//保证线程安全，实现同步操作
list.add(data);
size++;
}

②出队操作：

public synchronized E pop() {
size--;
return list.removeFirst();//从头取出
}

③详细代码：

public class MyQueue2 {
private LinkedList list = new LinkedList<>();
private int size = 0;//用于统计队列的长度
public synchronized void put(E data) {//保证线程安全，实现同步操作
list.add(data);
size++;
}
public synchronized E pop() {
size--;
return list.removeFirst();//从头取出
}
public synchronized int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}

关于java中几种实现队列的方式就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。