当前位置：首页 > article >正文

C、C++常用数据结构：栈

article 2024/10/23 23:28:11

栈

栈：栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。
栈的本质是一种线性表。
添加元素，称为入栈（push）；删除元素，称为出栈（pop）。
栈可以用顺序存储实现，也可以用链式存储实现，分别成为顺序栈和链栈。但一般使用顺序存储实现，因为栈不允许在栈中间进行插入和删除。
栈数据结构有两种初始化方式，一种是动态初始化，另一种是静态初始化。

动态初始化和静态初始化对比

1. 内存分配方式

动态初始化：栈的大小在运行时确定，通常使用动态内存分配（如new或malloc）来实现。栈的内存从堆中分配，而不是栈帧或全局数据段。（重点是从堆中分配内存）。可以根据实际需要调整栈的大小。例如int* stack = new int[100];
静态初始化：栈的大小在编译时确定，通常使用数组来实现，并且在栈帧或全局数据段中分配内存。一旦栈的大小确定，就不能再改变。例如：int stack[100];

2. 性能对比

动态初始化：由于涉及动态内存分配（如new、delete），分配和释放速度较慢，并且有内存碎片的可能。
静态初始化：因为内存是在栈上或全局段中分配的，分配和释放的速度非常快。

代码示例

动态初始化：

#include <iostream>

using namespace std;

/**
 * 动态内存分配栈
 */
class DynamicStack
{
private:
    int *stack;
    int top;
    int maxsize;

public:
    DynamicStack(int size) : top(-1), maxsize(size)
    {
        stack = new int[size];
    }

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

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

    void push(int val)
    {
        if (isFull())
        {
            cout << "动态分配的栈已满（达到最大值）" << endl;
            return;
        }
        stack[++top] = val;
        cout << stack[top] << "入栈" << endl;
    }

    void pop()
    {
        if (isEmpty())
        {
            cout << "栈为空，不能pop" << endl;
            return;
        }
        cout << stack[top] << "出栈" << endl;
        top--;
    }

    int getTop()
    {
        if (isEmpty())
        {
            cout << "栈为空，不能getTop" << endl;
            return -1;
        }
        return stack[top];
    }
};

int main(int argc, char const *argv[])
{
    DynamicStack dystack(5);
    dystack.push(11);
    dystack.push(25);
    dystack.push(36);
    cout << "栈顶：" << dystack.getTop() << endl;
    dystack.pop();
    dystack.pop();
    dystack.pop();
    return 0;
}

静态初始化：

#include <iostream>

using namespace std;

#define MAXSIZE 100

/**
 * 静态内存分配栈
 */
class StaticStack
{
private:
    int stack[MAXSIZE];
    int top;

public:
    StaticStack() : top(-1) {}
    bool isEmpty() { return top == -1; }
    bool isFull() { return top == MAXSIZE - 1; }

    void push(int value)
    {
        if (isFull())
        {
            cout << "栈已满" << endl;
            return;
        }
        stack[++top] = value;
        cout << stack[top] << "入栈" << endl;
    }

    void pop()
    {
        if (isEmpty())
        {
            cout << "栈为空" << endl;
            return;
        }
        cout << stack[top] << "出栈" << endl;
        top--;
    }

    int getTop()
    {
        if (isEmpty())
        {
            cout << "栈为空" << endl;
            return 0;
        }
        return stack[top];
    }
};

int main(int argc, char const *argv[])
{
    /* code */
    StaticStack static_stack;
    static_stack.push(11);
    static_stack.push(25);
    static_stack.push(36);
    cout << "栈顶：" << static_stack.getTop() << endl;
    static_stack.pop();
    static_stack.pop();
    static_stack.pop();
    return 0;
}

C++的标准库`<stack>`

以上通过编写栈的相关代码，只是为了更直观和简单地理解栈数据结构，实际上，在 C++ 中，可以使用标准库 <stack> 提供的 stack 模板来创建和操作栈。

stack 是一个模板类，可以用来存储任何类型的数据（如 int、double、自定义对象等）。例如：stack<int> s;
stack 的一些基本操作：
- push: 将元素压入栈顶。
- pop: 移除栈顶元素。
- top: 获取栈顶元素的值（但不移除）。
- empty: 检查栈是否为空。
- size: 获取栈中元素的数量。