数据结构 - C/C++ - 栈

• 公开视频 -> 链接点击跳转公开课程
• 博客首页 -> 链接点击跳转博客主页

目录

结构特性

结构实现

结构容器

结构设计

顺序栈

链式栈

---

结构特性

• 栈(stack)是线性表的一种形式，限定仅在表的一端进行插入或者删除的操作。

• 栈顶 - 表中允许插入、删除的一端称为栈顶(top)，栈顶位置是可以发生变化的。

  • 插入 - 进栈、入栈、压栈。

  • 删除 - 出栈。

• 栈底 - 表中不允许插入、删除的一端称为栈底(bottom)，栈底位置通常是固定不变的。

• 空栈 - 表中不存在任何元素。

• LIFO - last in first out - 先进后出、后进先出。

结构实现

• 顺序栈

int Arr[5] = {0};
 
[栈顶] - Arr[4]
[元素] - Arr[x]
[元素] - Arr[x]
[元素] - Arr[x]
[栈底] - Arr[0] 

• 顺序栈使用连续的内存空间来存储元素，通常使用数组来实现。

• 栈底指向数组起始地址(下标为0的元素)。

• 栈顶指向当前栈中最后一个压入的元素位置。

• 链式栈

• 

[栈顶元素 | 指针] -> [下一个元素 | 指针] -> ... -> [栈底元素 | 空指针]

结构容器

#include <iostream>
#include <stack>
 
int main()
{
    std::stack<int> myStack;
 
    std::cout << myStack.size() << std::endl;
    std::cout << myStack.empty() << std::endl;
 
    //入栈
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
 
    std::cout << myStack.size() << std::endl;
    std::cout << myStack.empty() << std::endl;
 
    //获取栈顶元素
    std::cout << myStack.top() << std::endl;
 
    //出栈
    myStack.pop();
    std::cout << myStack.top() << std::endl;
 
    return 0;
}

结构设计

顺序栈

#include <iostream>
 
class Stack
{
public:
    int*    data;                   //栈的数组
    int     topIndex;               //栈顶索引
    int     capacity;               //栈的容量
 
public:
    Stack();                        //默认构造函数
    Stack(int Size);                //有参构造函数
    Stack(const Stack& other);      //拷贝构造函数
    ~Stack();                       //默认析构函数
 
public:
    void Push(int value);           //入栈函数
    void Pop();                     //出栈函数
    int Top();                      //栈顶元素
 
public:
    bool IsEmpty();                 //是否为空
    int Size();                     //元素个数
 
};
 
Stack::Stack() : data(nullptr), topIndex(-1), capacity(0)
{
 
}
 
Stack::Stack(int Size) : topIndex(-1), capacity(Size)
{
    this->data = new int[capacity] {};
}
 
Stack::Stack(const Stack& other) : data(new int[other.capacity]), topIndex(other.topIndex), capacity(other.capacity)
{
    for (size_t i = 0; i < capacity; i++)
    {
        this->data[i] = other.data[i];
    }
}
 
Stack::~Stack()
{
    if (data != NULL)
    {
        delete[] data;
        data = nullptr;
    }
}
 
void Stack::Push(int value)
{
    if (Size() == capacity)
    {
        //默认容量
        int size = capacity;
 
        //动态扩容
        capacity = (capacity == 0) ? 5 : capacity * 2;
 
        //申请内存
        int* newData = new int[capacity] {};
 
        //数据拷贝
        memcpy(newData, this->data, size * sizeof(int));
 
        //释放数据
        if (this->data != NULL)
        {
            delete[] this->data;
        }
 
        //修正指向
        this->data = newData;
 
    }
 
    data[++topIndex] = value;
}
 
void Stack::Pop()
{
    if (IsEmpty())
    {
        return;
    }
    --topIndex;
}
 
int Stack::Top()
{
    return this->data[topIndex];
}
 
bool Stack::IsEmpty()
{
    return this->topIndex == -1 ? true : false;
}
 
int Stack::Size()
{
    return topIndex + 1;
}

链式栈

class Node
{
public:
    int value;
    Node* Next;
    Node(int Num) : value(Num), Next(nullptr) {}
};
 
class Stack
{
public:
    Node* Head;
 
public:
    Stack() : Head(nullptr) 
    {
 
    }
 
    Stack(const Stack& other)
    {
        if (other.Head == nullptr)
        {
            Head = nullptr;
        }
        else
        {           
            Head = new Node(other.Head->value);
            Node* head = Head;
            Node* node = other.Head->Next;
            while (node != nullptr)
            {
                head->Next = new Node(node->value);
                head = head->Next;
                node = node->Next;
            }
        }
    }
 
    ~Stack()
    {
        Clear();
    }
 
public:
 
    void Push(int value)
    {
        Node* node = new Node(value);
 
        node->Next = Head;
 
        Head = node;
    }
 
    void Pop()
    {
        if (!IsEmpty())
        {
            Node* temp = Head;
            Head = Head->Next;
            delete temp;
        }
    }
 
    int Top()
    {
        if (!IsEmpty())
        {
            return Head->value;
        }
    }
 
public:
 
    bool IsEmpty()
    {
        return Head == nullptr;
    }
 
    void Clear()
    {
        while (!IsEmpty())
        {
            Pop();
        }
    }
 
};