1.2 堆栈的顺序存储实现和链式存储实现（C语言）

堆栈的存储实现

• • • 堆栈的顺序存储实现源码
    • 运行
    • 堆栈的链式存储实现源码
    • 运行
    • 图解链式入栈

堆栈的顺序存储实现源码

#include #include #define ERROR 0#define N 5  /* 存储空间初始分配量 */typedef struct SNode *Stack;struct SNode {int *Data; /* 存储元素的数组 */int Top;      /* 栈顶指针 */int MaxSize;/* 堆栈最大容量 */};//生成空堆栈，其最大长度为MaxSizeStack CreateStack(int MaxSize){Stack S = (Stack)malloc(sizeof(struct SNode));S->Data = (int *)malloc(MaxSize * sizeof(int));S->Top = -1;S->MaxSize = MaxSize;return S;}//判断堆栈是否已满bool IsFull(Stack S){return (S->Top == S->MaxSize - 1);//等号两边相等就表示已满，返回真(1)，不等于的话就返回假(0)}//将元素X压入堆栈bool Push(Stack S, int X){if (IsFull(S)) {printf("堆栈满");return false;}else {S->Data[++(S->Top)] = X;//-1+1=0，从0开始存储元素return true;}}//判断堆栈S是否为空bool IsEmpty(Stack S){return (S->Top == -1);//空就返回真(1)，不等于的话就反回假(0)}//删除并返回栈顶操作int Pop(Stack S){if (IsEmpty(S)) {printf("堆栈空");return ERROR; /* ERROR是int的特殊值，标志错误 */}elsereturn (S->Data[(S->Top)--]);}/* 返回S的元素个数，即栈的长度 */int StackLength(Stack S){return S->Top + 1;}/* 从栈底到栈顶依次对栈中每个元素显示 */void Stackshow(Stack S){int i=0;if (-1== S->Top) {printf("栈是空的");}elsewhile (i <= S->Top){printf("%d\t ",  S->Data[i++]);}printf("\n");}int main() {Stack s;//结构体指针 int i = 0;s=CreateStack(N);printf("此时Top指向的元素为%d\n", s->Top);printf("此时堆栈s的元素有\n");Stackshow(s);    printf("此时堆栈s的长度为%d\n", StackLength(s));printf("将元素X压入堆栈\n");for (i = 1; i < N; i++) {   printf("将%d压入堆栈s\n",i);Push(s,i);}printf("此时Top指向的元素为%d\n", s->Top);printf("此时堆栈s的元素有\n");Stackshow(s);printf("此时堆栈s的长度为%d\n", StackLength(s));printf("删除并返回栈顶元素\n");for (i = 1; i < N; i++) {printf("将%d从堆栈s删除并返回\n", Pop(s));}return 0;}

运行

此时Top指向的元素为-1此时堆栈s的元素有栈是空的此时堆栈s的长度为0将元素X压入堆栈将1压入堆栈s将2压入堆栈s将3压入堆栈s将4压入堆栈s此时Top指向的元素为3此时堆栈s的元素有1 234此时堆栈s的长度为4删除并返回栈顶元素将4从堆栈s删除并返回将3从堆栈s删除并返回将2从堆栈s删除并返回将1从堆栈s删除并返回

堆栈的链式存储实现源码

#include #include #define ERROR 0#define N 5  /* 存储空间初始分配量 */typedef struct SNode *PtrToSNode;struct SNode {int Data;PtrToSNode Next;//struct SNode *Next; 意义同上};typedef PtrToSNode Stack;typedef struct LinkStack{Stack top;};/*  构造一个空栈S */LinkStack CreateStack(){ /* 构建一个堆栈的头结点，返回该结点指针 */LinkStack S;S.top= (Stack)malloc(sizeof(struct SNode));S.top = NULL;return S;}/* 把S置为空栈 */void ClearStack(LinkStack *S){Stack p, q;p = S->top;while (p){q = p;p = p->Next;free(q);}}bool IsEmpty(LinkStack S){ /* 判断堆栈S是否为空，若是返回true；否则返回false */return (S.top == NULL);}bool Push(LinkStack *S, int X){ /* 将元素X压入堆栈S */PtrToSNode TmpCell;TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));TmpCell->Data = X;TmpCell->Next = S->top; /* 把当前的栈顶元素赋值给新结点的直接后继 */S->top = TmpCell;/* 将新的结点s赋值给栈顶指针 */return true;}int Pop(LinkStack *S){ /* 删除并返回堆栈S的栈顶元素 */PtrToSNode FirstCell= S->top;int TopElem=0;if (IsEmpty(*S)) {printf("堆栈空");return ERROR;}else {TopElem = FirstCell->Data; //记录栈顶元素FirstCell = S->top;  //将栈顶结点赋值给新结点S->top = S->top->Next; //使得栈顶指针下一以为，指向后一结点free(FirstCell);//释放结点return TopElem;}}/* 从栈底到栈顶依次对栈中每个元素显示 */void Stackshow(LinkStack S){Stack p;p = S.top;if (NULL == S.top) {printf("栈是空的");}elsewhile (p){printf("%d\t ",  p->Data);p = p->Next;}printf("\n");}int main() {LinkStack s;//结构体指针 int i = 0;s=CreateStack();ClearStack(&s);printf("此时top指向的元素为%d\n", s.top);printf("此时堆栈s的元素有\n");Stackshow(s);printf("将元素X压入堆栈\n");for (i = 1; i < N; i++) {   printf("将%d压入堆栈s\n",i);Push(&s,i);}printf("此时top指向的元素为%d\n", *s.top);printf("此时堆栈s的元素有\n");Stackshow(s);printf("删除并返回栈顶元素\n");for (i = 1; i < N; i++) {printf("将%d从堆栈s删除并返回\n", Pop(&s));}printf("此时堆栈s的元素有\n");Stackshow(s);return 0;}

运行

此时top指向的元素为0此时堆栈s的元素有栈是空的将元素X压入堆栈将1压入堆栈s将2压入堆栈s将3压入堆栈s将4压入堆栈s此时top指向的元素为4此时堆栈s的元素有4 321删除并返回栈顶元素将4从堆栈s删除并返回将3从堆栈s删除并返回将2从堆栈s删除并返回将1从堆栈s删除并返回此时堆栈s的元素有栈是空的

图解链式入栈

单链表有头指针，而栈顶指针也是必须的，此处把两者合二为一了，把栈顶放在单链表的头部，已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

NICE