栈的存储结构主要有
栈是计算机科学中的一种数据结构，可以用于实现许多算法和功能，如表达式求值、函数调用等。栈的存储结构主要有两种：顺序栈和链栈。在本文中，我们将从多个角度分析这两种存储结构，包括它们的定义、实现、优缺点以及使用场景。
一、顺序栈
顺序栈，也称为数组栈，是使用数组来实现的栈。它的数据结构比较简单，只需要一个数组和一个指向栈顶元素的指针即可。栈顶指针指向栈顶元素位置的下一个位置，表示栈顶元素不存在。下面是顺序栈的代码实现：
typedef struct Stack
{
int* data;
int top;
int capacity;
}Stack;
void init(Stack* s, int n){
s->data = (int*)malloc(sizeof(int) * n);
s->top = 0;
s->capacity = n;
}
void push(Stack* s, int x){
if(s->top == s->capacity){
printf("The stack is full.\n");
return;
}
s->data[s->top++] = x;
}
int pop(Stack* s){
if(s->top == 0){
printf("The stack is empty.\n");
return -1;
}
return s->data[--s->top];
}
int top(Stack* s){
if(s->top == 0){
printf("The stack is empty.\n");
return -1;
}
return s->data[s->top - 1];
}
int empty(Stack* s){
return s->top == 0;
}
int size(Stack* s){
return s->top;
}
顺序栈的优点在于它的实现简单，访问元素的时间复杂度为O(1)，在元素数量较少、空间复杂度不太敏感的情况下表现良好。但是，它也有一些缺点。首先，顺序栈的大小是固定的，一旦分配的空间不足以容纳新元素，就需要重新分配空间。其次，顺序栈在插入和删除操作时需要移动元素，效率较低。
二、链栈
链栈是使用链表来实现的栈。它的数据结构与顺序栈类似，区别在于每个节点都包含一个指向下一个节点的指针。链栈的代码实现如下：
typedef struct Node
{
int data;
struct Node* next;
}Node;
typedef struct Stack
{
Node* top;
int size;
}Stack;
void init(Stack* s){
s->top = NULL;
s->size = 0;
}
void push(Stack* s, int x){
Node* node = (Node*)malloc(sizeof(Node));
node->data = x;
node->next = s->top;
s->top = node;
s->size++;
}
int pop(Stack* s){
if(s->top == NULL){
printf("The stack is empty.\n");
return -1;
}
int res = s->top->data;
Node* node = s->top->next;
free(s->top);
s->top = node;
s->size--;
return res;
}
int top(Stack* s){
if(s->top == NULL){
printf("The stack is empty.\n");
return -1;
}
return s->top->data;
}
int empty(Stack* s){
return s->top == NULL;
}
int size(Stack* s){
return s->size;
}
链栈的优点在于它可以动态申请内存，并且插入和删除操作不需要移动元素，效率较高。但是，链栈的访问元素时间复杂度为O(n)，在元素数量较多、需要频繁访问栈顶元素的情况下表现不佳。
三、使用场景
顺序栈和链栈各有优缺点，在不同的场景下选择不同的存储结构可以更好地发挥它们的优势。比如，顺序栈适合存储固定大小的数据，如表达式求值中的操作符栈。而链栈适合存储动态的数据，如函数调用中的参数栈。此外，栈还可以用于解决许多其他问题，如括号匹配、回文判断等。
