棧的順序存儲及運算

1．棧的順序存儲

　　棧的順序存儲可用向量來實現(xiàn)，即利用一組地址連續(xù)的存儲單元依次存放棧中的各個數(shù)據(jù)元素，又可稱為順序棧。最先 入棧的數(shù)據(jù)元素為棧底，最后入棧的數(shù)據(jù)元素為棧頂。一般將向量的低下標位置作為棧底，并保持不變，棧頂位置隨著元素的進棧和出棧操作而變化。為了方便操 作，通常設(shè)一個標記top標出棧頂元素所在的位置。使用C語言，我們可將順序棧的數(shù)據(jù)類型描述如下：

結(jié)構(gòu)3-1 順序棧

#define Maxsize 100     //假設(shè)棧空間最多為100個元素

typedef char Datatype;  //假設(shè)棧元素的數(shù)據(jù)類型為字符

typedef struct

{ Datatype data[Stacksize];

    int top;

  }Seqstack;

　　該類型包含兩部分內(nèi)容：一是存放棧中數(shù)據(jù)元素的data數(shù)組，另一個是標記棧頂位置的top。在C語言的描述 中，我們可約定data數(shù)組中的data[0]單元不用，并用top=0表示?？眨@也是初始化棧的狀態(tài)。在實際應(yīng)用時，需聲明一個屬于上述類型的棧變 量，即可對此變量進行棧的有關(guān)操作。

　　現(xiàn)假設(shè)有一個棧類型，其最大存儲空間Maxsize為6，s為指向該類型的棧指針，按照約定，棧中可存放的數(shù)據(jù) 元素最多為5個，可存放在s->data[1]至s->data[5]中。初始狀態(tài)下s->top=0，表示棧空，如圖3-2（a）所 示。當(dāng)棧不滿時，可進行進棧操作，當(dāng)棧不空時，可進行出棧操作。若有數(shù)據(jù)元素（A，B，C，D，E）依次進棧，則s->top每次加1，并將元素存 入s->top所標記的位置，棧的狀態(tài)如圖3-2（b）、3-2（c）所示。若有數(shù)據(jù)元素出棧，則刪除s->top標記位置的數(shù)據(jù)元 素，s->top每次減1，如圖3-2（d）所示。

（a）空棧            （b）A進棧           （c）棧滿         （d）E、D出棧

圖3-2 順序棧的狀態(tài)及進棧、出棧操作

　　可見?？蘸蜅M是進行棧操作的兩個限制條件：

　　棧空條件：s->top = 0，此時不能進行出棧操作

　　棧滿條件：s->top = Maxsize -1，此時不能進行進棧操作

2．棧的基本運算的實現(xiàn)

　　算法3-1 初始化

　　棧的初始化即創(chuàng)建一個空棧?？赏ㄟ^指針變量獲取該空棧。算法描述如下： 

void init_seqstack(Seqstack *s)

 { s->top = 0;

 }

　　算法3-2 判?？?/span>

　　對一個已創(chuàng)建的棧判斷其是否為空。若為空，則返回1，否則，返回0，函數(shù)的返回值為整型，參數(shù)為指向已知棧的指針。算法描述如下：

int empty_seqstack (Seqstack *s)

 { if(s->top == 0)

     return 1;

   else 

return 0;

 }

　　算法3-3 判棧滿

　　　對一個已創(chuàng)建的棧判斷其是否為滿。若為滿，則返回1，否則，返回0，函數(shù)的返回值為整型，參數(shù)為指向已知棧的指針。算法描述如下：

int full_seqstack (Seqstack *s)

 { if(s->top == Maxsize-1)

     return 1;

   else 

return 0;

 }

　　算法3-4 進棧

　　將一個新的數(shù)據(jù)元素插入到棧中作為新的棧頂元素。注意插入前首先要判斷棧是否已滿，若棧滿，則不能插入，函數(shù)返回0值，表示插入不成功；若不滿，移動棧頂標記，插入新的數(shù)據(jù)元素，函數(shù)返回1，表示插入成功。算法描述如下：

int push_seqstack(Seqstack *s, Datatype x)

 { if(full_seqstack(s))            //判棧是否為滿

   { printf(″Overflow＼n″);

     return 0;}

  else

   { s->top++;

     (s->data)［s->top］ = x;

     return 1;}

}

　　算法3-5 出棧

　　在已知棧中刪除棧頂元素并將棧頂元素作為返回值。注意在刪除操作之前首先要判斷棧是否為為空，若為空，則不能刪除；若不為空，則返回棧頂元素，移動棧頂標記。算法描述如下：

Datatype pop_seqstack(Seqstack *s,Datatype *x)

 { if(empty_seqstack(s))         //判棧是否為空

     { printf(″Underflow＼n″);     return 0;}

    else

     { &x = (s->data)［s->top］;

s->top--;}

    return  x;

   }

　　算法3-6 取棧頂元素

　　在已知棧中取出棧頂元素并將棧頂元素作為返回值。注意在取出操作之前首先要判斷棧是否為為空，若為空，則無元素可?。蝗舨粸榭?，則返回棧頂元素。算法描述如下：

Datatype gettop_seqstack(Seqstack *s)

 { Datatype  x;

   if(empty_seqstack(s))        //判棧是否為空

     {printf(″Stack is empty.＼n″);

      x = NULL;}

   else

      x = (s->data)［s->top］;

   return x;

}

　　算法3-7 置空

　　將棧的棧頂標記置為初始狀態(tài)，成為空棧。算法描述如下： 

void clear_seqstack(Seqstack *s)

 { s->top = 0;

 }