數據結構與算法-棧與隊列

數據結構與算法

(C#語言版)

DataStructure&AlgorithminC#第三章棧與隊列電子信息學院IPLTableofContents第1章緒論第2章線性表第3章棧與隊列第4章串第5章數組和廣義表第6章樹和二叉樹第7章圖第8章查找第9章排序電子信息學院本章位置TableofContents電子信息學院3.0簡介3.1棧的概念及類型定義3.2棧的存儲結構及實現3.3隊列的概念及類型定義3.4隊列的存儲結構及實現3.5遞歸3.0Introduction棧和隊列是兩種特殊的線性結構。它們的數據元素之間具有順序的邏輯關系，都可以采用順序存儲結構和鏈式存儲結構。線性表的插入和刪除操作不受限制，可以在任意位置進行。棧的插入和刪除操作只允許在表的一端進行。隊列的插入和刪除操作則分別在表的兩端進行。棧的特點是后進先出(LIFO)

，隊列的特點是先進先出(FIFO)

。3.1棧的概念及類型定義棧是一種“后進先出”（LastInFirstOut，LIFO）的線性結構。棧就像某種只有單個出入口的倉庫，每次只允許一件件地往里面堆貨物（入棧），然后一件件地往外取貨物（出棧），不允許從中間放入或抽出貨物。3.1.1棧的基本概念3.1.2棧的抽象數據類型3.1.3C#中的棧類3.1.1棧的定義棧（stack）是一種特殊的線性數據結構，其插入和刪除操作只允許在數據結構的一端進行。LIFO。棧中插入數據元素的過程稱為入棧(push)，刪除數據元素的過程稱為出棧(pop)。允許操作的一端稱為棧頂（top），不允許操作的一端稱為棧底（bottom）。棧頂指針：標識棧頂的當前位置（動態(tài)）。3.1.2棧的抽象數據類型棧的數據元素是由n(n≥0)個數據元素a0，a1，a2，…，an-1組成的有限序列。棧記作：Stack={a0，a1，a2，…，an-1}棧中的數據元素至少具有一種相同的屬性，屬于同一種抽象數據類型。n表示棧中數據元素的個數，稱為棧的長度。若n=0，則稱為空棧。棧的基本操作Initialize:棧的初始化。創(chuàng)建一個棧，并進行初始化操作，例如設置棧狀態(tài)為空。Count:返回棧中元素個數。Empty/Full:判斷棧的狀態(tài)是否為空或滿。Push:入棧。該操作將數據元素插入棧中作為新的棧頂元素。Pop:出棧。該操作取出當前棧頂數據元素，下一個數據元素成為新的棧頂元素。Peek:獲得但不移除棧頂數據元素。棧頂指針不變。3.1.3C#中的棧類在System.Collections名字空間中定義了一個棧類Stack，提供一種數據后進先出的集合，其數據元素的類型是object類。Stack類的屬性和方法：

公共構造函數Stack();

//初始化Stack類的新實例Stack(ICollectionc);Stack(intcapacity);virtualintCount{get;}

//獲取包含在棧中的元素數公共屬性Stacks1=newStack();Stacks2=newStack(30);1.非泛型棧類StackStack的公共方法virtualvoidPush(objectobj);

//將對象插入棧的頂部virtualobjectPop();

//移除并返回位于棧頂部的對象virtualobjectPeek();

//返回棧頂的對象，但不將其移除virtualboolContains(objectobj);

//確定某個元素是否在棧中2.泛型棧類Stack<T>2.0版C#語言增加了泛型（Generics）。泛型通常與集合一起使用。

新的命名空間System.Collections.Generic，它包含定義泛型集合的接口和類，泛型集合允許用戶創(chuàng)建強類型集合，它能提供比非泛型集合更好的類型安全性和性能?！纠?.1】創(chuàng)建Stack對象，向其添加值以及打印出其值usingSystem;using

System.Collections;StackmyStack=newStack();myStack.Push("Hello");myStack.Push("World");myStack.Push("!");Console.WriteLine("myStack");Console.WriteLine("\tCount:{0}", myStack.Count);Console.Write("\tValues:\n");foreach(objectoinmyStack)Console.WriteLine("\t{0}",o);程序運行結果

myStackCount:3Values:!WorldHello

【例3.2】利用棧進行數制轉換N=an×dn+an-1×dn-1

+...+a1×d1

+a0N=(N/d)×d+N%d例如：（2468)10

