栈

栈相关

栈的实现

用数组实现栈（顺序栈）

//Stack.hpp

#ifndef Stack_hpp
#define Stack_hpp

#include <iostream>
using namespace std;

//顺序栈
template <typename T>
class Stack {
    T *data; //成员数组
    int top; //栈顶指针，当前栈顶元素的位置
    int size; //栈中元素的最大个数

public:
    Stack();
    ~Stack();

    bool is_empty(); //判断栈空
    bool is_full(); //判断栈满
    void push(const T &elem); //入栈
    void pop(); //出栈
    T get_top(); //访问栈顶元素
};


//栈初始化
//初始栈空，栈顶指针指向-1，初始空间为10
template <typename T>
Stack<T>::Stack() : top(-1), size(10) {
    data = new T[size]; //申请一个初始为10的空间
}

//销毁栈
template <typename T>
Stack<T>::~Stack() {
    delete [] data;
    data = nullptr;
}

//判断栈空
template <typename T>
bool Stack<T>::is_empty() {
    if (top == -1) {
        return true;
    } else {
        return false;
    }
}

//判断栈满
template <typename T>
bool Stack<T>::is_full() {
    if (top == size-1) {
        return true;
    } else {
        return false;
    }
}

//入栈
template <typename T>
void Stack<T>::push(const T &elem) {
    if (is_full()) {
        throw out_of_range("Stack<>::push(): 栈满");
    } else {
        data[++top] = elem;
    }
}

//出栈
template <typename T>
void Stack<T>::pop() {
    if (is_empty()) {
        throw out_of_range("Stack<>::pop(): 栈空");
    } else {
        top--;
    }
}

//访问栈顶元素
template <typename T>
T Stack<T>::get_top() {
    if (is_empty()) {
        throw out_of_range("Stack<>::top(): 栈空");
    } else {
        return data[top];
    }
}

#endif

用链表实现栈（链栈）

//Stack.hpp

#ifndef Stack_hpp
#define Stack_hpp

#include <iostream>
using namespace std;

//结点
template <typename T>
struct node {
    T data; //数据域
    node *next; //指针域
};

//链栈
template <typename T>
class Stack {
    node<T> *top; //栈顶指针
public:
    Stack();
    ~Stack();

    bool is_empty(); //判断栈空
    void push(const T &elem); //入栈
    void pop(); //出栈
    T get_top(); //访问栈顶元素
};

//栈初始化
template <typename T>
Stack<T>::Stack() {
    top = nullptr; //初始为空
}

//销毁栈
template <typename T>
Stack<T>::~Stack() {
    node<T> *ptr = nullptr;
    while (!is_empty()) {
        ptr = top->next;
        delete top;
        top = ptr;
    }
}

//判断栈空
template <typename T>
bool Stack<T>::is_empty() {
    if (top == nullptr) {
        return true;
    } else {
        return false;
    }
}

//入栈
template <typename T>
void Stack<T>::push(const T &elem) {
    node<T> *ptr = new node<T>;
    ptr->data = elem;
    ptr->next = top;
    top = ptr;
}

//出栈
template <typename T>
void Stack<T>::pop() {
    if (is_empty()) {
        throw out_of_range("Stack<>::pop(): 栈空");
    } else {
        node<T> *ptr = top->next;
        delete top;
        top = ptr;
    }
}

//访问栈顶元素
template <typename T>
T Stack<T>::get_top() {
    if (is_empty()) {
        throw out_of_range("Stack<>::top(): 栈空");
    } else {
        return top->data;
    }
}

#endif

stack（栈）

函数方法

代码	功能
s.push(x)	将x压入栈顶
s.top()	返回栈顶的元素
s.pop()	删除栈顶的元素
s.size()	返回栈中元素的个数
s.empty()	检查栈是否为空,若为空返回true,否则返回false