queue的实现类（数据结构篇|队列）

本文目录

• 数据结构篇|队列
• java中的“queue类”是什么，有什么作用
• queue java 是怎么实现的
• java中创建队列Queue的问题
• c++如何查看queue里面的函数原型
• C/C++线程安全型队列的实现
• deque java
• 为什么javaSE不能初始化Queue类型

数据结构篇|队列

实现这个队列在这里我选择复用之前实现的数组的一些方法，链接如下：

将实现的Array类拷贝过来之后，然后我们再创建一个接口，这个接口的方法如上所示， getSize() 方法是获取队列中元素的个数， isEmpty() 是判断队列中是否为空， enqueue() 方法是向队列中添加一个E类型的元素e， dequque() 方法是让队列中队首的元素进行出队， getFront() 是查看队首的元素。

创建完接口之后再创建一个实现类ArrayQueue，因为需要复用引入进来的Array类，所以先声明一个Array类型的参数array，然后进行构造方法的编写。第一个构造方法是有参的，适用于用户已知需要多大容量的情况下，参数为整形的 capacity ，意思是可以传入队列的容量，所以在方法中就直接实例化Array类并将capacity传入进去。再编写一个无参的构造方法，这个方法适用于不知道容量的情况，所以再方法中直接实例化Array类。

getSize()方法是为了获取队列中元素的个数，所以直接调用array类的getSize()方法即可。isEmpty()方法是为了判断队列中是否为空，所以也就是直接调用Array类中的方法即可。

getCapacity()方法是为了获取队列中的容量，那么是同样的调用Array类的getCapacity方法即可。

第一个方法是入队方法，因为队列的特性是先入先出的，所以添加元素要向队列的对位添加，所以调用Array类的addLast()方法即可，同样的dequeue()方法是需要从队首删除一个元素的，所以调用Array类的removeFirst()方法即可。第三个方法是获取队首的元素并进行返回，因为这个队列是基于数组进行实现的，所以直接适用get()方法，参数传入0即可。

这个方法主要用于进行函数的测试。

注意：实现的队列的方法中出队操作是比较耗时的，虽然在元素个数较少的时候这种时间的消耗可以忽略不计，但是在元素非常多的情况下对效率的影响是很大的，所以接下来我们要对队列进行改进。这就是下面要介绍的循环队列。

创建一个类LoopQueue实现Queue接口，其中包含三个属性，首先是创建了一个E类型的数组data，然后是设置了队首和队尾，第三个是统计队列元素个数的size属性。定义完属性之后再来编写循环队列的构造方法，首先第一个是一个有参的构造方法，参数是整形的capacity，也就是容量。
在方法中首先是将数组data进行初始化，这里可能有人会想，为什么要把容量加1呢？原因是因为循环队列需要有意的浪费一个空间，所以需要将数组的容量设置为用户传入的容量+1，然后将fornt、tail和size都初始化为0。接着是无参构造方法，这里就直接复用有参构造方法将容量设置为10。

getCapacity()方法是为了获取队列的容量，因为在初始化数组时容量设置的比用户传入的容量多1个，所以在这里应该将数组的长度-1，这样便可以计算出队列可用的容量。isEmpty()方法可以通过第五点循环队列的设想看出当数组为空时，front和tail是相等的。getSize()方法就很简单啦，直接返回size即可。

resize()方法用于进行数组的扩容操作，在这里需要传入扩容需要的容量。在方法中首先需要创建一个E类型的数组newData，并将容量传入，具体为什么需要将容量+1，还是因为循环队列需要对1个空间进行浪费。然后对原数组也就是data进行循环，将newData的第1个元素也就是0的位置，赋值为data的front。这里为什么要这么写，也是因为队列是循环的。循环结束后只需要将data指向newData，front赋值为0，tail与元素个数一致即可。

enqueue方法是向队列中添加元素，首先需要判断数组是否为满，因为队列是循环的，所以需要使用 (tail + 1) % data.length == front 计算数组的容量情况，当数组为满时需要进行扩容，这里我就将新的数组扩容为原来的2倍了。然后将e添加到数组中的最后一个位置，然后对tail和size进行维护。