轉換成(4644)8

的運算過程如下：NN/8N%8計算順序輸出順序24683084

308384

3846

404usingSystem;usingSystem.Collections.Generic;namespacestackqueuetest{public

class

DecOctConversion{

public

static

voidMain(string[]args){

intn=2468;Stack<int>s=new

Stack<int>(20);

Console.Write("十進制數:{0}->八進制:",n);

while(n!=0){ s.Push(n%8); n=n/8; }

inti=s.Count;

while(i>0){

Console.Write(s.Pop());i--; }

Console.WriteLine(); }}}3.2棧的存儲結構及實現棧作為一種特殊的線性結構，可以如同一般線性表一樣采用順序存儲結構和鏈式存儲結構實現。順序存儲結構的棧稱為順序棧（SequencedStack），鏈式存儲結構的棧稱為鏈式棧（LinkedStack）。3.2.1棧的順序存儲結構及操作實現3.2.2棧的鏈式存儲結構及操作實現3.2.3棧的應用舉例3.2.1棧的順序存儲結構及操作實現public

class

SequencedStack<T>{

privateT[]items;

private

const

intempty=-1;

private

inttop=empty;

……}SequencedStack類的對象就是一個棧實例。通過對這個對象調用公有的屬性和方法訪問類中成員或進行相應的操作。成員變量items用數組存儲棧的數據元素，成員變量top指示當前棧頂數據元素的下標。順序棧的操作棧的初始化返回棧的元素個數判斷棧的空與滿狀態(tài)入棧：當棧不滿時，棧頂元素下標top加1，將k放入top位置，作為新的棧頂數據元素。出棧：當棧不空時，取走top處的元素，top減1，下一位置的數據元素作為新的棧頂元素。獲得棧頂數據元素的值。當棧非空時，獲得top位置處的數據元素，此時該數據元素未出棧，top值不變。1）棧的初始化構造方法初始化一個棧對象，它申請items數組的存儲空間來存放棧的數據元素，設置棧初始狀態(tài)為空。publicSequencedStack(intn){items=newT[n];top=empty;}publicSequencedStack():this(16){}2）返回棧的元素個數將返回棧的元素個數的成員定義為屬性，相對于成員方法顯得更簡潔。public

intCount{

get{returntop+1; }}

3）判斷棧的空與滿狀態(tài)當top==empty時，棧為空狀態(tài)；當top≥items.Length-1時，棧為滿狀態(tài)。public

bool

Empty{

get{

returntop==empty;

}}public

bool

Full{

get{return

top>=items.Length-1;

}}4）入棧當棧不滿時，棧頂元素下標top加1，將k放入top位置，作為新的棧頂元素。入棧的數據是T類型，在調用該操作時，參數的類型要與棧定義時聲明的類型保持一致。當棧當前分配的存儲空間已裝滿數據元素，在進行后續(xù)的操作前，需要調用DoubleCapacity方法重新分配存儲空間，并將原數組中的數據元素逐個拷貝到新數組。

public

voidPush(Tk){

if(Full)DoubleCapacity();top++;items[top]=k;}重新分配存儲空間private

voidDoubleCapacity(){

intcount=Count;

intcapacity=2*items.Length;T[]copy=newT[capacity];

for(inti=0;i<count;i++)copy[i]=items[i];items=copy;}當棧不滿時，Push操作的時間復雜度為O(1)。如果需要增加容量以容納新元素，則Push操作的時間復雜度成為O(n)。5）出棧當棧不空時，取走top位置處的元素，top減1，下一位置上的元素成為新的棧頂元素。出棧的數據元素具有類型T，在調用該操作時，將與棧定義時聲明的類型保持一致。此方法的運算復雜度是O(1)。publicTPop(){Tk=default(T);

if(!Empty){ //棧不空k=items[top]; //取得棧頂元素top--;

returnk;}else

//棧空時產生異常

throw

new

InvalidOperationException();}6）獲得棧頂數據元素的值當棧非空時，獲得top位置處的元素，此時該數據未出棧，top值不變。public

TPeek(){

if(!Empty)

returnitems[top];

else

newInvalidOperationException();}

7）輸出棧中每個數據元素的值當棧非空時，從棧頂結點開始，直至棧底結點，依次輸出結點值。public

