本文首发于 个人博客
我们都知道函数都是存放在栈上，由系统帮我们管理，那么栈到底是一种什么样的数据结构呢？他是如何管理数据的？ 日常开发中我们或许并没有直接的用上栈这种数据结构，但是它却能帮我们解决一些很棘手的问题，这篇文章主要分享一下个人对栈的理解以及如何用 c去实现一个栈的结构。本文涉及的代码可以前往 示例代码 处查看。
栈结构
我们知道栈其实也是一种线性结构，接下来我们从两种逻辑来实现它，顺序存储 和 链式存储 。
顺序栈
顺序存储通常都要借助于数组，因为数组中的数据在内存中都是连续的，为了方便我们对于栈的查询以及遍历，我们加入一个指向栈顶的元素 top, 那么其数据结构应该是这样：
typedef int Status;
typedef int Data;
typedef struct {
Data data[MAXSIZE];
int top;
}Stack;
其结构很简单，用一个数组能保存栈中每个位置的数据，然后用一个 top 来记录当前栈的顶位于何处，这样我们就能通过一系列的方法对栈进行操作。
// 初始化空栈
Status InitStack (Stack *S) {
S->top = -1;
return SUCCESS;
}
// 清空栈
Status ClearStack (Stack *S) {
S->top = -1;
return SUCCESS;
}
// 判断是否为空栈
bool IsEmpty(Stack S) {
if (S.top == -1) {
return true;
} else {
return false;
}
}
// 返回栈长度
int StackLength(Stack s) {
return s.top+1;
}
// 获取栈顶元素
Status GetStackTop(Stack S,Data *data) {
if (S.top == -1)return ERROR;
*data = S.data[S.top];
return SUCCESS;
}
// 入栈
Status PushData(Stack *S,Data data) {
if (S->top == MAXSIZE-1) return ERROR;
int top = S->top+1;
S->data[top] = data;
S->top++;
return SUCCESS;
}
// 出栈
Status Pop(Stack *S,Data *data) {
if (S->top == -1) return ERROR;
*data = S->data[S->top];
S->top--;
return SUCCESS;
}
// 从栈底到栈顶打印栈
Status PrintStack(Stack S) {
if (S.top == -1) {
printf("空栈 \n");
return ERROR;
}
for (int i = 0; i <= S.top; i ++) {
printf("%d--",S.data[i]);
}
printf("\n");
return SUCCESS;
}
验证
int main(int argc, const char * argv[]) {
// insert code here...
Stack S;
InitStack(&S);
for (int i = 0; i < 10; i ++) {
PushData(&S, i);
}
PrintStack(S);
Data data;
Pop(&S, &data);
PrintStack(S);
printf("出栈的数据是： %d \n",data);
GetStackTop(S, &data);
printf("栈顶的数据是： %d \n",data);
return 0;
}
------------------------打印数据
栈中数据是：0--1--2--3--4--5--6--7--8--9--
栈中数据是：0--1--2--3--4--5--6--7--8--
出栈的数据是： 9
栈顶的数据是： 8
有几个小细节点需要我们注意：
- 线性栈的置空不用清空每个位置的数据，只需要修改 top 即可
- 返回栈的长度不用判断 top = -1 的情况，因为 -1+1 = 0 其最终结果是一样的
其实通过上述实现我们可以发现，栈的处理核心逻辑在于 top 的处理。
链式栈
分析了顺序栈之后我们再来看看链式栈，顾名思义，链式栈用的结构就是链式存储，内部必不可少的用到指针，其在内存中不是连续的，靠的是指针的指向，所以其数据结构可以是这样：
// 栈中每个位置的数据
typedef struct Node {
Data data;
Node *next;
} Node;
// 栈的结构
typedef struct {
Node *top; // 栈顶节点
int count; // 栈的数据量
} Stack;
这里的链式栈的结构就由一个指向栈顶的指针 和 其数据长度构成，栈的指针指向栈顶，由上往下通过 next 指针相连，看起来应该是这样：
根据前面链表的相关内容，我们很容易写出它的相关方法：
// 创建一个空栈
Status InitStack(Stack *S) {
S->top = (Node *)malloc(sizeof(Node));
if (!S->top) return ERROR;
S->top = NULL;
S->count = 0;
return SUCCESS;
}
// 入栈
Status PushData(Stack *S, Data data) {
if (!S) return ERROR;
Node *newTop = (Node *)malloc(sizeof(Node));
newTop->data = data;
newTop->next = S->top;
S->top = newTop;
S->count++;
return SUCCESS;
}
// 出栈
Status Pop(Stack *S,Data *data) {
if (!S) return ERROR;
Node *temp = S->top;
S->top = temp->next;
S->count--;
*data = temp->data;
free(temp);
return SUCCESS;
}
// 获取栈顶元素
Status GetTop(Stack S,Data *data) {
if (S.count == 0) return ERROR;
*data = S.top->data;
return SUCCESS;
}
// 清空栈
Status ClearStack(Stack *S) {
Node *temp = S->top;
while (temp) {
Node *target = temp;
temp = temp->next;
free(target);
}
S->top = NULL;
S->count = 0;
return SUCCESS;
}
// 从栈顶到栈底打印
Status PrintStack(Stack S) {
if (S.count <= 0) return ERROR;
printf("栈的数据从顶到底是：");
Node *temp = S.top;
while (temp) {
printf("%d - ",temp->data);
temp = temp->next;
}
printf("\n");
return SUCCESS;
}
验证
int main(int argc, const char * argv[]) {
// insert code here...
Stack S;
InitStack(&S);
if (InitStack(&S) == SUCCESS) {
for (int i = 1; i < 10; i++) {
PushData(&S, i);
}
}
PrintStack(S);
Data data;
Pop(&S, &data);
PrintStack(S);
printf("出栈的元素是: %d \n",data);
GetTop(S, &data);
printf("栈顶的元素是: %d \n",data);
return 0;
}
--------------------- 打印数据
栈的数据从顶到底是：9 - 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 -
栈的数据从顶到底是：8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 -
出栈的元素是: 9
栈顶的元素是: 8
总结
这篇文章主要讲述了栈的结构以及栈的 顺序存储实现 和 链式存储实现 ，希望能够讲述明白。
网友评论