1. Abstract
堆栈是操作受限的线性表：只能在同一端插入和删除（后进先出）
2. 顺序栈（顺序存储）
#define SIZE 100
typedef char StackElemType;
typedef struct{
StackElemType elem[SIZE];
int top;
}SeqStack;
void InitStack(SeqStack *S){
S->top = -1;
}
int Push(SeqStack *S, StackElemType x){
if(S->top >= SIZE-1) return 0;
S->top++;
S->elem[S->top] = x;
return 1;
}
int Pop(SeqStack *S, StackElemType *x){
if(S->top == -1) return 0; // 空栈
*x = S->elem[S->top];
S->top--;
return 1;
}
3. 链栈（链式存储）
3.1 定义
#define SIZE 100
typedef char StackElemType;
typedef struct{
StackElemType data;
struct LinkStackNode *next;
}LinkStackNode, *LinkStack;
void InitLS(LinkStack *top){
*top = (LinkStack *)malloc(sizeof(LinkStackNode));
(*top)->next = NULL;
}
void LSPush(LinkStack top, StackElemType x){
LinkStackNode *n;
n = (LinkStackNode *)malloc(sizeof(LinkStackNode));
n->data = x;
n->next = top->next;
top->next = n;
}
int LSPop(LinkStack top, StackElemType *x){
LinkStackNode *n = top->next;
if(n == NULL) return 0;
top->next = n->next;
*x = n->data;
free(n);
return 1;
}
3.2 多栈运算
把多个链栈的指针放入一个一维指针数组中统一管理，实现同时管理和使用多个栈
LinkStack tops[M];
3.3 应用
输入十进制整数，以八进制形式打印
void Conversion(int N){
LinkStack top;
int x;
InitLS(&top);
while(N > 0){
x = N%8;
LSPush(top, x);
N = N/8l;
}
while(!IsEmpty(top)){
LSPop(top, &x);
printf(" %d", x);
}
}
Document Information
- Author: Zeka Lee
- Link: https://zhekaili.github.io/0011/03/02/(C)Stack/
- Copyright: 自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）