一、栈
栈是一种限定性的线性表，只能在栈顶进行插入和删除操作。先出后进的线性表。
二、顺序栈
1. 顺序栈的结构体设计
#define MAXSIZE 10//线性表长度的最大值
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
typedef int Status;//状态值
typedef int ElemType;//结点的数据类型，视实际情况而定。在此以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. 链式栈的结构体设计
//链式栈结点
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");
}
