请实现一个队列，支持以下操作：添加元素、删除第一个元素、获取第一个元素。

GeekLiHua

发布于 2025-01-21 16:59:14

7110

文章被收录于专栏：JavaJava

请实现一个队列，支持以下操作：添加元素、删除第一个元素、获取第一个元素。

简介：请实现一个队列，支持以下操作：添加元素、删除第一个元素、获取第一个元素。

算法思路

算法思路：

在不使用 STL 库的情况下，我们可以通过手动维护队列底层数据结构的方式来实现队列。具体而言，我们可以采用链表这样一种数据结构来表示队列。

首先，我们需要定义一个 node 结构体，表示链表节点的数据结构：

struct Node {
    int val;
    Node* next;

    Node(int x) : val(x), next(NULL) {}
};

接着，我们定义 Queue 类来表示队列本身。在 Queue 类中，我们需要定义变量 head 和 tail 分别指向队列的头和尾，以及一个成员函数 push 用于添加元素，另外定义 pop 和 front 分别用于删除第一个元素和获取第一个元素：

class Queue {
public:
    Node *head, *tail;

    Queue() {
        head = tail = NULL;
    }

    void push(int x) { // 添加元素
        if (!head) {
            head = tail = new Node(x);
        } else {
            tail->next = new Node(x);
            tail = tail->next;
        }
    }

    void pop() { // 删除第一个元素
        if (head) {
            Node* tmp = head;
            head = head->next;
            delete tmp;
        } else {
            return;
        }
    }

    int front() { // 获取第一个元素
        if (head) {
            return head->val;
        } else {
            return -1;
        }
    }
};

最后，我们在主函数中创建一个 Queue 对象，调用其函数来执行相应操作即可：

#include <iostream>

using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int x) : val(x), next(NULL) {}
};

class Queue {
public:
    Node *head, *tail;

    Queue() {
        head = tail = NULL;
    }

    void push(int x) { // 添加元素
        if (!head) {
            head = tail = new Node(x);
        } else {
            tail->next = new Node(x);
            tail = tail->next;
        }
    }

    void pop() { // 删除第一个元素
        if (head) {
            Node* tmp = head;
            head = head->next;
            delete tmp;
        } else {
            return;
        }
    }

    int front() { // 获取第一个元素
        if (head) {
            return head->val;
        } else {
            return -1;
        }
    }
};

int main() {
    Queue q; // 创建一个队列

    // 添加元素
    q.push(1);
    q.push(2);
    q.push(3);

    // 获取第一个元素
    cout << "First element: " << q.front() << endl;

    // 删除第一个元素
    q.pop();

    // 获取删除后的第一个元素
    cout << "After pop, first element: " << q.front() << endl;

    return 0;
}

在上述代码实现中，我们定义了一个 Queue 变量来表示整个队列。通过手动维护链表的添加、删除和获取等操作，实现队列的基本功能。

Java版本

class Node {
    int val;
    Node next;

    Node(int x) {
        val = x;
        next = null;
    }
}

class Queue {
    private Node head; // 头节点
    private Node tail; // 尾节点

    public Queue() { // 构造函数
        head = tail = null;
    }

    public void push(int x) { // 添加元素
        if (head == null) {
            head = tail = new Node(x);
        } else {
            tail.next = new Node(x);
            tail = tail.next;
        }
    }

    public void pop() { // 删除第一个元素
        if (head != null) {
            Node tmp = head;
            head = head.next;
            tmp.next = null;
        }
    }

    public int front() { // 获取第一个元素
        if (head != null) {
            return head.val;
        } else {
            return -1;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Queue q = new Queue(); // 创建一个队列

        // 添加元素
        q.push(1);
        q.push(2);
        q.push(3);

        // 获取第一个元素
        System.out.println("First element: " + q.front());

        // 删除第一个元素
        q.pop();

        // 获取删除后的第一个元素
        System.out.println("After pop, first element: " + q.front());
    }
}

在上述代码实现中，我们定义了一个 Queue 变量来表示整个队列。通过手动维护链表的添加、删除和获取等操作，实现队列的基本功能。需要注意的是，在 Java 中采用 Node 类来表示链表节点，因此这里使用了一个 Node 类。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-06-13，如有侵权请联系 cloudcommunity@tencent.com 删除

队列