栈与队列

模板留作参考

链式栈：

#include <iostream>

template <typename ElemType>
class Node {
public:
    ElemType data;
    Node* next;
    Node(ElemType data, Node* next) {
        this->data = data;
        this->next = next;
    }
}; // Node 结点类

template <typename ElemType>
class Stack {
private:
    Node<ElemType>* top; // 栈顶指针

public:
    Stack() {
        top = nullptr;
    } // 初始栈顶为空

    ~Stack() {
        Node<ElemType>* p;
        while (top != nullptr) {
            pop();
        }
    } // 清除栈

    bool empty() {
        return top == nullptr;
    } // 判断栈是否为空

    int size() {
        int count = 0;
        for (Node<ElemType> *p = top; p != nullptr; p = p->next) {
            count++;
        }
        return count;
    } // 返回栈中元素个数

    void push(ElemType data) {
        Node<ElemType>* p = new Node<ElemType>(data, top); // 新结点的 next 指向原来的栈顶
        top = p; // 新结点成为栈顶
    } // 入栈

    bool pop() {
        if (empty()) {
            std::cout << "Stack is empty!" << std::endl;
            return false;
        }
        Node<ElemType>* p = top;
        top = top->next;
        delete p;
        return true;
    } // 出栈

    ElemType getTop() {
        if (empty()) {
            std::cout << "Stack is empty!" << std::endl;
            exit(1);
        }
        ElemType data = top->data;
        return data;
    } // 获取栈顶元素
}; // Stack 栈类，无头结点链表，链表头为栈顶

int main() {
    Stack<int> *s = new Stack<int>();
    for (int i = 1; i <= 10; i++) {
        s->push(i);
    }
    std::cout << "size: " << s->size() << std::endl;
    while (!s->empty()) {
        std::cout << s->getTop() << " ";
        s->pop();
    }
    delete s;
    return 0;
}

链队列：

#include <iostream>

template <typename ElemType>
class Node {
public:
    ElemType data;
    Node* next;
    Node(ElemType data, Node* next) {
        this->data = data;
        this->next = next;
    }
}; // Node 结点类

template <typename ElemType>
class Queue {
private:
    Node<ElemType>* front; // 队头指针
    Node<ElemType>* rear; // 队尾指针

public:
    Queue() {
        front = rear = nullptr;
    } // 初始队头队尾为空

    ~Queue() {
        while(front != nullptr) {
            pop();
        } // 依次删除队头结点
    }

    bool empty() {
        return front == nullptr;
    } // 判断队列是否为空

    int size() {
        int count = 0;
        for (Node<ElemType>* p = front; p != nullptr; p = p->next) {
            count++;
        }
        return count;
    } // 返回队列中元素个数

    void push_back(ElemType data) {
        Node<ElemType>* p = new Node<ElemType>(data, nullptr);
        if (empty()) {
            front = rear = p; // 队列为空时，队头队尾都指向新结点
        } else {
            rear->next = p;
            rear = p;
        } // 队列不为空时，队尾指向新结点
    } // 入队

    bool pop() {
        if (empty()) {
            std::cout << "Queue is empty!" << std::endl;
            return false;
        }
        Node<ElemType>* p = front;
        front = front->next;
        delete p;
        return true;
    } // 出队

    ElemType getFront() {
        if (empty()) {
            std::cout << "Queue is empty!" << std::endl;
            exit(1);
        }
        ElemType data = front->data;
        return data;
    } // 取队头元素
};
int main() {
    Queue<int> *q = new Queue<int>();
    for (int i = 1; i <= 10; i++) {
        q->push_back(i);
    }
    std::cout << "size: " << q->size() << std::endl;
    while (!q->empty()) {
        std::cout << q->getFront() << " ";
        q->pop();
    }
    delete q;
    return 0;
}

循环队列：

#include <iostream>

template <typename ElemType>
class SqQueue {
private:
    ElemType* data; // 存放队列元素的数组
    int front; // 队头指针
    int rear; // 队尾指针
    int maxSize; // 队列最大容量
    int count = 0; // 队列元素个数

public:
    SqQueue(int maxSize) {
        this->maxSize = maxSize;
        data = new ElemType[maxSize];
        front = rear = 0;
    } // 构造函数

    ~SqQueue() {
        delete []data;
    } // 析构函数

    bool empty() {
        return count == 0;
    } // 判空

    int size() {
        return count;
    } // 求队列元素个数

    bool push_back(ElemType elem) {
        if (count == maxSize) {
            std::cout << "Queue is full!" << std::endl;
            return false;
        } // 队列满
        count ++;
        data[rear] = elem;
        rear = (rear + 1) % maxSize; // 队尾指针加 1, 取模是为了防止数组越界（假溢出）
        return true;
    }

    bool pop() {
        if (empty()) {
            std::cout << "Queue is empty!" << std::endl;
            return false;
        }
        // 这里没必要把队头元素置为 0, 因为队头指针 front 会自动加 1
        count --;
        front = (front + 1) % maxSize; // 队头指针加 1, 取模是为了防止数组越界（假溢出）
        return true;
    }

    ElemType getFront() {
        if (empty()) {
            std::cout << "Queue is empty!" << std::endl;
            exit(1);
        }
        return data[front];
    }
};

int main() {
    SqQueue<int> *q = new SqQueue<int>(8);
    for (int i = 1; i <= 10;i ++) {
        q->push_back(i);
    }
    std::cout << "size: " << q->size() << std::endl;
    while (!q->empty()) {
        std::cout << q->getFront() << " ";
        q->pop();
    }
    delete q;
    return 0;
}