【数据结构】栈算法(算法原理+源码)

发布时间:2024年01月23日

博主介绍:?全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战?有需要可以联系作者我哦!

🍅附上相关C语言版源码讲解🍅

👇🏻 精彩专栏推荐订阅👇🏻 不然下次找不到哟

目录

一、栈算法

栈的基本操作:

栈的应用:

栈的实现方式:

二、算法实现

?三、小结

大家点赞、收藏、关注、评论啦 !

谢谢哦!如果不懂,欢迎大家下方讨论学习哦。

一、栈算法

栈(Stack)是一种具有特定规则的数据结构,它基于后进先出(Last In, First Out,LIFO)的原则。这意味着最后进栈的元素将会是最先出栈的。栈常常用于实现函数调用、表达式求值、括号匹配等问题。

栈的基本操作:

  1. Push: 将元素压入栈顶。
  2. Pop: 从栈顶弹出元素。
  3. Top(或Peek): 查看栈顶元素但不弹出。
  4. isEmpty: 检查栈是否为空。
  5. Size: 获取栈中元素的数量。

栈的应用:

  1. 函数调用: 保存函数调用的上下文,包括局部变量、返回地址等。
  2. 表达式求值: 中缀表达式转后缀表达式,然后使用栈进行求值。
  3. 括号匹配: 检查表达式中的括号是否匹配。
  4. 浏览器前进后退: 使用两个栈分别保存前进和后退的页面。
  5. 撤销操作: 记录操作历史,可以通过栈实现撤销功能。

栈的实现方式:

  1. 数组: 使用数组实现栈,需要注意栈的大小限制。
  2. 链表: 使用链表实现栈,动态分配内存,栈大小可以灵活调整。?

二、算法实现

?通过 pushpoppeek 操作对栈进行操作。

#include <iostream>
#define MAX_SIZE 100

class Stack {
private:
    int arr[MAX_SIZE];
    int top;

public:
    Stack() {
        top = -1;
    }

    bool isEmpty() {
        return top == -1;
    }

    bool isFull() {
        return top == MAX_SIZE - 1;
    }

    void push(int value) {
        if (!isFull()) {
            arr[++top] = value;
            std::cout << "Pushed: " << value << std::endl;
        } else {
            std::cout << "Stack overflow!" << std::endl;
        }
    }

    void pop() {
        if (!isEmpty()) {
            std::cout << "Popped: " << arr[top--] << std::endl;
        } else {
            std::cout << "Stack underflow!" << std::endl;
        }
    }

    int peek() {
        if (!isEmpty()) {
            return arr[top];
        } else {
            std::cout << "Stack is empty!" << std::endl;
            return -1; // Assuming -1 as an error value
        }
    }
};

int main() {
    Stack myStack;
    myStack.push(5);
    myStack.push(10);
    myStack.push(20);

    std::cout << "Top of the stack: " << myStack.peek() << std::endl;

    myStack.pop();
    myStack.pop();
    myStack.pop();
    myStack.pop(); // Trying to pop from an empty stack

    return 0;
}

执行结果:

?三、小结

堆栈(栈)是一种基本的数据结构,其优点主要应用在一下方面:

  1. 简单直观: 栈的操作相对简单,主要包括入栈(Push)和出栈(Pop)两种基本操作。这种简单性使得栈易于理解和实现。

  2. 高效的操作: 由于遵循后进先出(LIFO)的原则,栈的操作具有常数时间复杂度。入栈和出栈的操作都只涉及栈顶元素,不需要遍历整个数据结构,因此效率较高。

  3. 内存管理: 栈的内存管理是自动的,当一个函数被调用时,其局部变量和函数调用信息被压入栈,函数执行完毕后自动弹出。这种自动管理有助于避免内存泄漏和提高程序的稳定性。

  4. 函数调用: 栈被广泛用于实现函数调用。每次函数调用时,局部变量和返回地址被存储在栈中,函数执行完毕后可以轻松地回到调用点。

  5. 递归: 栈为递归算法提供了自然的支持。递归调用时,每次调用都会创建一个新的栈帧,形成递归调用链。

  6. 表达式求值: 栈在中缀表达式转后缀表达式、以及后缀表达式求值等方面的应用是非常常见的,提供了一种简单而有效的解决方案。

  7. 回溯算法: 在深度优先搜索中,通常使用栈来存储搜索路径,以便回溯到先前的状态。

  8. 括号匹配: 栈常被用来检查表达式中的括号是否匹配,这是许多编程语言编译器和解释器的基本操作。

大家点赞、收藏、关注、评论啦 !

谢谢哦!如果不懂,欢迎大家下方讨论学习哦。

文章来源:https://blog.csdn.net/a910247/article/details/135737990
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。