【数据结构 01】栈

一、原理

栈通常从数据结构和内存空间两个角度解释，从数据结构的角度，栈是一种线性结构表，只允许在固定的一端进行插入和删除元素，从内存空间角度，操作系统为函数和变量分配的内存空间通常在栈区，但是无论是从数据结构还是内存空间角度来看，栈都遵从的原则是：后进先出原则。

栈的特性是顺序存储（随机访问）和后进先出（LIFO：Last In First Out）

• 压栈：栈的插入操作叫做进栈、压栈、入栈，入数据在栈顶
• 出栈：栈的删除操作叫做出栈，出数据也在栈顶

栈的缺陷：

1. 栈空间有容量限制，实现动态扩容的栈在每次插入时都需要检查是否需要扩容，降低了效率。
2. 栈空间的扩容策略可能会导致内存空间浪费。
3. 数据只能从栈顶进行增删，不支持随机增删。

二、Stack.h

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <stdlib.h>#define CAPACITY 4   // 初始容量为4typedef int DataType;typedef struct Stack
{DataType* data;int size;int capacity;
}Stack;void Init(Stack* s)
{s->data = (DataType*)malloc(sizeof(DataType) * CAPACITY);s->size = 0;s->capacity = CAPACITY;
}void CheckCapacity(Stack* s)
{if (s->size == s->capacity){// 栈已满，需要扩容s->data = (DataType*)realloc(s->data, sizeof(DataType) * (s->size + 4));s->capacity += 4;}
}int Empty(Stack* s)
{return s->size == 0;
}void Push(Stack* s, DataType x)
{CheckCapacity(s);s->data[s->size] = x;++s->size;
}void Pop(Stack* s)
{if (Empty(s)){printf("栈为空，pop失败\n");return;}--s->size;
}DataType Head(Stack* s)
{if (Empty(s)){printf("栈为空，无栈顶元素\n");return NULL;}return s->data[s->size - 1];
}void Destroy(Stack* s)
{free(s->data);s->data = NULL;printf("栈已销毁\n");
}void Print(Stack* s)
{if (Empty(s)){printf("栈为空！\n");return;}int i = 0;for (; i < s->size; ++i){printf("%2d ", s->data[i]);}printf("，栈顶元素为：%2d\n", Head(s));
}

三、test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Stack.h"int main()
{Stack s;Init(&s);Push(&s, 1);Push(&s, 3);Push(&s, 5);Push(&s, 7);Push(&s, 2);Push(&s, 4);Push(&s, 6);Push(&s, 8);Print(&s);Pop(&s);Pop(&s);Pop(&s);Print(&s);Push(&s, 20);Print(&s);Pop(&s);Pop(&s);Pop(&s);Pop(&s);Pop(&s);Pop(&s);Pop(&s);Pop(&s);Print(&s);Destroy(&s);
}