voidShow(boolshowTypeName){if(showTypeName)Console.Write(“Stack:”);if(!Empty){for(inti=this.top;i>=0;i--){Console.Write(items[i]+“”);}Console.WriteLine();}}【例3.3】使用順序棧的基本操作編譯并運行SequencedStackTest.cs，運行時從命令行輸入參數：

>cscSequencedStackTest.cs/r:..\stackqueue\bin\Debug\stackqueue.dll

>SequencedStackTestabc運行結果如下：Push:abcstack:cbaPush:12stack:21cbaPop:21stack:cbaPush:34stack:43cbaPop:43stack:cbaPop:cba

3.2.2棧的鏈式存儲結構及操作實現usinglists;public

class

LinkedStack<T>:

SingleLinkedList<T>{private

SingleLinkedNode<T>top;……}

鏈式棧的操作棧的初始化判斷棧的空與滿狀態(tài)返回棧的元素個數入棧出棧獲得棧頂數據元素的值，該數據元素未出棧。LinkedStack類的一個對象就是一個棧。成員變量top指向棧頂數據元素結點，結點類型為單向鏈表的結點類SingleLinkedNode，結點數據域的類型為泛型T。1）棧的初始化用構造方法創(chuàng)建一個棧，它用基類（SingleLinkedList類）的構造方法創(chuàng)建一條單向鏈表，棧的狀態(tài)初始為空。publicLinkedStack():base(){top=base.Head.Next;}2）返回棧的元素個數由基類SingleLinkedList繼承的公共屬性Count即可完成返回棧的元素個數的功能。3）判斷棧的空與滿狀態(tài)當top==null時，棧為空；動態(tài)向系統(tǒng)申請存儲空間，不必判斷棧是否已滿。public

override

boolEmpty{

get{returntop==null;}}

與前面比較，可以體會到面向對象程序設計帶來的便利。導出類既可以直接繼承基類的屬性和方法（子類與父類有相同的行為），也可以重寫基類的屬性和方法（子類有與父類不同的行為，但行為的命名是相同的）4）入棧在棧頂結點top之前插入一個結點來存放數據k，并使top指向新的棧頂結點。public

voidPush(Tk){

SingleLinkedNode<T>q=new

SingleLinkedNode<T>(k);q.Next=top;//q結點作為新的棧頂結點top=q;

base.Head.Next=top;}5）出棧當棧不為空時，取走top指向的棧頂結點的值，刪除該結點，使top指向新的棧頂結點。publicTPop(){Tk=default(T);if(!Empty){//棧不空k=top.Item;//取得棧頂數據元素值top=top.Next;//刪除棧頂結點base.Head.Next=top;

returnk;}else

//?？諘r產生異常throw

new

InvalidOperationException();}6）獲得棧頂數據元素的值當棧非空時，獲得棧頂top的數據，此時該數據元素未出棧，top值不變。public

intPeek(){if(!Empty)return

top.Item;else

thrownewInvalidOperationException();}

鏈式棧的基本操作3.2.3棧的應用舉例基于棧結構的方法嵌套調用判斷表達式中括號是否匹配使用棧計算表達式的值1）基于棧結構的方法嵌套調用程序中方法的嵌套調用是指在程序運行時，一個方法中可以調用另一個方法，每個方法在執(zhí)行完后應返回到調用它的方法中。系統(tǒng)建立一個棧結構可以實現這種函數嵌套調用機制。執(zhí)行方法A時，A中的某語句又調用方法B，系統(tǒng)要做一系列的入棧操作：將調用語句后的下一條語句作為返回地址信息保存在棧中，該過程稱為保護現場；將A調用方法B的實參保存在棧中，該過程稱為實參壓棧；在棧中分配方法B的局部變量。子過程返回B方法執(zhí)行完成時，系統(tǒng)則要做一系列的出棧操作才能保證將系統(tǒng)控制返回調用B的方法A中退回棧中為方法B的局部變量分配的空間；退回棧中為方法B的參數分配的空間；取出保存在棧中的返回地址信息，該過程稱為恢復現場，程序繼續(xù)運行A方法。方法調用的次序與返回的次序正好相反?？梢姡到y(tǒng)棧結構是實現嵌套調用或遞歸調用的基礎。方法嵌套調用時的系統(tǒng)棧2）判斷表達式中括號是否匹配如表達式中

