昨天跟一個CSDN上的朋友聊天，他說現(xiàn)在如果讓他自己手寫一個?；蛘哧犃?，估計都要寫蠻久的，平時雖然都在用，但是都是別人封裝好的集合。

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

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

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

棧的主要機制可以用數(shù)組來實現(xiàn)，也可以用鏈表來實現(xiàn)，下面用數(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("棧已滿！");

return;

}

a[++top]= value;

}

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

if(isEmpty()){

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

return0;

}

return a[top];

}

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

if(isEmpty()){

System.out.println("棧中沒有數(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ù)項入棧和出棧的時間復(fù)雜度均為O(1)。這也就是說，棧操作所消耗的時間不依賴于棧中數(shù)據(jù)項的個數(shù)，因此操作時間很短。棧不需要比較和移動操作。

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

publicclassRoundQueue{

privatelong[] a;

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

privateint nItems;//實際存儲數(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("隊列已滿");

return;

}

rear =++rear % size;

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

nItems++;

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

rear = -1;

}

a[++rear] = value;

*/

}

publiclong remove(){

if(isEmpty()){

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

return0;

}

nItems--;

front = front % size;

return a[front++];

}

publicvoid display(){

if(isEmpty()){

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

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("隊列為空！");

return0;

}

return a[front];

}

publicboolean isFull(){

return(nItems == size);

}

publicboolean isEmpty(){

return(nItems ==0);

}

publicint size(){

return nItems;

}

}

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

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

publicclassPriorityQueue{

privatelong[] a;

privateint size;

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

publicPriorityQueue(int maxSize){

size = maxSize;

nItems =0;

a =newlong[size];

}

publicvoid insert(long value){

if(isFull()){

System.out.println("隊列已滿！");

return;

}

int j;

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

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("隊列為空！");

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(" ");

}

}

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