一挺举、棧
棧是一種限定性的線性表杀赢，只能在棧頂進行插入和刪除操作烘跺。先出后進的線性表湘纵。
二、順序棧
1. 順序棧的結(jié)構(gòu)體設(shè)計
#define MAXSIZE 10//線性表長度的最大值
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
typedef int Status;//狀態(tài)值
typedef int ElemType;//結(jié)點的數(shù)據(jù)類型滤淳，視實際情況而定梧喷。在此以int為例。
typedef struct {
ElemType data[MAXSIZE];
int top;
}SqStack;
2.初始化一個空棧
Status InitStack(SqStack *S) {
S-> top = -1;
return OK;
}
3.清空棧
Status ClearStack(SqStack *S) {
S->top = -1;
return OK;
}
4.棧的長度
棧的長度為：S.top+1
5.獲取棧頂
if(S.top == -1) return ERROR;
*e = S.data[S.top];
return OK;
6.入棧
Status Push(SqStack *S, ElemType e) {
//棧滿脖咐，不能壓棧
if (S->top == MAXSIZE -1) return ERROR;
S->top++;
S->data[S->top] = e;
return OK;
}
7.出棧
Status Pop(SqStack *S, ElemType *e) {
//空棧铺敌，不能出棧
if (S->top == -1) return ERROR;
*e = S->data[S->top];
S->top--;
return OK;
}
8.遍歷
void TraverseStack(SqStack S) {
for (int i = 0; i<=S.top; i++) {
printf("棧元素：%d ",S.data[S.top]);
}
printf("\n");
}
二、鏈式棧
1. 鏈式棧的結(jié)構(gòu)體設(shè)計
//鏈式棧結(jié)點
typedef struct StackNode {
ElemType data;
struct StackNode *next;
}StackNode;
typedef struct StackNode *LinkStackPtr;
//鏈式棧
typedef struct {
LinkStackPtr top;
int count;
}LinkStack;
2.初始化一個空棧
Status InitStack(LinkStack *S) {
S->count = 0;
S->top = NULL;
return OK;
}
3.清空棧
Status ClearLinkStack(LinkStack *S) {
LinkStackPtr p = S->top;
LinkStackPtr temp;
while (p) {
temp = p;
p = p->next;
free(temp);
}
S->count = 0;
return OK;
}
4.棧的長度
棧的長度為：S.count
5.獲取棧頂
S.top->data
6.入棧
Status PushLinkStack(LinkStack *S, ElemType e) {
LinkStackPtr ptr = (LinkStackPtr)malloc(sizeof(StackNode));
ptr->data = e;
ptr->next = NULL;
ptr->next = S->top->next;
S->top->next = ptr;
S->count++;
return OK;
}
7.出棧
Status PopLinkStack(LinkStack *S, ElemType *e) {
//空棧不能出棧
if (S->count == 0) {
return ERROR;
}
*e = S->top->data;
LinkStackPtr p = S->top;
S->top = p->next;
free(p);
S->count--;
return OK;
}
8.遍歷
void TraverseLinkStack(LinkStack S) {
LinkStackPtr p = S.top;
while (p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
