堆栈的链式存储实现

堆栈的链式存储结构实际上就是一个单链表,叫做链栈。插入和删除操作只能在链栈的栈顶进行。Top一定在链表的head;

1 typedef struct SNode *Stack;
2 
3 struct SNode {
4 
5   ElementType Data;  //int
6 
7   struct SNode *Next;
8 
9 };

(1)堆栈初始化(建立空栈)

 1 Stack CreateStack() {
 2 
 3   //构建一个堆栈的头结点,返回指针
 4 
 5   Stack S;
 6 
 7   S = (Stack)malloc(sizeof(struct SNode));
 8 
 9   S->Next = NULL;
10 
11   return S;
12 
13 }

(2)判断堆栈S是否为空

1 int IsEmpty (Stack S){
2 
3   //判断堆栈S是否为空,若为空函数返回整数1,否则返回0
4 
5   return (S->Next == NULL);
6 
7 }

(3)入栈(往堆栈的头插入结点)

 1 void Push (ElementType item, Stack S){
 2 
 3   //将元素item压入堆栈S
 4 
 5   struct SNode *T;  //(TmpCell)
 6 
 7   T = (struct SNode *)malloc(sizeof(struct SNode));  //申请结点
 8 
 9   T->Data(Element) = item;  
10 
11   T->Next = S->Next;
12 
13   S->Next = T;
14 
15 }

(4)出栈

 1 ElementType Pop (Stack S) {
 2 
 3   //删除并返回堆栈S的栈顶元素
 4 
 5   struct SNode *FirstCell;
 6 
 7   ElementType TopElem;  //int
 8 
 9   if ( IsEmpty(S) ) {
10 
11     printf("堆栈空");  return NULL;
12 
13   }
14 
15   else {
16 
17     FirstCell = S->Next;
18 
19     S->Next = FirstCell->Next;
20 
21     TopElem = FirstCell->Element;
22 
23     free(FirstCell);
24 
25     return TopElem;
26 
27   }
28 
29 }
原文地址:https://www.cnblogs.com/zhengxin909/p/12527371.html