【数据结构与算法】掌握顺序栈：从入门到实践网站首页 学无止境

【数据结构与算法】掌握顺序栈：从入门到实践

青竹雾色间 2024-09-26 12:01:19

简介【数据结构与算法】掌握顺序栈：从入门到实践

?博客主页：青竹雾色间.

?系列专栏：数据结构与算法

?博客制作不易欢迎各位?点赞+⭐收藏+➕关注

前言

当你学习数据结构和算法时，顺序栈（Sequential Stack）是一个重要的概念。它是一种基于数组实现的栈结构，具有先进后出（LIFO）的特性。在本文中，我将介绍如何使用C语言实现顺序栈，并提供一些示例代码。

顺序栈的实现

首先，我们需要定义一个结构体来表示顺序栈：

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;  // 栈顶指针
} SeqStack;

在上述代码中，我们定义了一个数组data用于存储栈中的元素，以及一个整数top表示栈顶指针。

接下来，我们可以实现一些基本的栈操作函数。

初始化栈

void initStack(SeqStack *stack) {
    stack->top = -1;  // 栈顶指针初始化为-1
}

该函数用于初始化一个空的顺序栈，将栈顶指针设为-1，表示栈为空。

判断栈空

int isEmpty(SeqStack stack) {
    return stack.top == -1;
}

上述代码用于检查顺序栈是否为空。如果栈顶指针为-1，表示栈中没有元素，返回1；否则返回0。

判断栈满

int isFull(SeqStack stack) {
    return stack.top == MAX_SIZE - 1;
}

该函数用于检查顺序栈是否已满。如果栈顶指针等于MAX_SIZE - 1，表示栈已满，返回1；否则返回0。

入（进）栈

int push(SeqStack *stack, int value) {
    if (isFull(*stack)) {
        printf("Stack is full. Cannot push element.
");
        return 0;  // 入栈失败
    }
    
    stack->top++;  // 栈顶指针加1
    stack->data[stack->top] = value;  // 将元素存入栈顶位置
    return 1;  // 入栈成功
}

当要将一个元素压入栈时，首先检查栈是否已满。如果栈已满，则无法进行入栈操作，这称为栈上溢。如果栈未满，则将栈顶指针加1，并将新元素存储在栈顶指针指向的位置。

出栈

int pop(SeqStack *stack, int *value) {
    if (isEmpty(*stack)) {
        printf("Stack is empty. Cannot pop element.
");
        return 0;  // 出栈失败
    }
    
    *value = stack->data[stack->top];  // 将栈顶元素赋值给value
    stack->top--;  // 栈顶指针减1
    return 1;  // 出栈成功
}

当要从栈中弹出一个元素时，首先检查栈是否为空。如果栈为空，则无法进行出栈操作，这称为栈下溢。如果栈非空，则返回栈顶指针指向的元素，并将栈顶指针减1，表示栈顶指向下一个元素。

获取栈顶元素

int getTop(SeqStack stack, int *value) {
    if (isEmpty(stack)) {
        printf("Stack is empty. No top element.
");
        return 0;  // 获取失败
    }
    
    *value = stack.data[stack.top];  // 将栈顶元素赋值给value
    return 1;  // 获取成功
}

该函数用于获取栈顶元素的值，并将其赋给value。如果栈为空，会输出错误信息并返回0。

示例代码

下面是一个示例程序，演示了如何使用顺序栈进行一些基本操作：

#include <stdio.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} SeqStack;

void initStack(SeqStack *stack) {
    stack->top = -1;
}

int isEmpty(SeqStack stack) {
    return stack.top == -1;
}

int isFull(SeqStack stack) {
    return stack.top == MAX_SIZE - 1;
}

int push(SeqStack *stack, int value) {
    if (isFull(*stack)) {
        printf("Stack is full. Cannot push element.
");
        return 0;
    }
    
    stack->top++;
    stack->data[stack->top] = value;
    return 1;
}

int pop(SeqStack *stack, int *value) {
    if (isEmpty(*stack)) {
        printf("Stack is empty. Cannot pop element.
");
        return 0;
    }
    
    *value = stack->data[stack->top];
    stack->top--;
    return 1;
}

int getTop(SeqStack stack, int *value) {
    if (isEmpty(stack)) {
        printf("Stack is empty. No top element.
");
        return 0;
    }
    
    *value = stack.data[stack.top];
    return 1;
}

int main() {
    SeqStack stack;
    initStack(&stack);
    
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);
    
    int top;
    getTop(stack, &top);
    printf("Top element: %d
", top);
    
    int value;
    pop(&stack, &value);
    printf("Popped element: %d
", value);
    
    getTop(stack, &top);
    printf("Top element: %d
", top);
    
    return 0;
}

以上代码创建了一个顺序栈，并进行了一些入栈、出栈和获取栈顶元素的操作。运行该程序，输出如下：

Top element: 3
Popped element: 3
Top element: 2

这说明顺序栈的基本操作已经成功实现。

顺序栈的应用前景

表达式求值：顺序栈可以用于解析和计算数学表达式，如中缀表达式转后缀表达式，并利用后缀表达式进行求值。
括号匹配：顺序栈可以用于检查表达式中的括号是否匹配，如圆括号、方括号和花括号的配对情况。
浏览器历史记录：浏览器的后退功能可以使用顺序栈来实现。每当用户访问一个新的网页时，该网页的URL可以被推入栈中；当用户点击后退按钮时，可以从栈顶弹出上一个网页的URL。
撤销操作：在文本编辑器、图形绘制软件等应用程序中，顺序栈可以用于实现撤销操作。每当用户进行编辑或绘制操作时，相关的修改可以被推入栈中；当用户执行撤销操作时，可以从栈顶弹出最近的修改并还原到上一个状态。
函数调用：在程序执行过程中，函数调用的过程可以使用顺序栈来管理函数的调用关系和返回地址。
浏览器的前进功能：类似于后退功能，顺序栈可以用于实现浏览器的前进功能。每当用户执行后退操作时，访问的网页URL可以被推入栈中；当用户执行前进操作时，可以从栈顶弹出下一个网页的URL。
缓存管理：顺序栈可以用于缓存管理，特别是最近访问页面的缓存。当用户访问一个页面时，可以将其URL推入栈中，并根据缓存的大小限制栈的长度，当栈已满时，最久未访问的页面URL将被弹出。