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

小灰灰 2024-03-16 17:11 68阅读 0赞

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

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

### 算法思路 ###

算法思路：

在不使用 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 类。