[算法] 堆栈

顺序存储实现：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 typedef int Position;
 5 typedef int ElementType;
 6 typedef struct SNode *PtrToSNode;
 7 struct SNode {
 8     ElementType *Data;
 9     Position Top;
10     int MaxSize;
11 };
12 typedef PtrToSNode Stack;
13 //创建
14 Stack CreateStack(int MaxSize) {
15     Stack S=(Stack)malloc(sizeof(struct SNode));
16     S->Data=(ElementType*)malloc(MaxSize * sizeof(ElementType));
17     S->Top=-1;
18     S->MaxSize=MaxSize;
19     return S;
20 }
21 //入栈
22 bool IsFull(Stack S) {
23     return(S->Top==S->MaxSize-1);
24 }
25 bool Push(Stack S,ElementType X) {
26     if(IsFull(S)) {
27         printf("堆栈满");
28         return false;
29     } else {
30         S->Data[++(S->Top)]=X;
31         return true;
32     }
33 }
34 //出栈
35 bool IsEmpty(Stack S) {
36     return(S->Top==-1);
37 }
38 ElementType Pop(Stack S) {
39     if(IsEmpty(S)) {
40         printf("堆栈空");
41         return -1;
42     } else
43         return(S->Data[(S->Top)--]);
44 }
45 
46 int main(){
47     Stack st;
48     st = CreateStack(3);
49     Push(st,10);
50     Push(st,20);
51     Push(st,30);
52     printf("%d",Pop(st));
53     printf("%d",Pop(st));
54     printf("%d",Pop(st));
55 }

分析：

1、定义结构体：数组Data[MaxSize]存储数据；Top记录栈顶元素下标；MaxSize记录堆栈容量

2、创建：为栈申请内存；根据容量为数据申请内存；初始化Top

3、入栈、出栈：都在栈顶完成；入栈判满，出栈判空；入栈先加，出栈后减

链式存储实现：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 typedef int ElementType;
 4 typedef struct SNode *PtrToSNode;
 5 struct SNode {
 6     ElementType Data;
 7     PtrToSNode Next;
 8 };
 9 typedef PtrToSNode Stack;
10 //创建 
11 Stack CreateStack() {
12     Stack S;
13     S=(Stack)malloc(sizeof(struct SNode));
14     S->Next=NULL;
15     return S;
16 }
17 
18 bool IsEmpty(Stack S) {
19     return(S->Next==NULL);
20 }
21 //压栈 
22 bool Push(Stack S,ElementType X){
23     PtrToSNode TmpCell;
24     TmpCell=(PtrToSNode)malloc(sizeof(struct SNode));
25     TmpCell->Data=X;
26     TmpCell->Next=S->Next;
27     S->Next=TmpCell; 
28     return true;
29 }
30 //出栈 
31 ElementType Pop(Stack S){
32     PtrToSNode FirstCell;
33     ElementType TopElem;
34     if(IsEmpty(S)){
35         printf("堆栈空");
36         return -1; 
37     }
38     else{
39         FirstCell=S->Next;
40         TopElem=FirstCell->Data;
41         S->Next=FirstCell->Next;
42         free(FirstCell);
43         return TopElem;
44     }
45 }
46 
47 int main() {
48 Stack st;
49 st = CreateStack();
50 Push(st,10);
51 Push(st,20);
52 Push(st,30);
53 printf("%d",Pop(st));
54 printf("%d",Pop(st));
55 printf("%d",Pop(st));
56 }