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

目录

前言

顺序栈的实现

初始化栈

判断栈空

判断栈满

入(进)栈

出栈

获取栈顶元素

示例代码

顺序栈的应用前景


前言

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

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

顺序栈的实现

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

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

#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。

入(进)栈

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

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

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

出栈

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

int pop(SeqStack *stack, int *value) {
    if (isEmpty(*stack)) {
        printf("Stack is empty. Cannot pop element.\n");
        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.\n");
        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.\n");
        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.\n");
        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.\n");
        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\n", top);
    
    int value;
    pop(&stack, &value);
    printf("Popped element: %d\n", value);
    
    getTop(stack, &top);
    printf("Top element: %d\n", top);
    
    return 0;
}

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

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

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

顺序栈的应用前景

  1. 表达式求值:顺序栈可以用于解析和计算数学表达式,如中缀表达式转后缀表达式,并利用后缀表达式进行求值。

  2. 括号匹配:顺序栈可以用于检查表达式中的括号是否匹配,如圆括号、方括号和花括号的配对情况。

  3. 浏览器历史记录:浏览器的后退功能可以使用顺序栈来实现。每当用户访问一个新的网页时,该网页的URL可以被推入栈中;当用户点击后退按钮时,可以从栈顶弹出上一个网页的URL。

  4. 撤销操作:在文本编辑器、图形绘制软件等应用程序中,顺序栈可以用于实现撤销操作。每当用户进行编辑或绘制操作时,相关的修改可以被推入栈中;当用户执行撤销操作时,可以从栈顶弹出最近的修改并还原到上一个状态。

  5. 函数调用:在程序执行过程中,函数调用的过程可以使用顺序栈来管理函数的调用关系和返回地址。

  6. 浏览器的前进功能:类似于后退功能,顺序栈可以用于实现浏览器的前进功能。每当用户执行后退操作时,访问的网页URL可以被推入栈中;当用户执行前进操作时,可以从栈顶弹出下一个网页的URL。

  7. 缓存管理:顺序栈可以用于缓存管理,特别是最近访问页面的缓存。当用户访问一个页面时,可以将其URL推入栈中,并根据缓存的大小限制栈的长度,当栈已满时,最久未访问的页面URL将被弹出。

这些只是顺序栈应用的一些例子,实际上,顺序栈在许多领域都有应用,如编译器设计、图形处理、操作系统等。顺序栈提供了一种简单而有效的数据结构,可以在许多问题中实现后进先出的操作。


通过以上所述 希望这篇文章对你学习数据结构和算法有所帮助!

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

06-10 11:22