第二章 表、栈和队列

链表

单链表

#include <iostream>
using namespace std;

// 定义节点结构体
struct Node {
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

// 定义单链表类
class SinglyLinkedList {
private:
    Node* head;
public:
    SinglyLinkedList() : head(nullptr) {}

    // 在链表末尾添加新节点
    void addAtEnd(int value);

    // 从链表中删除值为value的节点
    void remove(int value);

    // 打印链表内容
    void printList();
};

// 在链表末尾添加新节点
void SinglyLinkedList::addAtEnd(int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 从链表中删除值为value的节点
void SinglyLinkedList::remove(int value) {
    Node* temp = head;
    Node* prev = nullptr;

    if (temp != nullptr && temp->data == value) {
        head = temp->next;
        delete temp;
        return;
    }

    while (temp != nullptr && temp->data != value) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == nullptr) return; // 如果没有找到值，则返回

    prev->next = temp->next;
    delete temp;
}

// 打印链表内容
void SinglyLinkedList::printList() {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    SinglyLinkedList list;

    list.addAtEnd(1);
    list.addAtEnd(2);
    list.addAtEnd(3);
    list.printList(); // 输出: 1 2 3

    list.remove(2);
    list.printList(); // 输出: 1 3

    return 0;
}

双链表

#include <iostream>
using namespace std;

// 定义节点结构体，包含数据、前驱指针和后继指针
struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int d) : data(d), prev(nullptr), next(nullptr) {}
};

// 定义双链表类
class DoublyLinkedList {
private:
    Node* head;
    Node* tail; // 追踪链表尾部

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    // 在链表末尾追加新节点
    void addAtEnd(int value);

    // 从链表中删除值为value的节点
    void remove(int value);

    // 打印链表内容
    void printList();
};

// 在链表末尾追加新节点
void DoublyLinkedList::addAtEnd(int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        head = newNode;
        tail = newNode;
    } else {
        newNode->prev = tail;
        tail->next = newNode;
        tail = newNode;
    }
}

// 从链表中删除值为value的节点
void DoublyLinkedList::remove(int value) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == value) {
            if (temp->prev != nullptr) { // 不是头结点
                temp->prev->next = temp->next;
            } else { // 是头结点
                head = temp->next;
            }

            if (temp->next != nullptr) { // 不是尾节点
                temp->next->prev = temp->prev;
            } else { // 是尾节点
                tail = temp->prev;
            }

            delete temp;
            return;
        }
        temp = temp->next;
    }
}

// 打印链表内容
void DoublyLinkedList::printList() {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    DoublyLinkedList list;

    list.addAtEnd(1);
    list.addAtEnd(2);
    list.addAtEnd(3);
    list.printList(); // 输出: 1 2 3

    list.remove(2);
    list.printList(); // 输出: 1 3

    return 0;
}

---

栈

数组实现

#include <iostream>
#include <stdexcept> // 为了使用 std::out_of_range

class ArrayStack {
private:
    int* stack;
    int capacity;
    int top;

public:
    ArrayStack(int size) : capacity(size), top(-1) {
        stack = new int[size];
    }

    ~ArrayStack() {
        delete[] stack;
    }

    void push(int value);
    int pop();
    int peek();
    bool isEmpty();
    bool isFull();
};

void ArrayStack::push(int value) {
    if (isFull()) {
        throw std::out_of_range("Stack is full.");
    }
    top++;
    stack[top] = value;
}

int ArrayStack::pop() {
    if (isEmpty()) {
        throw std::out_of_range("Stack is empty.");
    }
    int value = stack[top];
    top--;
    return value;
}

int ArrayStack::peek() {
    if (isEmpty()) {
        throw std::out_of_range("Stack is empty.");
    }
    return stack[top];
}

bool ArrayStack::isEmpty() {
    return top == -1;
}

bool ArrayStack::isFull() {
    return top == capacity - 1;
}

int main() {
    ArrayStack s(5); // 创建一个容量为5的栈

    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);

    try {
        s.push(6); // 这里会抛出异常，因为栈已经满了
    } catch (const std::out_of_range& e) {
        std::cout << e.what() << std::endl;
    }

    while (!s.isEmpty()) {
        std::cout << s.pop() << " ";
    }
    std::cout << std::endl;

    return 0;
}

链表实现

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

class LinkedListStack {
private:
    Node* top;

public:
    LinkedListStack() : top(nullptr) {}

    void push(int value);
    int pop();
    int peek();
    bool isEmpty();
};

void LinkedListStack::push(int value) {
    Node* newNode = new Node(value);
    newNode->next = top;
    top = newNode;
}

