目录
栈（stack）是一种线性数据结构，采用后进先出（Last In First Out）的原则，即最后一个进入栈的元素最先被取出。栈的常用操作有：push（入栈），pop（出栈），isEmpty（判断栈是否为空），peek（查看栈顶元素）。它具有“先进后出”的特点。栈通过顶部进行操作，只能在栈顶进行插入和删除操作，因此也被称为“后进先出（LIFO）”的结构。
栈的应用非常广泛，比如在编程中可以用来实现函数调用、表达式求值、括号匹配等；在计算机系统中可以用来实现系统调用、内存分配等。
常见的栈实现方式有数组和链表两种，其中数组实现的栈又称为顺序栈，链表实现的栈称为链式栈。
void InitStack(SqStack *S)
{
S->top = -1; // 栈顶指针初始化为-1，表示栈为空
}
void DestroyStack(SqStack *S)
{
free(S); // 释放栈空间
}
在 push 操作时，将元素插入数组中，并将栈顶指针加一；在 pop 操作时，将栈顶指针减一并返回栈顶元素。
bool Push(SqStack *S, int x)
{
if (S->top == MAX_SIZE-1) // 栈满，无法插入新元素
return false;
S->top++; // 栈顶指针+1
S->data[S->top] = x; // 新元素入栈
return true;
}
栈的删除操作指的是从栈中弹出元素的操作。由于栈是一种“后进先出”的数据结构，因此删除的元素总是栈顶元素。
栈的删除操作可以使用 pop() 方法来实现。pop() 方法会弹出并返回栈顶元素，同时将栈顶指针指向下一个元素。如果栈为空，则弹出操作会抛出异常。
bool Pop(SqStack *S, int *x)
{
if (S->top == -1) // 栈为空，无法弹出栈顶元素
return false;
*x = S->data[S->top]; // 栈顶元素出栈
S->top--; // 栈顶指针-1
return true;
}
在C语言中通过数组实现栈的操作，我们可以通过下标来获取栈顶元素。假设我们定义了一个栈数组stack和一个栈顶指针top，那么获得栈顶元素的方法如下：
bool GetTop(SqStack S, int *x)
{
if (S.top == -1) // 栈为空，无法获取栈顶元素
return false;
*x = S.data[S.top]; // 获取栈顶元素
return true;
}
这个函数接收栈数组和栈顶指针作为参数，如果栈为空则输出提示信息并返回-1，否则返回栈顶元素。
bool StackEmpty(SqStack S)
{
return S.top == -1; // 栈顶指针为-1表示栈为空
}
void ClearStack(SqStack *S)
{
S->top = -1; // 栈顶指针初始化为-1，表示栈为空
}
在使用 C 语言实现栈时，我们可以使用数组来存储栈中元素，并使用一个变量来记录栈顶指针。栈顶指针指向栈顶元素的下标。在 push 操作时，将元素插入数组中，并将栈顶指针加一；在 pop 操作时，将栈顶指针减一并返回栈顶元素。
我们使用结构体定义了一个 Stack 类型，包含一个数组和一个整数类型的栈顶指针 top。在 createStack 函数中，我们分配了一个 Stack 结构体的内存，并将 top 初始化为 -1。isEmpty 函数用于判断栈是否为空。push 函数用于将元素入栈，如果栈已满则打印出错信息并退出程序，否则将元素插入数组中并将 top 加一。pop 函数用于弹出栈顶元素，如果栈为空则打印出错信息并退出程序，否则返回栈顶元素并将 top 减一。在主函数中，我们创建了一个新栈并调用了 push 和 pop 操作，最后释放了所分配的内存。
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Stack {
int data[MAX_SIZE]; // 数组存储元素
int top; // 栈顶指针
};
struct Stack* createStack() {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->top = -1;
return stack;
}
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
void push(struct Stack* stack, int x) {
if (stack->top == MAX_SIZE - 1) {
printf("Stack Overflow\n");
exit(1);
}
stack->data[++stack->top] = x;
}
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow\n");
exit(1);
}
return stack->data[stack->top--];
}
int main() {
struct Stack* stack = createStack();
push(stack, 1);
push(stack, 2);
push(stack, 3);
printf("%d\n", pop(stack)); // 输出 3
printf("%d\n", pop(stack)); // 输出 2
printf("%d\n", pop(stack)); // 输出 1
free(stack);
return 0;
}
在这个示例代码中，我们定义了一个栈数组 stack 和一个指针 top，用于跟踪栈顶元素的位置。push() 函数用于将元素推入栈，如果栈满了，就会返回一个错误信息。pop() 函数用于弹出栈顶元素，如果栈为空，则返回一个错误信息。peek() 函数用于返回栈顶元素的值，如果栈为空，则返回 -1。print() 函数用于打印整个栈的内容。
在主函数中，我们演示了如何使用这些函数。我们先将元素 1、2 和 3 推入栈中，然后打印整个栈。接着我们弹出栈顶元素，再次打印栈内容，最后打印栈顶元素的值。
#include <stdio.h>
#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = -1;
void push(int x) {
if (top == MAX_SIZE - 1) {
printf("Error: Stack overflow\n");
return;
}
stack[++top] = x;
}
void pop() {
if (top == -1) {
printf("Error: Stack is empty\n");
return;
}
top--;
}
int peek() {
if (top == -1) {
printf("Error: Stack is empty\n");
return -1;
}
return stack[top];
}
void print() {
if (top == -1) {
printf("Stack is empty\n");
return;
}
printf("Stack: ");
for (int i = 0; i <= top; i++) {
printf("%d ", stack[i]);
}
printf("\n");
}
int main() {
push(1);
push(2);
push(3);
print(); // Stack: 1 2 3
pop();
print(); // Stack: 1 2
printf("Top element: %d\n", peek()); // Top element: 2
return 0;
}
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct node {
int data;
struct node *next;
};
// 定义顺序栈结构体
struct stack {
struct node *top;
};
// 初始化栈
void init_stack(struct stack *s) {
s->top = NULL;
}
// 入栈
void push(struct stack *s, int data) {
struct node *new_node = (struct node *)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = s->top;
s->top = new_node;
}
// 出栈
int pop(struct stack *s) {
if (s->top == NULL) {
printf("Error: stack is empty.\n");
return -1;
}
int data = s->top->data;
struct node *temp = s->top;
s->top = s->top->next;
free(temp);
return data;
}
// 打印栈中元素
void print_stack(struct stack *s) {
struct node *current = s->top;
printf("Stack: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
struct stack s;
init_stack(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
print_stack(&s);
printf("Popped: %d\n", pop(&s));
printf("Popped: %d\n", pop(&s));
print_stack(&s);
push(&s, 4);
push(&s, 5);
print_stack(&s);
return 0;
}
输出结果：
Stack: 3 2 1
Popped: 3
Popped: 2
Stack: 1
Stack: 5 4 1
链栈是一种使用链表结构实现的栈，入栈和出栈操作与普通栈的操作相似。
在链栈的顶部插入一个新节点即可，也可以说是将新元素作为链表的表头。具体步骤如下：
1. 创建一个新的节点，并给节点赋值。
2. 如果链栈为空，将新的节点设为栈顶，即链栈的头节点。
3. 如果链栈不为空，将新的节点插入到链栈的头节点之前，然后将新节点设为栈顶。
从链栈的顶部删除一个节点即可，也可以说是删除链表的表头。具体步骤如下：
1. 如果链栈为空，直接返回空。
2. 如果链栈不为空，将栈顶节点删除，然后将栈顶指针指向下一个节点。
链栈是基于链表实现的栈，其初始化需要创建一个头节点，头节点的指针域指向空。初始化后的链栈拥有一个头节点，top指针指向头节点的下一个节点，count为0表示栈为空。
typedef struct StackNode {
int data; // 数据域
struct StackNode *next; // 指针域
} StackNode, *LinkStackPtr;
typedef struct {
LinkStackPtr top; // 栈顶指针
int count; // 栈元素个数
} LinkStack;
void InitStack(LinkStack *S)
{
S->top = (LinkStackPtr)malloc(sizeof(StackNode)); // 创建头节点
S->top->next = NULL; // 头节点的指针域指向空
S->count = 0; // 栈元素个数为0
}
共享栈是一种特殊的栈数据结构，它是两个栈共用同一块内存空间。这种栈可以实现两个栈在同一块空间上进行操作，节约了内存空间。共享栈的实现可以通过两种方式：静态分配和动态分配。
静态分配的共享栈是在程序开始时预先定义它的大小，而动态分配的共享栈则是在程序运行时动态地分配内存。静态分配的共享栈适用于事先知道栈大小的情况，而动态分配的共享栈则更加灵活，可以根据实际需要进行分配。
共享栈的常规操作包括push、pop和isEmpty等。当两个栈都没有满时，可以同时向两个栈中push元素。当其中一个栈满时，另一个栈可以继续使用剩余空间。同样地，当其中一个栈为空时，另一个栈可以继续使用整个空间。
共享栈常用于多个程序共用同一块内存空间的情况。在嵌入式系统中，共享栈可以用于操作系统内核和应用程序之间共享内存的情况。
以下是用C语言实现共享栈的示例代码，其中使用静态分配的方式：
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 共享栈的最大大小
typedef struct {
int data[MAX_SIZE];
int top1;
int top2;
} ShareStack;
// 初始化共享栈
void initShareStack(ShareStack *stack) {
stack -> top1 = -1;
stack -> top2 = MAX_SIZE;
}
// 判断共享栈是否为空
int isShareStackEmpty(ShareStack *stack) {
return stack -> top1 == -1 && stack -> top2 == MAX_SIZE;
}
// 将元素压入栈1
void pushToStack1(ShareStack *stack, int x) {
if (stack -> top1 + 1 == stack -> top2) { // 栈1和栈2的分界点
printf("Stack overflow.\n");
return;
}
stack -> top1++;
stack -> data[stack -> top1] = x;
}
// 将元素压入栈2
void pushToStack2(ShareStack *stack, int x) {
if (stack -> top1 + 1 == stack -> top2) { // 栈1和栈2的分界点
printf("Stack overflow.\n");
return;
}
stack -> top2--;
stack -> data[stack -> top2] = x;
}
// 从栈1中弹出元素
int popFromStack1(ShareStack *stack) {
if (stack -> top1 == -1) {
printf("Stack underflow.\n");
return -1;
}
int x = stack -> data[stack -> top1];
stack -> top1--;
return x;
}
// 从栈2中弹出元素
int popFromStack2(ShareStack *stack) {
if (stack -> top2 == MAX_SIZE) {
printf("Stack underflow.\n");
return -1;
}
int x = stack -> data[stack -> top2];
stack -> top2++;
return x;
}
int main() {
ShareStack stack;
initShareStack(&stack);
pushToStack1(&stack, 1);
pushToStack1(&stack, 2);
pushToStack2(&stack, 3);
pushToStack2(&stack, 4);
printf("pop from stack1: %d\n", popFromStack1(&stack));
printf("pop from stack2: %d\n", popFromStack2(&stack));
return 0;
}在上述示例代码中，共享栈的最大大小为100，定义了一个结构体ShareStack来表示共享栈。其中，top1表示栈1的栈顶指针，top2表示栈2的栈顶指针。静态分配的共享栈在程序开始时预先定义了它的大小，并使用结构体中的data数组来存储共享栈的元素。
在初始化共享栈时，将栈1和栈2的栈顶指针都初始化为-1和MAX_SIZE，表示栈为空。isShareStackEmpty函数用于判断共享栈是否为空。
共享栈的push和pop操作分别对两个栈进行处理。当栈1和栈2的分界点相遇时，说明两个栈都满了，此时再push元素会导致栈溢出。因此，在push操作前需要检查是否已经满了。
在pop操作中，如果栈1或栈2为空，则会出现栈下溢的情况，需要进行处理。
最后，在测试代码中，我们向栈1和栈2中各压入两个元素，然后依次从栈1和栈2中弹出元素。
栈是一种常见的数据结构，易错点包括以下几个方面：
1. 栈空间溢出：当栈中存储的数据量超过了栈的大小时，将会发生栈溢出错误。
2. 函数调用不当：函数调用时，参数、返回值、局部变量等数据都存储在栈中。如果函数调用不当，例如递归函数调用深度太深，会导致栈空间快速耗尽，从而引发栈溢出错误。
3. 栈中数据类型不匹配：栈数据结构中只能存储一种数据类型，如果在栈中存储了不同类型的数据，会导致数据类型不匹配错误。
4. 栈的访问越界：当访问栈中的数据时，注意不能超出栈的范围，否则会引发栈访问越界错误。
5. 栈的空间过小：栈的大小限制了存储在其中的数据量，如果栈的空间过小，容易发生栈溢出错误。
6. 栈中数据处理不当：栈中的数据应该按照先进后出的顺序处理，如果处理顺序错乱，会导致结果错误。
综上所述，栈的易错点主要包括栈空间溢出、函数调用不当、栈中数据类型不匹配、栈的访问越界、栈的空间过小和栈中数据处理不当等方面。要避免这些错误，应该注意栈的使用规范和限制。