（［］（））或［（［］［］）］等為正確的匹配，

［（］）或（［（）]

或

[()])均為不正確的匹配。檢驗括弧匹配的方法可用“按期待的急迫程度進行處理”描述之。括弧匹配遵循后進先出規(guī)律如何表示下列“不匹配”

的情況？到來的右括弧非是所“期待”的;來了一個“不速之客”;直到結束，也沒有等到“期待”的匹配;括弧匹配算法的設計思想1）凡出現左括弧(，則進棧；2）凡出現右括弧)，首先檢查棧是否空？若?？?，則表明該“右括弧)”多余否則和棧頂元素比較，若相匹配，則“左括弧(出棧”否則表明不匹配3）表達式檢驗結束時，若?？?，則表明表達式中匹配正確否則表明“左括弧(”有余。public

static

stringMatchingBracket(stringexpstr){

SequencedStack<char>s1=new

SequencedStack<char>(30);//創(chuàng)建空棧charNextToken,OutToken;inti=0;boolLlrR=true;while(LlrR&&i<expstr.Length){NextToken=expstr[i];i++;switch(NextToken){case‘('://遇見左括號時,入棧s1.Push(NextToken);break;case

‘)’://遇見右括號時,出棧if(s1.Empty)LlrR=false;else{OutToken=s1.Pop();if(!OutToken.Equals(‘(’))LlrR=false;//判斷出棧的是否為左括號}break;}}if(LlrR)if(s1.Empty)return

“OK!”;elsereturn

“期望)!”;elsereturn

“期望(!”;}3）表達式求值設Exp=S1+OP+S2則稱OP+S1+S2

為前綴表示法S1+OP+S2

為中綴表示法

S1+S2+OP

為后綴表示法3）中綴式丟失了括弧信息，致使運算的次序被改變;4)前綴式的運算規(guī)則為:

連續(xù)出現的兩個操作數和在它們之前且緊靠它們的運算符構成一個最小表達式;5)后綴式的運算規(guī)則為:運算符出現的順序恰為表達式的運算順序;每個運算符和在它之前出現且緊靠它的兩個操作數構成一個最小表達式;例如:

Exp=a

b

+

(c

d/e)

f前綴式:

+

ab

c/def中綴式:

a

b

+

c

d/e

f后綴式:

ab

cde/

f

+結論:1）操作數之間的相對次序不變;2）運算符的相對次序不同;如何從后綴式求值？先找運算符，再找操作數例如：

ab

cde/

f

+a

bd/ec-d/e(c-d/e)

f如何從原表達式求得后綴式？

在后綴式中，優(yōu)先權高的運算符領先于優(yōu)先權低的運算符出現。分析“原表達式”和“后綴式”中的運算符:原表達式:

a+b

c

d/e

f

后綴式:

abc

+de/f

每個運算符的運算次序要由它之后的一個運算符來定。從原表達式求得后綴式的規(guī)律1)設立暫存運算符的棧OPTR和暫存操作數的棧OPND2)設表達式的結束符為“#”,

予設運算符棧的棧底為“#”3)若當前字符是操作數，則進入棧OPND;4)若當前運算符的優(yōu)先數高于棧頂運算符，則進棧;5)否則，退出棧頂運算符發(fā)送給后綴式;6)“(”對它之前后的運算符起隔離作用，“)”可視為自相應左括弧開始的表達式的結束符。a(b(c+d/e)-f)##a

