C++数组模拟之单链表与双链表和栈和队列的实现过程

下面是一个完整的攻略。

1. 单链表的实现

单链表是一种常用的链式结构，其核心是节点(Node)和指针(pointer)：

• 节点：保存数据和指向下一个节点的指针
• 指针：用于连接各个节点

以下是单链表的核心代码：

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

// 单链表类
class LinkedList {
public:
    LinkedList(): head(nullptr) {}

    void add_front(int data); // 在链表头添加节点
    void add_back(int data); // 在链表尾添加节点
    void remove(int data); // 删除指定数据的节点
    void print(); // 打印链表内容

private:
    Node* head; // 头节点
};

其中，add_front和add_back方法分别是在链表头和链表尾添加节点，核心思路如下：

• 在链表头添加节点：

  1. 新建节点
  2. 将head节点作为新节点的下一个节点
  3. 将head更新为新节点

• 在链表尾添加节点：

  1. 新建节点
  2. 找到链表的最后一个节点
  3. 将最后一个节点的next指针指向新节点

remove方法的核心是找到要删除的节点以及更新节点的next指针。

print方法的核心是遍历链表，并输出每个节点的数据。

以下是add_front方法的示例：

void LinkedList::add_front(int data) {
    Node* new_node = new Node(data);
    new_node->next = head;
    head = new_node;
}

2. 双链表的实现

双链表和单链表类似，不同之处在于：

• 节点(Node)保存了指向上一个节点的指针(prev)和下一个节点的指针(next)
• add_front方法需要更新原head节点的prev指针，remove方法需要更新相关节点的prev和next指针

以下是双链表的核心代码：

// 双链表节点结构体
struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int d): data(d), prev(nullptr), next(nullptr) {}
};

// 双链表类
class DoublyLinkedList {
public:
    DoublyLinkedList(): head(nullptr), tail(nullptr) {}

    void add_front(int data); // 在链表头添加节点
    void add_back(int data); // 在链表尾添加节点
    void remove(int data); // 删除指定数据的节点
    void print(); // 打印链表内容

private:
    Node* head; // 头节点
    Node* tail; // 尾节点
};

以下是add_front方法的示例：

void DoublyLinkedList::add_front(int data) {
    Node* new_node = new Node(data);
    if (head == nullptr) { // 空链表
        head = new_node;
        tail = new_node;
    } else {
        new_node->next = head;
        head->prev = new_node;
        head = new_node;
    }
}

3. 栈的实现

栈(Stack)是一种基于先进后出(LIFO)的数据结构，其核心操作是压入(push)和弹出(pop)元素：

• 压入元素：将元素放在栈顶
• 弹出元素：取出栈顶元素

以下是栈的核心代码：

// 栈类
class Stack {
public:
    Stack(): top(-1) {}

    void push(int data); // 压入元素
    int pop(); // 弹出元素
    bool is_empty(); // 判断栈是否为空
    void print(); // 打印栈内容

private:
    static const int MAXSIZE = 100; // 栈最大容量
    int data[MAXSIZE]; // 栈数据
    int top; // 栈顶索引
};

其中，push方法的实现：

void Stack::push(int data) {
    if (top >= MAXSIZE - 1) { // 栈满
        cout << "Stack is full!" << endl;
        return;
    }
    data[++top] = data;
}

pop方法的实现：

int Stack::pop() {
    if (top < 0) { // 栈空
        cout << "Stack is empty!" << endl;
        return -1;
    }
    return data[top--];
}

4. 队列的实现

队列(Queue)是一种基于先进先出(FIFO)的数据结构，其核心操作是入队(enqueue)和出队(dequeue)：

• 入队：将元素加入队尾
• 出队：取出队头元素

以下是队列的核心代码：

// 队列类
class Queue {
public:
    Queue(): front(0), rear(0) {}

    void enqueue(int data); // 入队
    int dequeue(); // 出队
    bool is_empty(); // 判断队列是否为空
    void print(); // 打印队列内容

private:
    static const int MAXSIZE = 100; // 队列最大容量
    int data[MAXSIZE]; // 队列数据
    int front; // 队头索引
    int rear; // 队尾索引
};

其中，enqueue方法的实现：

void Queue::enqueue(int data) {
    if ((rear + 1) % MAXSIZE == front) { // 队列已满
        cout << "Queue is full!" << endl;
        return;
    }
    data[rear] = data; // 将数据放到队尾
    rear = (rear + 1) % MAXSIZE; // 更新尾指针
}

dequeue方法的实现：

int Queue::dequeue() {
    if (front == rear) { // 队列为空
        cout << "Queue is empty!" << endl;
        return -1;
    }
    int res = data[front]; // 取出队头元素
    front = (front + 1) % MAXSIZE; // 更新头指针
    return res;
}

5. 示例说明

以下是一个示例程序，分别展示了单链表、双链表、栈和队列的基本操作：

int main() {
    // 单链表示例
    LinkedList ll;
    ll.add_front(1);
    ll.add_front(2);
    ll.add_back(3);
    ll.add_back(4);
    ll.print();
    ll.remove(2);
    ll.print();

    // 双链表示例
    DoublyLinkedList dll;
    dll.add_front(1);
    dll.add_front(2);
    dll.add_back(3);
    dll.add_back(4);
    dll.print();
    dll.remove(2);
    dll.print();

    // 栈示例
    Stack s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.print();
    s.pop();
    s.print();

    // 队列示例
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.print();
    q.dequeue();
    q.print();

    return 0;
}

以上程序将输出以下结果：

2 -> 1 -> 3 -> 4
1 -> 3 -> 4
2 -> 1 -> 3 -> 4
1 -> 3 -> 4
3 -> 2 -> 1
3 -> 1
3 2 1
2 1
1 -> 2 -> 3
2 -> 3

阅读剩余 82%