1、棧的結(jié)構(gòu)
棧結(jié)構(gòu)@2x.png
棧結(jié)構(gòu)遵循先進(jìn)后出的原則，進(jìn)棧和出棧都從棧頂進(jìn)行操作；
我們可以用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種方式來實(shí)現(xiàn)棧崔列。
2梢褐、順序存儲(chǔ)實(shí)現(xiàn)棧
2.1代碼準(zhǔn)備
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType類型根據(jù)實(shí)際情況而定旺遮，這里假設(shè)為int */
/* 順序棧結(jié)構(gòu) */
typedef struct
{
SElemType data[MAXSIZE];
int top; /* 用于棧頂指針 ，當(dāng)棧為空時(shí)為-1*/
}SqStack;
2.2 構(gòu)建一個(gè)空棧
Status InitStack(SqStack *S){
S->top = -1;
return OK;
}
2.3 將棧置空
Status ClearStack(SqStack *S){
S->top = -1;
return OK;
}
2.4 判斷順序棧是否為空
Status StackEmpty(SqStack S){
if (S.top == -1)
return TRUE;
else
return FALSE;
}
2.5 返回棧的長度
int StackLength(SqStack S){
return S.top + 1;
}
2.6 獲取棧頂
Status GetTop(SqStack S,SElemType *e){
if (S.top == -1)
return ERROR;
else
*e = S.data[S.top];
return OK;
}
2.7 插入元素e為新棧頂元素
Status PushData(SqStack *S, SElemType e){
//棧已滿
if (S->top == MAXSIZE -1) {
return ERROR;
}
//棧頂指針+1;
S->top ++;
//將新插入的元素賦值給棧頂空間
S->data[S->top] = e;
return OK;
}
2. 8刪除S棧頂元素,并且用e帶回
Status Pop(SqStack *S,SElemType *e){
//空棧,則返回error;
if (S->top == -1) {
return ERROR;
}
//將要?jiǎng)h除的棧頂元素賦值給e
*e = S->data[S->top];
//棧頂指針--;
S->top--;
return OK;
}
2. 9從棧底到棧頂依次對棧中的每個(gè)元素打印
Status StackTraverse(SqStack S){
int i = 0;
printf("此棧中所有元素");
while (i<=S.top) {
printf("%d ",S.data[i++]);
}
printf("\n");
return OK;
}
3盈咳、鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)棧
3.1代碼準(zhǔn)備
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType類型根據(jù)實(shí)際情況而定耿眉，這里假設(shè)為int */
/* 鏈棧結(jié)構(gòu) */
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct
{
LinkStackPtr top;
int count;
}LinkStack;
3.2構(gòu)造一個(gè)空棧
Status InitStack(LinkStack *S)
{
S->top=NULL;
S->count=0;
return OK;
}
3.3把棧置為空棧
Status ClearStack(LinkStack *S){
LinkStackPtr p,q;
p = S->top;
while (p) {
q = p;
p = p->next;
free(q);
}
S->count = 0;
return OK;
}
3.4判斷棧是否為空
Status StackEmpty(LinkStack S){
if (S.count == 0)
return TRUE;
else
return FALSE;
}
3.5棧的長度
int StackLength(LinkStack S){
return S.count;
}
3.6返回棧頂元素
Status GetTop(LinkStack S,SElemType *e){
if(S.top == NULL){
return ERROR;
}else{
*e = S.top->data;
}
return OK;
}
3.7插入元素e到棧
Status Push(LinkStack *S, SElemType e){
//創(chuàng)建新結(jié)點(diǎn)temp
LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
//賦值
temp->data = e;
//把當(dāng)前的棧頂元素賦值給新結(jié)點(diǎn)的直接后繼, 參考圖例第①步驟;
temp->next = S->top;
//將新結(jié)點(diǎn)temp 賦值給棧頂指針,參考圖例第②步驟;
S->top = temp;
S->count++;
return OK;
}
3.8 刪除棧頂元素
Status Pop(LinkStack *S,SElemType *e){
LinkStackPtr p;
if (StackEmpty(*S)) {
return ERROR;
}
//將棧頂元素賦值給*e
*e = S->top->data;
//將棧頂結(jié)點(diǎn)賦值給p,參考圖例①
p = S->top;
//使得棧頂指針下移一位, 指向后一結(jié)點(diǎn). 參考圖例②
S->top= S->top->next;
//釋放p
free(p);
//個(gè)數(shù)--
S->count--;
return OK;
}
3.9 遍歷棧
Status StackTraverse(LinkStack S){
LinkStackPtr p;
p = S.top;
while (p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
return OK;
}
