您现在的位置是：网站首页>技术百科技术百科

数据结构之栈（Stack）

小大寒2024-01-01[技术百科]博学多闻

数据结构之栈（Stack）栈（Stack）是一种后进先出（LIFO）的数据结构，数据的插入和删除都发生在栈的顶部。栈具有非常高效的插入和删除操作，广泛应用于算法中的递归调用、表达式求值等场景。

数据结构之栈（Stack）

1. 基础概念

1.1 栈的定义

栈是一种线性数据结构，元素的操作（添加和删除）仅限于一端，称为栈顶。栈具有以下两大特点：

后进先出（LIFO）：最后被压入栈的元素最先被弹出。
两端操作：只允许在栈顶进行插入（Push）和删除（Pop）操作。

1.2 栈的特点

栈的主要特点是后进先出。它具有以下优点：

高效的元素访问：栈操作时间复杂度为 O(1)，无论栈的大小如何。
存储结构简单：可以通过数组或链表实现。

1.3 使用场景

栈广泛应用于以下场景：

函数调用：计算机内存中保存函数调用的执行环境，使用栈结构来存储返回地址和局部变量。
表达式求值：如中缀表达式转后缀表达式。
浏览器的历史记录：用户的页面访问记录可以使用栈来保存，后访问的页面最先返回。

2. 实现与操作

2.1 核心操作实现

栈的常见操作包括：Push（入栈）、Pop（出栈）、Peek（查看栈顶元素）、isEmpty（检查栈是否为空）。下面是用 C 语言实现的简单栈操作：

#include <stdio.h>
#include <stdlib.h>

#define MAX 5

// 定义栈结构体
typedef struct Stack {
    int items[MAX];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}

// 判断栈是否为满
int isFull(Stack* s) {
    return s->top == MAX - 1;
}

// 入栈操作
void push(Stack* s, int value) {
    if (isFull(s)) {
        printf("栈已满，无法入栈！\n");
    } else {
        s->items[++(s->top)] = value;
        printf("%d 已入栈\n", value);
    }
}

// 出栈操作
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("栈为空，无法出栈！\n");
        return -1;
    } else {
        return s->items[(s->top)--];
    }
}

// 查看栈顶元素
int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("栈为空！\n");
        return -1;
    } else {
        return s->items[s->top];
    }
}

int main() {
    Stack s;
    initStack(&s);
    
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    
    printf("栈顶元素：%d\n", peek(&s));
    
    printf("出栈元素：%d\n", pop(&s));
    printf("出栈元素：%d\n", pop(&s));
    
    return 0;
}
    </stdlib.h></stdio.h>

2.2 代码详解

initStack：初始化栈，将栈顶指针设置为-1，表示栈为空。
isEmpty：判断栈是否为空，若栈顶指针为-1，则栈为空。
isFull：判断栈是否为满，若栈顶指针等于最大容量减1，则栈满。
push：将元素压入栈顶，如果栈已满，输出提示信息。
pop：将栈顶元素弹出，并返回该元素。如果栈为空，输出提示信息。
peek：返回栈顶元素，但不删除它。如果栈为空，输出提示信息。

3. 时间与空间复杂度分析

3.1 时间复杂度

栈的基本操作时间复杂度：

Push：O(1)，直接操作栈顶。
Pop：O(1)，直接操作栈顶。
Peek：O(1)，直接访问栈顶。

3.2 空间复杂度

栈的空间复杂度是 O(n)，其中 n 是栈的最大容量，空间使用量与栈的元素数量直接相关。

4. 优缺点与局限性

4.1 优点

操作简单：栈操作简单且高效，插入和删除操作均为 O(1)。
适合特定场景：如函数调用的回溯、表达式求值等。

4.2 缺点与局限性

只支持单端操作：栈只允许从一端进行操作，无法在中间访问元素。
空间限制：栈的大小固定或动态调整可能导致性能瓶颈。

5. 常见应用场景

5.1 实际应用

栈可以用于解决许多实际问题，如“括号匹配”问题：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100

// 定义栈结构体
typedef struct {
    char items[MAX];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}

// 入栈操作
void push(Stack* s, char c) {
    if (s->top == MAX - 1) {
        printf("栈已满\n");
    } else {
        s->items[++(s->top)] = c;
    }
}

// 出栈操作
char pop(Stack* s) {
    if (isEmpty(s)) {
        return '\0';
    } else {
        return s->items[(s->top)--];
    }
}

// 括号匹配函数
int isValid(char* s) {
    Stack stack;
    initStack(&stack);

    for (int i = 0; i < strlen(s); i++) {
        char c = s[i];
        if (c == '(' || c == '{' || c == '[') {
            push(&stack, c);
        } else if (c == ')' || c == '}' || c == ']') {
            char top = pop(&stack);
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return 0;
            }
        }
    }
    return isEmpty(&stack);
}

int main() {
    char expr[] = "{[()]}";
    if (isValid(expr)) {
        printf("括号匹配成功！\n");
    } else {
        printf("括号匹配失败！\n");
    }
    return 0;
}
    </string.h></stdlib.h></stdio.h>