昨天跟一個(gè)CSDN上的朋友聊天，他說(shuō)現(xiàn)在如果讓他自己手寫(xiě)一個(gè)棧或者隊(duì)列，估計(jì)都要寫(xiě)蠻久的，平時(shí)雖然都在用，但是都是別人封裝好的集合。

確實(shí)，經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，包括排序算法，雖然我們平時(shí)不用手寫(xiě)了，但是這些內(nèi)功，作為開(kāi)發(fā)人員來(lái)說(shuō)是必須要掌握的。受此啟發(fā)，我打算更一下經(jīng)典數(shù)據(jù)結(jié)構(gòu)和算法的系列文章。今天先從棧和隊(duì)列說(shuō)起。

這些東西，擠地鐵時(shí)，吃飯排隊(duì)時(shí)，等公交時(shí)，可以拿來(lái)看看，或者，就把它當(dāng)作個(gè)下午茶吧~

我們知道，在數(shù)組中，若知道數(shù)據(jù)項(xiàng)的下標(biāo)，便可立即訪問(wèn)該數(shù)據(jù)項(xiàng)，或者通過(guò)順序搜索數(shù)據(jù)項(xiàng)，訪問(wèn)到數(shù)組中的各個(gè)數(shù)據(jù)項(xiàng)。但是棧和隊(duì)列不同，它們的訪問(wèn)是受限制的，即在特定時(shí)刻只有一個(gè)數(shù)據(jù)項(xiàng)可以被讀取或者被刪除。眾所周知，棧是先進(jìn)后出，只能訪問(wèn)棧頂?shù)臄?shù)據(jù)，隊(duì)列是先進(jìn)先出，只能訪問(wèn)頭部數(shù)據(jù)。這里不再贅述。

棧的主要機(jī)制可以用數(shù)組來(lái)實(shí)現(xiàn)，也可以用鏈表來(lái)實(shí)現(xiàn)，下面用數(shù)組來(lái)實(shí)現(xiàn)棧的基本操作：

classArrayStack{

privatelong[] a;

privateint size;//棧數(shù)組的大小

privateint top;//棧頂

publicArrayStack(int maxSize){

this.size = maxSize;

this.a =newlong[size];

this.top =-1;//表示空棧

}

publicvoid push(long value){//入棧

if(isFull()){

System.out.println("棧已滿(mǎn)！");

return;

}

a[++top]= value;

}

publiclong peek(){//返回棧頂內(nèi)容，但不刪除

if(isEmpty()){

System.out.println("棧中沒(méi)有數(shù)據(jù)");

return0;

}

return a[top];

}

publiclong pop(){//彈出棧頂內(nèi)容，刪除

if(isEmpty()){

System.out.println("棧中沒(méi)有數(shù)據(jù)！");

return0;

}

return a[top--];

}

publicint size(){

return top +1;

}

publicboolean isEmpty(){

return(top ==-1);

}

publicboolean isFull(){

return(top == size -1);

}

publicvoid display(){

for(int i = top; i >=0; i--){

System.out.print(a[i]+" ");

}

System.out.println("");

}

}

數(shù)據(jù)項(xiàng)入棧和出棧的時(shí)間復(fù)雜度均為O(1)。這也就是說(shuō)，棧操作所消耗的時(shí)間不依賴(lài)于棧中數(shù)據(jù)項(xiàng)的個(gè)數(shù)，因此操作時(shí)間很短。棧不需要比較和移動(dòng)操作。

隊(duì)列也可以用數(shù)組來(lái)實(shí)現(xiàn)，不過(guò)這里有個(gè)問(wèn)題，當(dāng)數(shù)組下標(biāo)滿(mǎn)了后就不能再添加了，但是數(shù)組前面由于已經(jīng)刪除隊(duì)列頭的數(shù)據(jù)了，導(dǎo)致空。所以隊(duì)列我們可以用循環(huán)數(shù)組來(lái)實(shí)現(xiàn)，見(jiàn)下面的代碼：

