C++数据结构之：栈Stack

摘要：

   it人员无论是使用哪种高级语言开发东东，想要更高效有层次的开发程序的话都躲不开三件套：数据结构，算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

   此系列专注讲解数据结构数组、链表、队列、栈、树、哈希表、图，通过介绍概念以及提及一些可能适用的场景，并以C++代码简易实现，多方面认识数据结构，最后为避免重复造轮子会浅提对应的STL容器。本文介绍的是栈Stack。

（开发环境：VScode，C++17）

关键词： C++，数据结构，栈，Stack

声明：本文作者原创，转载请附上文章出处与本文链接。

文章目录

• • • 摘要：
    • 正文：
    • • 介绍：
      • • 特性：
        • 应用：
      • 代码实现：
      • 对应STL：
    • 推荐阅读

正文：

介绍：

   栈（Stack）是一种后进先出（LIFO，Last In First Out）的数据结构，它只允许在一端进行操作或删除操作，这一端被称为栈顶（Top），而另一端则被称为栈底（Bottom）。

   栈也有两种存储表示方法：链栈和顺序栈。链栈是指采用链式存储结构实现的栈，通常用单链表来表示。它的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续也可以是不连续）；而顺序栈是用顺序存储结构实现的栈，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。

特性：

• 后进先出（LIFO）：栈中的元素按照先后顺序排列，最后一个进入的元素总是在栈顶，而第一个进入的元素在栈底。每次删除（或称为弹出）操作都是取出栈顶的元素，因此栈是一种后进先出的数据结构。
• 单端插入/删除：栈只允许在栈顶进行插入（压入，Push）和删除（弹出，Pop）操作。
• 受限的随机访问：栈中的元素只能通过栈顶进行访问，而不能直接访问栈底或其他位置的元素。
• 适用于简单的数据结构：栈只具有插入和删除元素的功能，不支持排序和查找等操作。

应用：

• 函数调用：在函数调用时，栈用于保存函数的返回地址和局部变量。当函数调用结束时，栈顶指针会回退到上一个函数的位置。
• 括号匹配：使用栈可以轻松解决括号匹配的问题。通过遍历表达式，将左括号压入栈中，当遇到右括号时，从栈顶弹出一个元素并判断是否与当前右括号匹配。
• 表达式求值：栈可以用来实现中缀表达式转后缀表达式，并且可以通过后缀表达式求解表达式的值。
• 浏览器前进后退：浏览器的前进和后退功能可以使用两个栈来实现，分别保存浏览历史记录。
• 撤销操作：在编辑器或办公软件中，撤销操作通常可以使用栈来实现，将每次的操作记录压入栈中，当需要撤销时从栈顶弹出一个操作并执行相反的操作。

代码实现：

#cstack.h
#ifndef CSTACK_H
#define CSTACK_H
#include <iostream>
using namespace std;

// 栈链节点
template<class T>
class CStackNode
{
public:
    CStackNode(T t):data(t),next(NULL){}
    ~CStackNode(){ next = NULL; }
    CStackNode(const CStackNode& node)
    {
        if(this == &node){
            return;
        }
        *this = node;
    }
    CStackNode &operator=(const CStackNode& node)
    {
        if (this == &node){
            return *this;
        }
        this->data = node.data;
        this->next = node.next;
        return *this;
    }
    
public:
    T data;
    CStackNode *next;
};


// 链式栈
template<class T>
class CStack
{
public:
    CStack() :top(NULL),node(NULL),m_size(0) {}
    ~CStack()
    {
        delete top;top = NULL;
        delete node;node = NULL;
    }

    void push(T t);                     // 入栈
    T pop();                            // 出栈
    void traverse();                    // 打印整个栈
    void clear();                       // 清空栈
    T getTop() { return top; }          // 返回栈顶元素
    int size() { return m_size; }       // 返回栈内成员个数
    bool empty() { return 0 == m_size; }// 判断是否为空栈

private:
    CStackNode<T>* top;     
    CStackNode<T>* node;      
    int m_size; 
};

template <class T>
inline void CStack<T>::push(T t)
{
    node = new CStackNode<T>(t);
    if(top == NULL){
        top = node;
    }
    else{
        node->next = top;
        top = node;
    }
    m_size++;
}

template <class T>
inline T CStack<T>::pop()
{
    if(empty()){
        throw "empty stack.";
    }
    node = top;
    top = top->next;
    m_size--;
    return node->data;
}

template <class T>
inline void CStack<T>::traverse()
{
    node = top;
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}

template <class T>
inline void CStack<T>::clear()
{
    node = top;
    while (node != NULL)
    {
        node = top->next;
        delete top;
        top = node;
    }
    top = NULL;
    m_size = 0 ;
}

#endif // !CSTACK_H

#cstack.cpp
#include "cstack.h"
#include <iostream>
using namespace std;

int main(int argc, char** argv)
{
    CStack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
    stack.push(6);
    stack.push(7);
    stack.push(8);
    stack.traverse();
    cout << stack.pop() << " " << stack.pop() << endl;
    stack.traverse();
    stack.clear();
    stack.traverse();
    return 0;
}

对应STL：

• stack：

  堆栈。其原理是先进后出（FILO），其底层容器可以是任何标准的容器适配器，默认为deque双端队列

推荐阅读

C/C++专栏：https://blog.csdn.net/weixin_45068267/category_12268204.html
（内含其它数据结构及对应STL容器使用）