在进行出队方法编写时首先需要判断当前数组是否为空，如果为空就抛出异常。因为需要将出队的元素进行返回，所以先将队首的元素进行保存。然后将队首的元素置为null。然后对front和size进行维护。因为是出队操作，所以可能需要进行缩容的操作，在这里先进行判断如果条件满足的话就将容量缩小至原来的二分之一。最后将保存的结果返回。

getFront()方法非常简单，首先将数组进行判断，如果为空抛出异常。不为空就将数组中的front位置的元素进行返回。

最后为了方便测试，我们将toString方法进行重写，在这里特别要注意的一点就是循环的时候，需要从front位置开始，到tail位置结束，可是因为是循环队列的缘故tail很有可能小于front。那么就使用 i != tail 进行判断，然后对i进行增加。然后将data进行append。最后将res进行返回即可。

java中的“queue类”是什么，有什么作用

java中的queue类是队列数据结构管理类。在它里边的元素可以按照添加它们的相同顺序被移除。\x0d\x0a队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。无论使用哪种排序方式，队列的头都是调用remove()或poll()所移除的元素。在 FIFO 队列中，所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个Queue实现必须指定其顺序属性。\x0d\x0a \x0d\x0aoffer 添加一个元素并返回true 如果队列已满，则返回false\x0d\x0apoll 移除并返问队列头部的元素 如果队列为空，则返回null\x0d\x0apeek 返回队列头部的元素 如果队列为空，则返回null\x0d\x0aput 添加一个元素 如果队列满，则阻塞\x0d\x0atake 移除并返回队列头部的元素 如果队列为空，则阻塞\x0d\x0aelement 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常\x0d\x0a\x0d\x0aadd 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常\x0d\x0aremove 移除并返回队列头部的元素 如果队列为空，则抛出一个\x0d\x0aNoSuchElementException异常\x0d\x0a\x0d\x0a注意：poll和peek方法出错进返回null。因此，向队列中插入null值是不合法的。\x0d\x0a \x0d\x0a还有带超时的offer和poll方法重载，例如，下面的调用：\x0d\x0aboolean success = q.offer(x,100,TimeUnit.MILLISECONDS);\x0d\x0a尝试在100毫秒内向队列尾部插入一个元素。如果成功，立即返回true；否则，当到达超时进，返回false。同样地，调用：\x0d\x0aObject head = q.poll(100, TimeUnit.MILLISECONDS);\x0d\x0a如果在100毫秒内成功地移除了队列头元素，则立即返回头元素；否则在到达超时时，返回null。\x0d\x0a阻塞操作有put和take。put方法在队列满时阻塞，take方法在队列空时阻塞。\x0d\x0a \x0d\x0aQueue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Queue接 口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法 了，而不能直接访问 LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。BlockingQueue 继承了Queue接口。

queue java 是怎么实现的

java中queue的使用
Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Queue接 口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法 了，而不能直接访问 LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。BlockingQueue 继承了Queue接口。

队列是一种数据结构．它有两个基本操作：在队列尾部加人一个元素，和从队列头部移除一个元素就是说，队列以一种先进先出的方式管理数据，如果你试图向一个 已经满了的阻塞队列中添加一个元素或者是从一个空的阻塞队列中移除一个元索，将导致线程阻塞．在多线程进行合作时，阻塞队列是很有用的工具。工作者线程可 以定期地把中间结果存到阻塞队列中而其他工作者线线程把中间结果取出并在将来修改它们。队列会自动平衡负载。如果第一个线程集运行得比第二个慢，则第二个 线程集在等待结果时就会阻塞。如果第一个线程集运行得快，那么它将等待第二个线程集赶上来。下表显示了jdk1.5中的阻塞队列的操作：

add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true 如果队列已满，则返回false
poll 移除并返问队列头部的元素 如果队列为空，则返回null
peek 返回队列头部的元素 如果队列为空，则返回null
put 添加一个元素 如果队列满，则阻塞
take 移除并返回队列头部的元素 如果队列为空，则阻塞

