Ⅰ 隊列的時間復雜度怎麼算
應該都是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();
}
}