栈（stack）是一种线性数据结构，采用后进先出（Last In First Out）的原则，即最后一个进入栈的元素最先被取出。栈的常用操作有：push（入栈），pop（出栈），isEmpty（判断栈是否为空），peek（查看栈顶元素）。它具有“先进后出”的特点。栈通过顶部进行操作，只能在栈顶进行插入和删除操作，因此也被称为“后进先出（LIFO）”的结构。

栈的应用非常广泛，比如在编程中可以用来实现函数调用、表达式求值、括号匹配等；在计算机系统中可以用来实现系统调用、内存分配等。

常见的栈实现方式有数组和链表两种，其中数组实现的栈又称为顺序栈，链表实现的栈称为链式栈。

2.栈的基本操作

2.1创建


void InitStack(SqStack *S)
{
    S->top = -1; // 栈顶指针初始化为-1，表示栈为空
}

2.2销毁


void DestroyStack(SqStack *S)
{
    free(S); // 释放栈空间
}

2.3插入Push

在 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;
}

2.4删除Pop

栈的删除操作指的是从栈中弹出元素的操作。由于栈是一种“后进先出”的数据结构，因此删除的元素总是栈顶元素。

栈的删除操作可以使用 pop() 方法来实现。pop() 方法会弹出并返回栈顶元素，同时将栈顶指针指向下一个元素。如果栈为空，则弹出操作会抛出异常。


bool Pop(SqStack *S, int *x)
{
    if (S->top == -1) // 栈为空，无法弹出栈顶元素
        return false;
    *x = S->data[S->top]; // 栈顶元素出栈
    S->top--; // 栈顶指针-1
    return true;
}

2.5获得栈顶元素GetTop

在C语言中通过数组实现栈的操作，我们可以通过下标来获取栈顶元素。假设我们定义了一个栈数组stack和一个栈顶指针top，那么获得栈顶元素的方法如下：


bool GetTop(SqStack S, int *x)
{
    if (S.top == -1) // 栈为空，无法获取栈顶元素
        return false;
    *x = S.data[S.top]; // 获取栈顶元素
    return true;
}

这个函数接收栈数组和栈顶指针作为参数，如果栈为空则输出提示信息并返回-1，否则返回栈顶元素。

2.6判空


bool StackEmpty(SqStack S)
{
    return S.top == -1; // 栈顶指针为-1表示栈为空
}

2.7清空栈


void ClearStack(SqStack *S)
{
    S->top = -1; // 栈顶指针初始化为-1，表示栈为空
}

3.C语言实现栈

在使用 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;
}

4.顺序栈

4.1数组实现顺序栈

在这个示例代码中，我们定义了一个栈数组 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;
}

4.2链表实现顺序栈


#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

5.链栈

链栈是一种使用链表结构实现的栈，入栈和出栈操作与普通栈的操作相似。

5.1入栈操作

在链栈的顶部插入一个新节点即可，也可以说是将新元素作为链表的表头。具体步骤如下：

        1. 创建一个新的节点，并给节点赋值。
        2. 如果链栈为空，将新的节点设为栈顶，即链栈的头节点。
        3. 如果链栈不为空，将新的节点插入到链栈的头节点之前，然后将新节点设为栈顶。

5.2出栈操作

从链栈的顶部删除一个节点即可，也可以说是删除链表的表头。具体步骤如下：

1. 如果链栈为空，直接返回空。
2. 如果链栈不为空，将栈顶节点删除，然后将栈顶指针指向下一个节点。

5.3初始化

链栈是基于链表实现的栈，其初始化需要创建一个头节点，头节点的指针域指向空。初始化后的链栈拥有一个头节点，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
}

6.共享栈

共享栈是一种特殊的栈数据结构，它是两个栈共用同一块内存空间。这种栈可以实现两个栈在同一块空间上进行操作，节约了内存空间。共享栈的实现可以通过两种方式：静态分配和动态分配。

静态分配的共享栈是在程序开始时预先定义它的大小，而动态分配的共享栈则是在程序运行时动态地分配内存。静态分配的共享栈适用于事先知道栈大小的情况，而动态分配的共享栈则更加灵活，可以根据实际需要进行分配。

共享栈的常规操作包括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中弹出元素。

7.栈的易错点

栈是一种常见的数据结构，易错点包括以下几个方面：

1. 栈空间溢出：当栈中存储的数据量超过了栈的大小时，将会发生栈溢出错误。

2. 函数调用不当：函数调用时，参数、返回值、局部变量等数据都存储在栈中。如果函数调用不当，例如递归函数调用深度太深，会导致栈空间快速耗尽，从而引发栈溢出错误。

3. 栈中数据类型不匹配：栈数据结构中只能存储一种数据类型，如果在栈中存储了不同类型的数据，会导致数据类型不匹配错误。

4. 栈的访问越界：当访问栈中的数据时，注意不能超出栈的范围，否则会引发栈访问越界错误。

5. 栈的空间过小：栈的大小限制了存储在其中的数据量，如果栈的空间过小，容易发生栈溢出错误。

6. 栈中数据处理不当：栈中的数据应该按照先进后出的顺序处理，如果处理顺序错乱，会导致结果错误。

综上所述，栈的易错点主要包括栈空间溢出、函数调用不当、栈中数据类型不匹配、栈的访问越界、栈的空间过小和栈中数据处理不当等方面。要避免这些错误，应该注意栈的使用规范和限制。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/635464