remove、element、offer 、poll、peek 其实是属于Queue接口。

阻塞队列的操作可以根据它们的响应方式分为以下三类：aad、removee和element操作在你试图为一个已满的队列增加元素或从空队列取得元素时 抛出异常。当然，在多线程程序中，队列在任何时间都可能变成满的或空的，所以你可能想使用offer、poll、peek方法。这些方法在无法完成任务时 只是给出一个出错示而不会抛出异常。

注意：poll和peek方法出错进返回null。因此，向队列中插入null值是不合法的。

还有带超时的offer和poll方法变种，例如，下面的调用：
boolean success = q.offer(x,100,TimeUnit.MILLISECONDS);
尝试在100毫秒内向队列尾部插入一个元素。如果成功，立即返回true；否则，当到达超时进，返回false。同样地，调用：
Object head = q.poll(100, TimeUnit.MILLISECONDS);
如果在100毫秒内成功地移除了队列头元素，则立即返回头元素；否则在到达超时时，返回null。

最后，我们有阻塞操作put和take。put方法在队列满时阻塞，take方法在队列空时阻塞。

java.ulil.concurrent包提供了阻塞队列的4个变种。默认情况下，LinkedBlockingQueue的容量是没有上限的（说的不准确，在不指定时容量为Integer.MAX_VALUE，不要然的话在put时怎么会受阻呢），但是也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。
ArrayBlockingQueue在构造时需要指定容量， 并可以选择是否需要公平性，如果公平参数被设置true，等待时间最长的线程会优先得到处理（其实就是通过将ReentrantLock设置为true来 达到这种公平性的：即等待时间最长的线程会先操作）。通常，公平性会使你在性能上付出代价，只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队 列，此队列按 FIFO（先进先出）原则对元素进行排序。
PriorityBlockingQueue是一个带优先级的 队列，而不是先进先出队列。元素按优先级顺序被移除，该队列也没有上限（看了一下源码，PriorityBlockingQueue是对 PriorityQueue的再次包装，是基于堆数据结构的，而PriorityQueue是没有容量限制的，与ArrayList一样，所以在优先阻塞 队列上put时是不会受阻的。虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError），但是如果队列为空，那么取元素的操作take就会阻塞，所以它的检索操作take是受阻的。另外，往入该队列中的元 素要具有比较能力。
最后，DelayQueue（基于PriorityQueue来实现的）是一个存放Delayed 元素的无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于或等于零的值时，则出现期满，poll就以移除这个元素了。此队列不允许使用 null 元素。

java中创建队列Queue的问题

因为queue是接口，不能new 接口，应该new接口实现类，你看jdk文档，搜索queue，如图：

看见下面有一大堆实现queue的类，选一个就行，针对队列的，你可以选LinkedBlockingQueue,AbstrctQueue,ArrayDeque

c++如何查看queue里面的函数原型

queue
queue是STL中现成的队列容器，我们只需要了解他的相关函数及使用方法，即可很方便的帮助我们使用队列这个数据结构。
1.头文件：
#include 《 queue 》
2.变量声明：
queue 《 数据类型 》变量名
例queue 《 int 》a； 即声明了一个int型的队列a
同理，也可声明queue 《 string 》 b; queue 《 struct node 》 c；
3.相关函数：
(1)q.push(x) ：即向队列q的队尾插入数据x
#include《queue》
queue《int》 q;
q.push(5);
cout 《《 q.front() 《《 endl;
1
2
3
1
2
3
(2)q.front()：此函数没有参数，是指返回队首的值(只返回此值，并不从队中删除)
queue《string》 q;
q.push("hello");
q.push("world");
cout 《《 q.front() 《《 endl;
1
2
3
1
2
3
(3)q.pop()：此函数没有参数，指删除队首元素
queue《double》 q;
q.push(5.3);
q.push(8);
cout 《《 q.front() 《《 ’\n’;
q.pop();
cout 《《 q.front() 《《 ’\n’;
1
2
3
4
5
6
1
2
3
4
5
6
(4)q.back()：此函数没有参数，返回队尾元素的值
queue《double》 q;
q.push(5.3);
q.push(8);
cout 《《 q.back() 《《 endl;
1
2
3
1
2
3
(5)q.empty()：此函数没有参数，判断队列是否为空，若队空，则返回真（1）
queue《int》 q;
cout 《《 q.empty() 《《 endl;
q.push("3");
cout 《《 q.empty() 《《 endl;
1
2
3
1
2
3
(6)q.size()：此函数没有参数，返回队列元素个数
queue《double》 q;
q.push(5.3);
q.push(8);
cout 《《 q.size() 《《 ’\n’;
1
2
3
4
1
2
3
4
二、priority_queue

