Ⅰ 队列的时间复杂度怎么算
应该都是O(n).
Ⅱ 数据结构 用循环链表表示的队列长度为n，若只设头指针，则出队和入队时间复杂度分别为多少为什么
1）出队列时间复杂度为O（1），因为头指针指向的是队头。
2）出队列时间复杂度为O（n），因为需要从头指针处移动n-1，此时指针才能指向队尾，O（n-1）是以O（n）来计的。
Ⅲ 简述采用无序链表和有序链表时优先队列入队和出队操作时间复杂度是多少
采用无序链表的队列，无论是直接在表头还是表尾插入，时间复杂度都是O(1) （链表有尾指针）
但是出队时需要从头到尾找最优先元素，因此时间复杂度为O(n)
如果是有序链表，则插入时找插入点的时间复杂度为O(n)
但是直接出链表表头（也就是队头元素）的时间复杂度为O(1)
Ⅳ map，list，queue 插入，删除的时间复杂度各是多少
include <iostream>
#include <stdio.h>
int jc(int m){
if(m!=1) return m*jc(m-1);
else return 1;
}
int c(int m,int n){
if(m>=n) return jc(m)/(jc(n)*jc(m-n));
}
int main(void){
int m,n;
scanf("%d%d",&m,&n);
printf("%d\n",c(m,n));
return 0;
}
Ⅳ 对于一个长度为n的单链存储的队列，在表头插入元素的时间复杂度为___，在表尾插入元素的时间复杂度为__。
题目有问题，既然是队列，怎么会在表头插入元素，表尾入队时间复杂度为O(n)
Ⅵ 如何在C++ STL的queue当中查找一个元素
如果num的范围已知，且空间足够，那么：
bool flg[size] = {false};
每次元素进队时多一步操作：(i为即将入队的值)
q.push(i);
flg[i] = true;
查找的时候只需要参考flg[num]就好。
这样查找比较快，时间复杂度为O(1)。
如果空间不够，或者想知道num在队中的位置，那么把整个队列遍历一遍。
queue<int>tmp;inti=1;
while(!q.empty()){
tmp.push(q.front());
q.pop();
if(tmp.rear==num) cout<<i<<endl;
i++;
}
while(!tmp.empty()){
q.push(tmp.front());
tmp.pop();
}
这样，所有值为num的元素所在的位置都可以知道了。
由于队列是动态的，所占用的空间只会多一点点。但时间复杂度为O(n)。
Ⅶ 从时间复杂度和空间复杂度的两个方面同时分析一下用栈实现队列和用队列实现栈
举例说明，假设我们进行以下4步：
push 1, 2
pop //此时应pop 1
push 3
pop //此时应pop 2
在运行第一个pop时，把A中的1,2全push到B中去，然后再pop得到1，此时B中还剩一个2
下一步push 3，是push到A中
最后一步pop，把B中的2给pop出去
关键点：
(2)如果不为空，则将栈A中所有元素依次pop出并push到栈B；
这里隐含了一点，如果为空，就直接从B中pop，不对A进行任何操作。很显然，需要if..else语句。
弹栈和一般的出栈不同，需要多一部检测B是否为空。
如果B不为空，则直接从B出栈，这时与一般的出栈相同。
如果B为空，则需要把A中所有的元素出栈并压栈到B中去，然后再对B进行一般的出栈操作。
Ⅷ stl中的queue怎么访问队列中某个元素
分析:
queue:队列
特性:只能访问首尾元素
访问接口:push，pop，front，back，queue(复制构造函数)，size，empty
结论:
只能访问首尾元素(访问方式看接口)，中间元素无法访问
如果要访问中间元素，请用其他容器，
vector、list等都可以
Ⅸ 关于队列和时间复杂度的问题
a) 如果只有头指针，且含头结点
1. 出队: O(1)，因为只要把头结点的下一个结点删除就好了
2. 入队: O(n)，要把新的结点插入到队尾，必须把队列历遍，找到队尾，才能插入
b) 如果只有头指针，不含头结点
1. 出队: O(n)，要把头结点删除，必须历遍队列，找到队尾，才能更新头指针 (循环单链的缘故，如果仅仅是普通单链，则本操作也是O(1) )
2. 入队: O(n)，同 (a).2
c) 如果只有尾指针
1. 出队: O(1)，只要把尾指针的下一个结点(没有头结点的情况)或者下下个结点(有头结点的情况)删除即可
2. 入队: O(1)，只要在尾指针的后面插入新的结点，并更新尾结点，所以是O(1)
Ⅹ 如何使用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代码
public
interface
Delayed
extends
Comparable<Delayed>
{
long
getDelay(TimeUnit
unit);
}
放入DelayQueue的元素还将要实现compareTo方法，DelayQueue使用这个来为元素排序。
下面的实例展示了如何使用阻塞队列来控制线程集。程序在一个目录及它的所有子目录下搜索所有文件，打印出包含指定关键字的文件列表。从下面实例可以看出，使用阻塞队列两个显着的好处就是：多线程操作共同的队列时不需要额外的同步，另外就是队列会自动平衡负载，即那边（生产与消费两边）处理快了就会被阻塞掉，从而减少两边的处理速度差距。下面是具体实现：
Java代码
public
class
BlockingQueueTest
{
public
static
void
main(String[]
args)
{
Scanner
in
=
new
Scanner(System.in);
System.out.print("Enter
base
directory
(e.g.
/usr/local/jdk5.0/src):
");
String
directory
=
in.nextLine();
System.out.print("Enter
keyword
(e.g.
volatile):
");
String
keyword
=
in.nextLine();
final
int
FILE_QUEUE_SIZE
=
10;//
阻塞队列大小
final
int
SEARCH_THREADS
=
100;//
关键字搜索线程个数
//
基于ArrayBlockingQueue的阻塞队列
BlockingQueue<File>
queue
=
new
ArrayBlockingQueue<File>(
FILE_QUEUE_SIZE);
//只启动一个线程来搜索目录
FileEnumerationTask
enumerator
=
new
FileEnumerationTask(queue,
new
File(directory));
new
Thread(enumerator).start();
//启动100个线程用来在文件中搜索指定的关键字
for
(int
i
=
1;
i
<=
SEARCH_THREADS;
i++)
new
Thread(new
SearchTask(queue,
keyword)).start();
}
}
class
FileEnumerationTask
implements
Runnable
{
//哑元文件对象，放在阻塞队列最后，用来标示文件已被遍历完
public
static
File
DUMMY
=
new
File("");
private
BlockingQueue<File>
queue;
private
File
startingDirectory;
public
FileEnumerationTask(BlockingQueue<File>
queue,
File
startingDirectory)
{
this.queue
=
queue;
this.startingDirectory
=
startingDirectory;
}
public
void
run()
{
try
{
enumerate(startingDirectory);
queue.put(DUMMY);//执行到这里说明指定的目录下文件已被遍历完
}
catch
(InterruptedException
e)
{
}
}
//
将指定目录下的所有文件以File对象的形式放入阻塞队列中
public
void
enumerate(File
directory)
throws
InterruptedException
{
File[]
files
=
directory.listFiles();
for
(File
file
:
files)
{
if
(file.isDirectory())
enumerate(file);
else
//将元素放入队尾，如果队列满，则阻塞
queue.put(file);
}
}
}
class
SearchTask
implements
Runnable
{
private
BlockingQueue<File>
queue;
private
String
keyword;
public
SearchTask(BlockingQueue<File>
queue,
String
keyword)
{
this.queue
=
queue;
this.keyword
=
keyword;
}
public
void
run()
{
try
{
boolean
done
=
false;
while
(!done)
{
//取出队首元素，如果队列为空，则阻塞
File
file
=
queue.take();
if
(file
==
FileEnumerationTask.DUMMY)
{
//取出来后重新放入，好让其他线程读到它时也很快的结束
queue.put(file);
done
=
true;
}
else
search(file);
}
}
catch
(IOException
e)
{
e.printStackTrace();
}
catch
(InterruptedException
e)
{
}
}
public
void
search(File
file)
throws
IOException
{
Scanner
in
=
new
Scanner(new
FileInputStream(file));
int
lineNumber
=
0;
while
(in.hasNextLine())
{
lineNumber++;
String
line
=
in.nextLine();
if
(line.contains(keyword))
System.out.printf("%s:%d:%s%n",
file.getPath(),
lineNumber,
line);
}
in.close();
}
}