Data-Structure6

Before：maybe是回校前最后一篇DS了😢浅浅立个flag：开学后成为日更博主😎

Data Structure 6 栈的链接实现及栈的应用

前情提要

在上一章节的内容中，我们学习了顺序栈相关知识，知道顺序栈的实现本质是在维护一个动态数组，那么在本章节中要讲解的链接栈与顺序栈的实现有何区别呢？

链接栈的存储实现

由于与栈相关的操作都是在栈顶进行的，所以并不需要直接前驱，使用单链表即可，也不需要头结点。下图是一个存储的图示：

话不多说，上链接栈定义代码！

template<class elemType>
class linkStack:public stack<elemType>{
    private:
        struct node{
            node *next;
            elemType data;
            node(const elemType &x , node *n = nullptr){
                next = n;
                data = x;
            }
            node():next(nullptr){}
            ~node();
        };

        node *top_p; //栈顶结点
    public:
        linkStack();
        ~linkStack();
        bool isEmpty() const;
        void push(const elemType &x);
        elemType pop();
        elemType top() const;
};

链接栈运算实现

构造函数&析构函数：

template<class elemType>
linkStack<elemType>::linkStack(){
    top_p = nullptr;
}

template<class elemType>
linkStack<elemType>::~linkStack(){
    node *q;
    while(t != nullptr){
        q = top_p;
        top_p = top_p -> next;
        delete q;
    }
}

进栈、出栈、判空、取栈顶元素：

template<class elemType>
void linkStack<elemType>::push(const elemType &x){
    top_p = new node(x , top_p);
}

template<class elemType>
elemType linkStack<elemType>::pop(){
    node *p = top_p;
    top_p = top_p -> next;
    elemType x = p -> data;
    delete p;
    return x;
}

template<class elemType>
bool linkStack<elemType>::isEmpty() const{
    return top_p == nullptr;
}

template<class elemType>
elemType linkStack<elemType>::top() const{
    return top_p -> data;
}

STL中的栈

在STL中，借助于其他容器存储数据的容器称作容器适配器。栈借助线性表进行存储，故属于容器适配器。栈可以借助的容器有vector、list和deque。在调用STL::stack时，如果不指定第二个参数，则默认是用deque来存储数据。
For example: $stack<int , vector<int>>$ $stack<int , list<int>>$

栈的应用

1.递归调用

void printInt(int num){
    if(num < 10){
        cout.put(num);
    }else{
        printInt(num/10);
        cout.put(num%10 + '0');
    }
}

这是应用递归函数实现对一个正整数的打印的函数
2.括号配对 balance类的定义

class balance{
    private:
        ifstream fin; //待检测文件流
        int curremtLine; //当前处理的行号
        int errors; //现有的错误数量
    struct Symbol{ //栈元素类型
        char token;
        int TheLine; 
    };
    enum Slash{
        SlashSlash; //C++注释
        SlashStar; //C注释
    };
    bool CheckMatch(char Symb I, char Symb2, int Line I, int Line2);
    char GetNextSymbol();
    void PutBackChar(char ch);
    void SkipComment(enum CommentType type);
    void SkipQuote(char type);
    char NextChar();

    public:
        balance(const char *s);
        int CheckBalance(); //检查括号是否匹配
};

class noFile{}; //若检查文件不存在，抛出此异常

具体实现就不给出了（还是太懒了😢😢😢）