数据结构——栈
栈：后进先出。
只有栈顶元素是可访问的
栈的链表实现
头文件 stack.h
#ifndef _STACK_H
struct Node;
typedef struct Node *PtrToNode;
// Stack本质上就是一个指向Node的指针。
typedef PtrToNode Stack;
typedef int ElementType;
int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S); // dispose部署
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
#endif //DEMO2_STACK_H
源文件stack.c
#include
#include
#include "stack.h"
struct Node {
ElementType Element;
PtrToNode Next;
};
/**
* 检测栈是否为空
* @param S
* @return
*/
int IsEmpty(Stack S) {
return S->Next == NULL;
}
/**
* 创建一个栈
* @return
*/
Stack CreateStack(void) {
Stack S;
S = malloc(sizeof(struct Node));
if (S == NULL) {
printf("Out Of Space");
return S;
}
S->Next = NULL;
MakeEmpty(S);
return S;
}
/**
* 清空一个栈
* @param S
*/
void MakeEmpty(Stack S) {
if (S == NULL) {
printf("use create stack first");
return;
}
while (!IsEmpty(S)) {
Pop(S);
}
}
/**
* 入栈
* @param X
* @param S
*/
void Push(ElementType X, Stack S) {
PtrToNode TmpCell;
TmpCell = malloc(sizeof(struct Node));
if (TmpCell == NULL) {
printf("Out Of Space");
return;
}
TmpCell->Element = X;
TmpCell->Next = S->Next;
S->Next = TmpCell;
}
/**
* 获取栈顶的元素
* @param S
* @return
*/
ElementType Top(Stack S) {
if (!IsEmpty(S)) {
return S->Next->Element;
// Stack S 本身并不存储值，可以理解为S->Next才是栈的顶部Node。
}
return 0;
}
/**
* 出栈
* @param S
*/
void Pop(Stack S) {
PtrToNode FirstCell;
if (IsEmpty(S)) {
printf("stack is empty");
return;
}
FirstCell = S->Next;
S->Next = S->Next->Next;
free(FirstCell);
}