c++ 实现栈、单向队列、双向队列

一、栈实现

code

//
// Created by shaoxinHe on 2024/6/8.
//

#ifndef CPRIMER_MYSTACK_H
#define CPRIMER_MYSTACK_H

#include "stdexcept"
#include "iostream"

using namespace std;

struct queuNode {
    int num{};
    queuNode *next = nullptr;
};

class myStack {
private:
    queuNode *stackTop;
    int stackSize = 0;

public:
    myStack() {
        stackTop = nullptr;
        stackSize = 0;
    }

    ~myStack() {
        while (stackTop) {
            delete stackTop;
            stackTop = stackTop->next;
        }
    }

    bool push(int num) {
        if (stackSize == 0) {
            stackTop = new queuNode;
            stackTop->num = num;
            stackSize++;
            return true;
        } else if (stackSize) {
            auto *tempNode = new queuNode;
            tempNode->num = num;
            tempNode->next = stackTop;
            stackTop = tempNode;
            stackSize++;
            return true;
        }
        return false;
    }

    int pop() {
        if (!isEmpty()) {
            throw out_of_range("栈为空");
        }
        int num = stackTop->num;
        queuNode *temp = stackTop;
        stackTop = stackTop->next;
        delete temp;
        stackSize--;
        return num;
    }
    int size(){
        return this->stackSize;
    }

    bool isEmpty(){
        return size() == 0;
    }
};

#endif //CPRIMER_MYSTACK_H

二、单向队列

code

//
// Created by shaoxinHe on 2024/6/8.
//

#ifndef CPRIMER_MYQUEUE_H
#define CPRIMER_MYQUEUE_H

#include "stdexcept"

struct queueNode {
    int num;
    queuNode *next = nullptr;
};


class myQueue {
private:
    queueNode *front, *rear;
    int queueSize;
public:
    myQueue() {
        front = nullptr;
        rear = nullptr;
        queueSize = 0;
    }

    ~myQueue() {
        while (front) {
            queuNode *temp = front;
            front = front->next;
            delete temp;
        }
    }

    int size() {
        return queueSize;
    }

    bool isEmpty() {
        return queueSize == 0;
    }

    void push(int num) {
        auto *temp = new queuNode;
        temp->num = num;

        if (isEmpty()) {
            front = rear = temp;
            queueSize++;
            return;
        }
        // 队尾插入元素
        rear->next = temp;
        rear = temp;
        queueSize++;

    }

    int pop() {
        if (isEmpty()) throw std::out_of_range("数组越界");
        queuNode *temp = front;
        front = front->next;
        int num = temp->num;
        queueSize--;
        delete temp;
        return num;
    }

};

#endif //CPRIMER_MYQUEUE_H

三、双向队列

code

//
// Created by shaoxinHe on 2024/6/8.
//

#ifndef CPRIMER_DOUBLEQUEUE_H
#define CPRIMER_DOUBLEQUEUE_H

#include "stdexcept"

struct doubleNode {
    int data;
    doubleNode *pre, *next;

    explicit doubleNode(int num) {
        data = num;
        pre = next = nullptr;
    }
};

class doubleQueue {
private:
    int dqSize;
    doubleNode *front, *rear;
public:
    doubleQueue() {
        dqSize = 0;
        front = rear = nullptr;
    }

    ~doubleQueue() {
        while (front) {
            doubleNode *temp = front;
            front = front->next;
            delete temp;
        }
    }

    int size() {
        return dqSize;
    }

    bool isEmpty() {
        return size() == 0;
    }


    void pushFront(int num) {
        push(num, true);
    }

    void pushRear(int num) {
        push(num, false);
    }

    int getFront(){
        if(isEmpty()) throw std::out_of_range("双向队列为空");
        return front->data;
    }

    int getRear(){
        if(isEmpty()) throw std::out_of_range("双向队列为空");
        return rear->data;
    }

    void push(int num, bool isFront) {

        auto *node = new doubleNode(num);
        if (isEmpty()) {
            front = rear = node;
            dqSize++;
        } else if (isFront) {      // 插入元素到双向队列头
            front->pre = node;
            node->next = front;
            front = node;
            dqSize++;
        } else {                  // 插入元素到双向队列的队尾
            rear->next = node;
            node->pre = rear;
            rear = node;
            dqSize++;
        }

    }

    int popFront() {
        if (isEmpty()) throw std::out_of_range("双向队列为空");
        int num = front->data;
        dqSize--;
        doubleNode *temp = front;
        front = front->next;
        delete temp;
        return num;
    }

    int popRear() {
        if (isEmpty()) throw std::out_of_range("双向队列为空");

        int num = rear->data;
        dqSize--;
        doubleNode *temp = rear;
        rear = rear->pre;
        delete temp;
        return num;
    }
};


#endif //CPRIMER_DOUBLEQUEUE_H