数据结构（二）栈

• 栈--c++实现
• • 栈的原型（链表描述）
  • Stack类的实现

在Stack.h文件中直接定义了结构体node，声明了Stack类。

templatestruct node{
    T data;
    node* next;
};
template
class Stack {
public:
    Stack();
    ~Stack();
    bool isEmpty() const;            //判断栈是否为空
    int getSize() const;             //返回栈中元素个数
    T& pick() const;                 //返回栈顶元素引用但不删除栈顶元素
    void pop();                      //删除栈顶元素
    void push(const T& element);     //将元素压入栈
private:
    int size;                    //栈中元素的个数
    node * top;               //栈顶节点的指针
};

#include "Stack.h"

template
Stack::Stack() {                        //构造函数
    top = new node;
    top->next = nullptr;
    size = 0;
}

template
Stack::~Stack() {                        //析构函数
    while (top != nullptr) {
        node *pd = top->next;
        delete top;
        top = pd;
    }
}

template
bool Stack::isEmpty() const {            //判断栈是否为空
    return size == 0;
}

template
int Stack::getSize() const {            //返回栈中元素个数
    return size;
}

template
T &Stack::pick() const {                //返回栈顶元素引用但不删除栈顶元素
    return top->data;
}

template
void Stack::push(const T &element) {    //将元素压入栈
    if (size == 0) {
        top->data = element;
    } else {
        node *pd = new node;
        pd->data = element;
        pd->next = top;
        top = pd;
    }
    size++;
}

template
void Stack::pop() {                    //删除栈顶元素
    node *pd = top->next;
    delete top;
    top = pd;
    size--;
}

测试程序如下:

int main(){
    Stack stack;
    for (int i = 0; i < 10 ; i++) {
        stack.push(i+1);
    }
    std::cout << "stack's size = " << stack.getSize() << std::endl;
    std::cout << "stack's top is " << stack.pick() << std::endl;
    stack.pop();
    std::cout << "stack's top is " << stack.pick() << std::endl;
    return 0;
}

测试结果如图：