C/C++线程安全型队列的实现

首先，互斥量这种线程相关的内容是平台相关的，我假设你用的是windows平台开发。
其次，说明一下我的开发环境，vs2008，控制台程序，空的工程。
最后给你贴代码，分文件来看。
===头文件QueueNode.h===
===你需要的节点数据可能不是整数，只要将typedef int QUEUEDATA这一句的int换成你想要的类型即可，但要注意，这个类型必须实现赋值操作符重载，相等比较操作符重载，以及复制构造函数===
#ifndef _QUEUE_NODE_H_
#define _QUEUE_NODE_H_
typedef int QUEUEDATA;
typedef struct node
{
QUEUEDATA data;
node* m_pNext;
}QUEUENODE;
#endif
===队列头文件Queue.h，有平台相关内容，请注意===
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include "QueueNode.h"
#include 《Windows.h》
class ThreadSafeQueue
{
public:
ThreadSafeQueue();
virtual ~ThreadSafeQueue();

bool InitQueue();
void EnQueue(const QUEUEDATA& data);
void DeQueue();
void Clear();
const QUEUENODE* Find(const QUEUEDATA& data) const;
void Print();
protected:
HANDLE m_hMutex;
QUEUENODE* m_pQueueHead;
};
#endif
===队列函数实现文件Queue.cpp===
#include "Queue.h"
#include 《iostream》
ThreadSafeQueue::ThreadSafeQueue()
{
m_pQueueHead = new QUEUENODE;
m_pQueueHead-》m_pNext = 0;
}
ThreadSafeQueue::~ThreadSafeQueue()
{
Clear();
delete m_pQueueHead;
CloseHandle(m_hMutex);
}
bool ThreadSafeQueue::InitQueue()
{
m_hMutex = CreateMutex(0, FALSE, 0);
return (m_hMutex!=0);
}
void ThreadSafeQueue::EnQueue(const QUEUEDATA& data)
{
WaitForSingleObject(m_hMutex, INFINITE);
QUEUENODE* pNode = new QUEUENODE;
pNode-》data = data;
pNode-》m_pNext = 0;
QUEUENODE* pTemp = m_pQueueHead;
while (pTemp-》m_pNext != 0)
{
pTemp = pTemp-》m_pNext;
}
pTemp-》m_pNext = pNode;
ReleaseMutex(m_hMutex);
}
void ThreadSafeQueue::DeQueue()
{
WaitForSingleObject(m_hMutex, INFINITE);
QUEUENODE* pNode = m_pQueueHead-》m_pNext;
if (pNode != 0)
{
m_pQueueHead-》m_pNext = pNode-》m_pNext;
delete pNode;
pNode = 0;
}
ReleaseMutex(m_hMutex);
}
const QUEUENODE* ThreadSafeQueue::Find(const QUEUEDATA& data) const
{
WaitForSingleObject(m_hMutex, INFINITE);
QUEUENODE* pNode = m_pQueueHead-》m_pNext;
while (pNode != 0)
{
if (pNode-》data == data)
{
break;
}
pNode = pNode-》m_pNext;
}
return pNode;
ReleaseMutex(m_hMutex);
}
void ThreadSafeQueue::Clear()
{
WaitForSingleObject(m_hMutex, INFINITE);
QUEUENODE* pNode = m_pQueueHead-》m_pNext;
QUEUENODE* pTemp = 0;
while (pNode != 0)
{
pTemp = pNode-》m_pNext;
delete pNode;
pNode = pTemp;
}
m_pQueueHead-》m_pNext = 0;
ReleaseMutex(m_hMutex);
}
void ThreadSafeQueue::Print()
{
WaitForSingleObject(m_hMutex, INFINITE);
QUEUENODE* pNode = m_pQueueHead-》m_pNext;
while (pNode != 0)
{
std::cout 《《 pNode-》data 《《 "\t";
pNode = pNode-》m_pNext;
}
std::cout 《《 std::endl;
ReleaseMutex(m_hMutex);
}
===测试代码文件main.cpp，包含了测试用可执行程序，两个操作queue的线程，需要说明的是，我本来打算用WaitMultipleObjects函数来等待两个线程都结束，但是没搞清楚是什么问题没有卡住，不打算继续纠缠它了，所以让主线程Sleep了5秒钟===
#include "Queue.h"
#include 《iostream》
DWORD WINAPI HandleQueue(void* pParam);
DWORD WINAPI HandleQueue2(void* pParam);
int main()
{
ThreadSafeQueue queue;
queue.InitQueue();
HANDLE hThread = {0};
DWORD threadID = 0;
hThread = CreateThread(NULL, 0, HandleQueue, (void*)(&queue), NULL, &threadID);
hThread = CreateThread(NULL, 0, HandleQueue2, (void*)(&queue), NULL, &threadID);
//WaitForMultipleObjects(2, hThread, TRUE, INFINITE);
Sleep(5000);
queue.Print();
queue.Clear();
return 0;
}
DWORD WINAPI HandleQueue(void* pParam)
{
ThreadSafeQueue* pQueue = reinterpret_cast《ThreadSafeQueue*》(pParam);
for (int i = 0; i 《 100; i++)
{
std::cout 《《 "HandleQueue EnQueue" 《《 std::endl;
pQueue-》EnQueue(i);
}
for (int i = 0; i 《 50; i++)
{
std::cout 《《 "HandleQueue DeQueue" 《《 std::endl;
pQueue-》DeQueue();
}
return 0;
}
DWORD WINAPI HandleQueue2(void* pParam)
{
ThreadSafeQueue* pQueue = reinterpret_cast《ThreadSafeQueue*》(pParam);
for (int i = 0; i 《 100; i++)
{
std::cout 《《 "HandleQueue2 EnQueue" 《《 std::endl;
pQueue-》EnQueue(i+100);
}
for (int i = 0; i 《 50; i++)
{
std::cout 《《 "HandleQueue2 DeQueue" 《《 std::endl;
pQueue-》DeQueue();
}
return 0;
}
新建一个空的控制台程序工程，向工程中加入这几个文件，编译之后可以直接运行。
第一个线程投入队列100个元素，出队50个元素，第二个线程同样。最后主线程输出队列中最后的内容，然后清空。
队列用链表实现，可以试想一下，如果线程同步没有处理，指针操作时一定会引起崩溃

deque java

deque java是什么？一起来看看吧：

deque java是一个双端队列接口，继承自Queue接口，Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque，其中LinkedList是最常用的。

Deque有三种用途：

普通队列(一端进另一端出):
Queue queue = new LinkedList()或Deque deque = new LinkedList()
双端队列(两端都可进出)
Deque deque = new LinkedList()
堆栈
Deque deque = new LinkedList()
注意：Java堆栈Stack类已经过时，Java官方推荐使用Deque替代Stack使用。Deque堆栈操作方法：push()、pop()、peek()。

Deque是一个线性collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的；在大多数实现中，插入操作不能失败。

Deque接口扩展(继承)了 Queue 接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素，从 Queue 接口继承的方法完全等效于 Deque 方法。

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出，堆栈方法完全等效于 Deque 方法。

为什么javaSE不能初始化Queue类型

接口接收实现类，Queue是接口，ArrayDeque是实现类，接口不能实例化就是不能new

Queue《String》 q = new ArrayDeque《String》();

类似的用法还有，比如：

List《String》 list=new ArrayList《String》();