请实现一个队列，支持以下操作：添加元素、删除第一个元素、获取第一个元素。
简介：请实现一个队列，支持以下操作：添加元素、删除第一个元素、获取第一个元素。
算法思路
算法思路：
在不使用 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 类。