int LinkedListStack::pop() {
    if (isEmpty()) {
        throw std::out_of_range("Stack is empty.");
    }
    Node* temp = top;
    int value = temp->data;
    top = top->next;
    delete temp;
    return value;
}

int LinkedListStack::peek() {
    if (isEmpty()) {
        throw std::out_of_range("Stack is empty.");
    }
    return top->data;
}

bool LinkedListStack::isEmpty() {
    return top == nullptr;
}

int main() {
    LinkedListStack s;

    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);

    while (!s.isEmpty()) {
        std::cout << s.pop() << " ";
    }
    std::cout << std::endl;

    return 0;
}

---

队列

数组实现

#include <iostream>
using namespace std;
const int N = 100010;
int q[N];

//[hh, tt] 之间为队列（左闭右闭）
int hh = 0;//队头位置
int tt = -1;//队尾位置
//操作次数
int m;
//操作方式
string s;

//入队：队尾先往后移动一格，再放入要插入的数据
void push(int x){
    q[++tt] = x;
}
//出队：队头往后移动一格
void pop(){
    hh++;
}
//[hh, tt]表示队列区间，当tt >= hh时，区间不为空
void empty(){
    if(tt >= hh) cout << "NO" << endl;
    else cout << "YES" << endl;
} 
//hh指向队头，q[hh]代表队头元素
void query (){
    cout << q[hh] << endl;
}

链表实现

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

class LinkedListQueue {
private:
    Node* front;
    Node* rear;

public:
    LinkedListQueue() : front(nullptr), rear(nullptr) {}

    void enqueue(int value);
    int dequeue();
    int peekFront();
    bool isEmpty();
};

void LinkedListQueue::enqueue(int value) {
    Node* newNode = new Node(value);
    if (isEmpty()) {
        front = newNode;
    } else {
        rear->next = newNode;
    }
    rear = newNode;
}

int LinkedListQueue::dequeue() {
    if (isEmpty()) {
        throw std::out_of_range("Queue is empty.");
    }
    Node* temp = front;
    int value = temp->data;
    front = front->next;
    if (front == nullptr) {
        rear = nullptr; // 清空队列
    }
    delete temp;
    return value;
}

int LinkedListQueue::peekFront() {
    if (isEmpty()) {
        throw std::out_of_range("Queue is empty.");
    }
    return front->data;
}

bool LinkedListQueue::isEmpty() {
    return front == nullptr;
}

int main() {
    LinkedListQueue q;

    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5);

    while (!q.isEmpty()) {
        std::cout << q.dequeue() << " ";
    }
    std::cout << std::endl;

    return 0;
}

循环队列

#include <iostream>

class CircularQueue {
private:
    int front;        // 队头索引
    int rear;         // 队尾索引
    int capacity;     // 队列最大容量
    int *queue;       // 动态数组存储队列元素

public:
    CircularQueue(int size) : capacity(size), front(-1), rear(-1) {
        queue = new int[size];
    }

    ~CircularQueue() {
        delete[] queue;
    }

    bool isFull();
    bool isEmpty();
    void enqueue(int value);
    int dequeue();
    void display();
};

bool CircularQueue::isFull() {
    return ((rear + 1) % capacity == front);
}

bool CircularQueue::isEmpty() {
    return (front == -1);
}

void CircularQueue::enqueue(int value) {
    if (isFull()) {
        std::cout << "队列已满\n";
        return;
    }
    if (isEmpty()) {
        front = 0;
    }
    rear = (rear + 1) % capacity;
    queue[rear] = value;
    std::cout << "元素 " << value << " 入队成功\n";
}

int CircularQueue::dequeue() {
    if (isEmpty()) {
        std::cout << "队列为空\n";
        return INT_MIN; // 假设INT_MIN不是一个有效的队列值
    }
    int value = queue[front];
    if (front == rear) {
        front = -1;
        rear = -1;
    } else {
        front = (front + 1) % capacity;
    }
    return value;
}

void CircularQueue::display() {
    if (isEmpty()) {
        std::cout << "队列为空\n";
        return;
    }
    std::cout << "队列为: ";
    if (front <= rear) {
        for (int i = front; i <= rear; i++)
            std::cout << queue[i] << " ";
    } else {
        for (int i = front; i < capacity; i++)
            std::cout << queue[i] << " ";
        for (int i = 0; i <= rear; i++)
            std::cout << queue[i] << " ";
    }
    std::cout << "\n";
}

int main() {
    CircularQueue q(5); // 创建一个容量为5的循环队列

    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5);
    q.display(); // 应该显示 1 2 3 4 5

    q.dequeue(); // 删除元素1
    q.dequeue(); // 删除元素2
    q.display(); // 应该显示 3 4 5

    q.enqueue(6); // 入队元素6
    q.display(); // 应该显示 3 4 5 6

    return 0;
}