Data-Structure5

Before：JaneZ今天更新频率有点高啊😎😎😎（ 这么良心的up还不快三连一下🤣🤣🤣 ）南京几个月前新开通了7号线，作为资深轨道交通爱好者的JaneZ也是在回到南京的第二天光速打卡了（ 应该坐完了永初路——福建路这一段 ），比较熟悉的几个站点就是中胜、大士茶亭、草场门、古平岗还有福建路（ nsfz校车！）吧。前2天去省人民看病，顺带打卡了7号线网红站点——清凉山！真的好看！地下6层是真的厉害！附上图片一张💕💕💕

Data Structure 5 栈

栈的定义

• 一种特殊的线性表，插入删除运算限定在表的某一端进行
• 允许进行插入删除操作的一端称为栈顶，另一端称为栈底
• 处于栈顶位置中的数据元素称为栈顶元素，若栈中没有元素，则称为空栈
• LIFO表（后进先出表）

栈的抽象类

template <class elemType>
class stack{
    public:
        virtual bool isEmpty() const = 0; //判栈空
        virtual void push(const elemType &x) = 0; //进栈
        virtual elemType pop() = 0; //出栈
        virtual elemType top() const = 0; //取栈顶元素
        virtual ~stack(); //虚析构函数
};

栈的顺序实现

栈的顺序实现称为顺序栈
顺序栈的实现需要3个变量：

• 一个指向栈元素类型的指针（指向动态数组的首地址）
• 一个表示数组规模的整型数
• 一个表示栈顶位置的整型数
  

下面是一个顺序栈类的定义

template <class elemType>
class seqStack : public stack<elemType>{
    private:
        elemType *elem;
        int top_p;
        int maxSize;
        void doubleSpace();
    public:
        seqStack(int initSize = 10);
        ~seqStack();
        bool isEmpty() const;
        void push(const elemType &x);
        elemType pop();
        elemType top() const;
};

具体实现

template <class elemType>
bool seqList<elemType>::isEmpty() const{
    return top_p == -1;
}

template <class elemType>
void seqList<elemType>::push(const elemType &x){
    if(top_p == maxSize -1){
        doubleSpace();
    }
    top_p ++;
    elem[top_p] == x;
}

template <class elemType>
elemType seqList<elemType>::pop(){
    top_p --;
    return elem[top_p + 1];
}

template <class elemType>
elemType seqList<elemType>::top() const{
    return elem[top_p];
}

template <class elemType>
void seqList<elemType>::doubleSpace(){
    elemType *tmp = elem;
    elem = new elemType[2 * maxSize];
    for(int i = 0; i < maxSize ; i ++){
        elem[i] = tmp[i];
    }
    maxSize *= 2;
    delete []tmp;
}