(b

(c+d

/e

/

/++

-f-

#3.3隊列的概念及類型定義3.3.1隊列的基本概念3.3.2隊列的抽象數據類型3.3.3C#中的隊列類3.3.1隊列的基本概念隊列(queue)是一種特殊的線性表，其插入和刪除操作分別在表的兩端進行?！跋冗M先出”（FirstInFirstOut，FIFO）的線性結構。向隊列中插入元素的過程稱為入隊(enqueue)，刪除元素的過程稱為出隊（dequeue）。允許入隊的一端為隊尾（rear），允許出隊的一端為隊頭（front）。3.3.2隊列的抽象數據類型隊列的數據元素是由n(n≥0)個相同抽象類型的數據元素a0，a1，a2，…，an-1組成的有限序列。隊列記為：

Queue={a0，a1，a2，…，an-1}n表示隊列的元素個數，稱為隊列的長度，若n=0，則稱為空隊列。隊列的基本操作Initialize:隊列的初始化。創(chuàng)建一個隊列，并進行初始化操作。Count:返回隊列中元素個數。Empty: 判斷隊列的狀態(tài)是否為空。Full:判斷隊列的狀態(tài)是否已滿。Enqueue:入隊。該操作將數據加入隊列隊尾處。在入隊前須判斷隊列的狀態(tài)是否已滿。Dequeue:出隊。該操作取出隊頭元素。在出隊前，須判斷隊列的狀態(tài)是否為空。Peek:獲得但不移除隊首數據元素。3.3.3C#中的隊列類在System.Collections名字空間中定義了一個隊列類Queue，提供了一種數據先進先出的集合，其數據元素的類型是object類。Queue類的屬性和方法：

公共構造函數Queue();

//初始化Queue類的新實例Queue(ICollectionc);Queue(intcapacity);virtualintCount{get;}

//獲取包含在隊列中的元素數公共屬性Queueq=newQueue();1.非泛型隊列類QueueQueue的公共方法virtualvoidEnqueue(objectobj);

//將對象添加到Queue的結尾virtualobjectDequeue();

//移除并返回位于Queue開始處的對象virtualobjectPeek();

//返回隊頭處的對象但不將其移除。virtualboolContains(objectobj);

//確定某個元素是否在隊列中【例3.5】創(chuàng)建Queue對象，向其添加值并打印出其值usingSystem;using

System.Collections;QueuemyQ=newQueue();myQ.Enqueue("Hello");myQ.Enqueue("World");myQ.Enqueue("!");Console.WriteLine("myQ");Console.WriteLine("\tCount:{0}",myQ.Count);Console.Write("\tValues:");foreach(objectoinmyQ)Console.Write("{0}\t",o);Console.WriteLine();myQCount:3Values:HelloWorld!

程序運行結果：2.泛型隊列類Queue<T>2.0版C#語言增加了泛型（Generics）。泛型通常與集合一起使用。

新的命名空間System.Collections.Generic，它包含定義泛型集合的接口和類，泛型集合允許用戶創(chuàng)建強類型集合，它能提供比非泛型集合更好的類型安全性和性能。Queue<int>q=newQueue<int>();q.Enqueue(14);3.4隊列的存儲結構及實現隊列作為一種特殊的線性表，可以如同棧和一般線性表一樣采用順序存儲結構和鏈式存儲結構實現。順序存儲結構的隊列稱為順序隊列，鏈式存儲結構的隊列稱為鏈式隊列。3.4.1隊列的順序存儲結構及操作實現3.4.2隊列的鏈式存儲結構及操作實現3.4.3隊列的應用舉例3.4.1隊列的順序存儲結構及操作實現public

class

SequencedQueue<T>{

privateT[]items;

private

intfront,rear;……}隊列的順序存儲結構用一組連續(xù)的存儲空間存放隊列的數據元素。成員變量items用數組存儲隊列的數據元素，成員變量front和rear分別作為隊頭元素下標和下一個入隊數據元素位置的下標，構成隊頭指針和隊尾指針。順序隊列“假溢出”設先有(a，b，c)入隊，那么front=0，rear=3。接著a和b出隊，d和e入隊，front=2，rear=5。如果再有數據入隊，應存放于rear=5位置處，數組下標溢出。順序隊列因多次入隊和出隊操作后出現的有存儲空間但不能進行入隊操作的溢出稱為假溢出。假溢出缺陷是因為順序隊列沒有重復使用存儲單元的機制。解決辦法是將順序隊列設計成“環(huán)形”結構。順序循環(huán)隊列front=(front+1)%items.Length；rear=(rear+1)%items.Length；

順序循環(huán)隊列的操作隊列的初始化返回隊列的元素個數判斷隊列的空與滿狀態(tài)入隊出隊獲得隊首對象，但不將其移除1）隊列的初始化構造方法初始化一個隊列對象，它申請items數組的存儲空間準備存放隊列的數據元素，設置隊列初始狀態(tài)為空。publicSequencedQueue(intn){items=newT[n+1];front=rear=0;}publicSequencedQueue():this(16){}2）返回隊列中元素的個數public

intCount{

get{

return

(rear-front

+

items.Length)

%

items.Length;} }

3）判斷隊列的空與滿狀態(tài)當front==rear時，隊列為空；當front==(rear+1)%items.Length時，隊列已滿，此時items數組中仍有一個空位置。public

boolEmpty{

get{returnfront==rear;}}

public

boolFull{

get{return

front==(rear+1)%items.Length;}}

4）入隊當隊列不滿時，將對象k存放在rear位置，作為新的隊尾數據元素，rear循環(huán)加1。入隊的數據元素是T類型，在調用該操作時，參數的類型要與隊列定義時聲明的類型保持一致。當隊列當前分配的存儲空間已裝滿數據元素，在進行后續(xù)的操作前，需要重新分配存儲空間，將原數組中的數據元素逐個拷貝到新數組，并相應調整隊首與隊尾指針。public

voidEnqueue(Tk){

if(Full)DoubleCapacity();items[rear]=k;rear=(rear+1)%items.Length;}重新分配存儲空間private

voidDoubleCapacity(){

inti,j,count=Count;

intcapacity=2*items.Length-1;

T[]copy=newT[capacity];

for(i=0;i<count;i++){

j=(i+front)%items.Length;copy[i]=items[j];}front=0;

rear=count;

items=copy;

}當隊列不滿時，Enqueue方法為O(1)操作。如果需要重新分配內部數組以容納新元素，則此方法成為O(n)操作。5）出隊當隊列不空時，取走front位置上的隊首元素，front循環(huán)加1，指向新的隊首元素。運算復雜度是O(1)。publicTDequeue(){Tk=default(T);

if(!Empty){//隊列不空k=items[front];front=(front+1)%items.Length;returnk;}else//?？諘r產生異常throw

newInvalidOperationException();}6）獲得隊首對象獲得但不移除隊首對象。當隊列不為空時，取走front位置上的隊首數據，front不變。publicTPeek(){if(!Empty)returnitems[front];else

throw

new

InvalidOperationException();}順序循環(huán)隊列小結入隊時只改變下標rear，出隊時只改變下標front，它們都做循環(huán)移動，取值范圍是0~items.Length-1，這使得存儲單元可以重復使用，避免“假溢出”現象。在隊列中設立一個空位置。如果不設立一個空位置，則隊列滿的條件也是front==rear，那么就無法與隊列空的條件（front==rear）相區(qū)別。而設立一個空位置，則隊列滿的條件是

front==(rear+1)%items.Length3.4.2隊列的鏈式存儲結構及操作實現public

class

LinkedQueue<T>{

private

SingleLinkedList<T>items;

private

SingleLinkedNode<T>front,rear;}

LinkedQueue類的一個對象就是一個隊列。成員變量front和rear分別指向隊頭和隊尾結點，結點類型為單鏈表節(jié)點類SingleLinkedNode<T>。鏈式隊列隊列的操作隊列的初始化返回隊列的元素個數判斷隊列的空與滿狀態(tài)入隊出隊獲得隊首對象1）隊列的初始化構造方法創(chuàng)建一條單向鏈表用作隊列，設置初始狀態(tài)為空。publicLinkedQueue(){items=new

SingleLinkedList<T>();front=items.Head.Next;

rear=items.Head;}2）返回隊列中元素的個數public

intCount{

get{

returnitems.Count;}}

3）判斷隊列的空與滿狀態(tài)當front==null且rear==items.Head時，隊列為空；不需要判斷隊列是否已滿。public

boolEmpty{

get{return(front==null)&&(rear==items.Head);}}4）入隊在rear指向的隊尾結點之后插入一個結點存放k，并使rear指向新的隊尾結點。此時入隊的數據元素是T類型，在調用該操作時，參數的類型要與隊列定義時聲明的類型保持一致。此方法的運算復雜度是O(1)。public

voidEnqueue(Tk){

SingleLinkedNode<T>q=new

SingleLinkedNode<T>(k);rear.Next=q;front=items.Head.Next;rear=q;}5）出隊當隊列不為空時，取走front指向的隊首結點的數據元素，并刪除該結點，使front指向新的隊首結點。此時出隊的數據元素具有類型T，在調用該操作時，將與隊列定義時聲明的類型保持一致。此方法的運算復雜度是O(1)。publicTDequeue(){Tk=default(T);if(!Empty){//隊列不空k=front.Item;//取得隊頭結點數據元素front=front.Next;//刪除隊頭結點items.Head.Next=front;if(front==null)

rear=items.Head;returnk;}elsethrow

new

Invali