publicclassRoundQueue{

privatelong[] a;

privateint size; //數(shù)組大小

privateint nItems;//實(shí)際存儲(chǔ)數(shù)量

privateint front;//頭

privateint rear; //尾

publicRoundQueue(int maxSize){

this.size = maxSize;

a =newlong[size];

front =0;

rear =-1;

nItems =0;

}

publicvoid insert(long value){

if(isFull()){

System.out.println("隊(duì)列已滿(mǎn)");

return;

}

rear =++rear % size;

a[rear]= value;//尾指針滿(mǎn)了就循環(huán)到0處,這句相當(dāng)于下面注釋內(nèi)容

nItems++;

/* if(rear == size-1){

rear = -1;

}

a[++rear] = value;

*/

}

publiclong remove(){

if(isEmpty()){

System.out.println("隊(duì)列為空！");

return0;

}

nItems--;

front = front % size;

return a[front++];

}

publicvoid display(){

if(isEmpty()){

System.out.println("隊(duì)列為空！");

return;

}

int item = front;

for(int i =0; i < nItems; i++){

System.out.print(a[item++% size]+" ");

}

System.out.println("");

}

publiclong peek(){

if(isEmpty()){

System.out.println("隊(duì)列為空！");

return0;

}

return a[front];

}

publicboolean isFull(){

return(nItems == size);

}

publicboolean isEmpty(){

return(nItems ==0);

}

publicint size(){

return nItems;

}

}

和棧一樣，隊(duì)列中插入數(shù)據(jù)項(xiàng)和刪除數(shù)據(jù)項(xiàng)的時(shí)間復(fù)雜度均為O(1)。

還有個(gè)優(yōu)先級(jí)隊(duì)列，優(yōu)先級(jí)隊(duì)列是比棧和隊(duì)列更專(zhuān)用的數(shù)據(jù)結(jié)構(gòu)。優(yōu)先級(jí)隊(duì)列與上面普通的隊(duì)列相比，主要區(qū)別在于隊(duì)列中的元素是有序的，關(guān)鍵字最小（或者最大）的數(shù)據(jù)項(xiàng)總在隊(duì)頭。數(shù)據(jù)項(xiàng)插入的時(shí)候會(huì)按照順序插入到合適的位置以確保隊(duì)列的順序。優(yōu)先級(jí)隊(duì)列的內(nèi)部實(shí)現(xiàn)可以用數(shù)組或者一種特別的樹(shù)——堆來(lái)實(shí)現(xiàn)。

publicclassPriorityQueue{

privatelong[] a;

privateint size;

privateint nItems;//元素個(gè)數(shù)

publicPriorityQueue(int maxSize){

size = maxSize;

nItems =0;

a =newlong[size];

}

publicvoid insert(long value){

if(isFull()){

System.out.println("隊(duì)列已滿(mǎn)！");

return;

}

int j;

if(nItems ==0){//空隊(duì)列直接添加

a[nItems++]= value;

}

else{//將數(shù)組中的數(shù)字依照下標(biāo)按照從大到小排列

for(j = nItems-1; j >=0; j--){

if(value > a[j]){

a[j+1]= a[j];

}

else{

break;

}

}

a[j+1]= value;

nItems++;

}

}

publiclong remove(){

if(isEmpty()){

System.out.println("隊(duì)列為空！");

return0;

}

return a[--nItems];

}

publiclong peekMin(){

return a[nItems-1];

}

publicboolean isFull(){

return(nItems == size);

}

publicboolean isEmpty(){

return(nItems ==0);

}

publicint size(){

return nItems;

}

publicvoid display(){

for(int i = nItems-1; i >=0; i--){

System.out.print(a[i]+" ");

}

System.out.println(" ");

}

}

這里實(shí)現(xiàn)的優(yōu)先級(jí)隊(duì)列中，插入操作需要 O(N) 的時(shí)間，而刪除操作則需要 O(1) 的時(shí)間。