Анимационная демонстрация очереди на связном списке (с головным узлом)

在本文中，讨论并实现了队列数据结构的链表实现。如果队列为空，则打印“-1”。

方法： 要解决该问题，请遵循以下想法：

我们维护两个指针， front 和 after 。 front 指向队列的第一项， rear 指向最后一项。

enQueue()： 该操作在rear后面添加一个新节点，并将rear移动到下一个节点。

deQueue()： 该操作删除前面的节点并将前面的节点移动到下一个节点。

请按照以下步骤解决问题：

创建一个类 QNode，其数据成员为整数 data 和 QNode* next
- 参数化构造函数，采用整数 x 值作为参数，并将数据设置为等于 x ，并将 next 设置为 NULL
创建一个类Queue，数据成员QNode 前后
带参数 x 的入队操作：
- 使用 data = x 初始化 QNode* temp
- 如果后部设置为 NULL，则将前部和后部设置为 temp 并返回（Base Case）
- 否则将后部设置为温度旁边，然后将后部移至温度
出队操作：
- 如果前面设置为NULL则返回(Base Case)
- 使用 front初始化 QNode temp 并将 front 设置为其下一个
- 如果前面等于NULL 则将后面设置为NULL
- 从内存中删除温度

下面是上述方法的实现：

C++

              
                
                    // C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
struct QNode {
    int
                          data;
    QNode* next;
    QNode(int d)
    {
        data = d;
        next = NULL;
    }
};
 
struct Queue {
    QNode *front, *rear;
    Queue() { front = rear = NULL; }
 
    void enQueue(int x)
    {
 
        // Create a new LL node
        QNode* temp = new QNode(x);
 
        // If queue is empty, then
        // new node is front and rear both
        if (rear == NULL) {
            front = rear = temp;
            return;
        }
 
        // Add the new node at
        // the end of queue and change rear
        rear->next = temp;
        rear = temp;
    }
 
    // Function to remove
    // a key from given queue q
    void deQueue()
    {
        // If queue is empty, return NULL.
        if (front == NULL)
            return;
 
        // Store previous front and
        // move front one node ahead
        QNode* temp = front;
        front = front->next;
 
        // If front becomes NULL, then
        // change rear also as NULL
        if (front == NULL)
            rear = NULL;
 
        delete (temp);
    }
};
 
// Driver code
int main()
{
 
    Queue q;
                        
    q.enQueue(10);
    q.enQueue(20);
    q.deQueue();
    q.deQueue();
    q.enQueue(30);
    q.enQueue(40);
    q.enQueue(50);
    q.deQueue();
    cout << "Queue Front : " << ((q.front != NULL) ? (q.front)->data : -1)<< endl;
                        
    cout << "Queue Rear : " << ((q.rear != NULL) ? (q.rear)->data : -1);
}
// This code is contributed by rathbhupendra

                  

              
            

C

              
                
                    // A C program to demonstrate linked list based
// implementation of queue
                        
#include <stdio.h>
                        
#include <stdlib.h>
 
// A linked list (LL) node to store a queue entry
struct QNode {
    int
                          key;
    struct QNode* next;
};
 
// The queue, front stores the front node of LL and rear
// stores the last node of LL
struct Queue {
    struct QNode *front, *rear;
};
 
// A utility function to create a new linked list node.
struct QNode* newNode(int k)
{
    struct QNode* temp
        = (struct QNode*)malloc(sizeof(struct QNode));
    temp->key = k;
    temp->next = NULL;
    return temp;
}
 
// A utility function to create an empty queue
struct Queue* createQueue()
{
    struct Queue* q
        = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}
 
// The function to add a key k to q
void enQueue(struct Queue* q, int k)
{
    // Create a new LL node
    struct QNode* temp = newNode(k);
                        
 
    // If queue is empty, then new node is front and rear
    // both
    if
                          (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
 
    // Add the new node at the end of queue and change rear
    q->rear->next = temp;
    q->rear = temp;
}
 
// Function to remove a key from given queue q
void deQueue(struct Queue* q)
{
    // If queue is empty, return NULL.
    if
                          (q->front == NULL)
        return;
 
    // Store previous front and move front one node ahead
    struct QNode* temp = q->front;
                        
 
    q->front = q->front->next;
 
    // If front becomes NULL, then change rear also as NULL
    if
                          (q->front == NULL)
        q->rear = NULL;
 
    free(temp);
}
 
// Driver code
int main()
{
    struct Queue* q = createQueue();
                        
    enQueue(q, 10);
    enQueue(q, 20);
    deQueue(q);
    deQueue(q);
    enQueue(q, 30);
    enQueue(q, 40);
    enQueue(q, 50);
    deQueue(q);
    printf("Queue Front : %d \n", ((q->front != NULL) ? (q->front)->key : -1));
    printf("Queue Rear : %d", ((q->rear != NULL) ? (q->rear)->key : -1));
    return 0;
}

                  

              
            

Java

              
                
                    // Java program for linked-list implementation of queue
 
// A linked list (LL) node to store a queue entry
class QNode {
    int
                          key;
    QNode next;
 
    // constructor to create a new linked list node
    public
                          QNode(int key)
    {
        this.key = key;
        this.next = null;
    }
}
 
// A class to represent a queue
// The queue, front stores the front node of LL and rear
// stores the last node of LL
class Queue {
    QNode front, rear;
 
    public
                          Queue() { this.front = this.rear = null; }
                        
 
    // Method to add an key to the queue.
    void
                          enqueue(int key)
    {
 
        // Create a new LL node
        QNode temp = new QNode(key);
 
        // If queue is empty, then new node is front and
        // rear both
        if (this.rear == null) {
            this.front = this.rear = temp;
            return;
        }
 
        // Add the new node at the end of queue and change
        // rear
        this.rear.next = temp;
        this.rear = temp;
    }
 
    // Method to remove an key from queue.
    void
                          dequeue()
    {
        // If queue is empty, return NULL.
        if (this.front == null)
                        
            return;
 
        // Store previous front and move front one node
        // ahead
        QNode temp = this.front;
        this.front = this.front.next;
 
        // If front becomes NULL, then change rear also as
        // NULL
        if (this.front == null)
                        
            this.rear = null;
    }
}
 
// Driver code
public class Test {
    public
                          static void main(String[] args)
    {
        Queue q = new Queue();
        q.enqueue(10);
                        
        q.enqueue(20);
                        
        q.dequeue();
        q.dequeue();
        q.enqueue(30);
                        
        q.enqueue(40);
                        
        q.enqueue(50);
                        
        q.dequeue();
        System.out.println("Queue Front : " + ((q.front != null) ? (q.front).key : -1));
        System.out.println("Queue Rear : " + ((q.rear != null) ? (q.rear).key : -1));
    }
}
// This code is contributed by Gaurav Miglani

                  

              
            

Python3

              
                
                    # Python3 program to demonstrate linked list
# based implementation of queue
 
# A linked list (LL) node
                        
# to store a queue entry
                        
 
 
class Node:
 
    def
                          __init__(self, data):
        self.data =
                          data
        self.next
                          = None
 
# A class to represent a queue
 
# The queue, front stores the front node
# of LL and rear stores the last node of LL
 
 
class Queue:
 
    def
                          __init__(self):
        self.front =
                          self.rear = None
 
    def
                          isEmpty(self):
        return self.front ==
                          None
 
    # Method to add an item to the queue
    def
                          EnQueue(self, item):
        temp = Node(item)
 
        if self.rear ==
                          None:
            self.front =
                          self.rear = temp
            return
        self.rear.next = temp
                        
        self.rear =
                          temp
 
    # Method to remove an item from queue
    def
                          DeQueue(self):
 
        if self.isEmpty():
            return
        temp = self.front
        self.front =
                          temp.next
 
        if(self.front ==
                          None):
            self.rear =
                          None
 
 
# Driver Code
if __name__ ==
                          '__main__':
    q = Queue()
    q.EnQueue(10)
                        
    q.EnQueue(20)
                        
    q.DeQueue()
    q.DeQueue()
    q.EnQueue(30)
                        
    q.EnQueue(40)
                        
    q.EnQueue(50)
                        
    q.DeQueue()
    print("Queue Front : " + str(q.front.data if q.front !=
                          None else -1))
    print("Queue Rear : " + str(q.rear.data if q.rear !=
                          None else -1))

                  

              
            

C#

              
                
                    // C# program for linked-list
// implementation of queue
                        
using System;
 
// A linked list (LL) node to
// store a queue entry
class QNode {
    public
                          int key;
    public
                          QNode next;
 
    // constructor to create
    // a new linked list node
    public
                          QNode(int key)
    {
        this.key = key;
        this.next = null;
    }
}
 
// A class to represent a queue The queue,
// front stores the front node of LL and
// rear stores the last node of LL
class Queue {
    public
                          QNode front, rear;
 
    public
                          Queue() { this.front = this.rear = null; }
                        
 
    // Method to add an key to the queue.
    public
                          void enqueue(int key)
    {
 
        // Create a new LL node
        QNode temp = new QNode(key);
 
        // If queue is empty, then new
        // node is front and rear both
        if (this.rear == null) {
            this.front = this.rear = temp;
            return;
        }
 
        // Add the new node at the
        // end of queue and change rear
        this.rear.next = temp;
        this.rear = temp;
    }
 
    // Method to remove an key from queue.
    public
                          void dequeue()
    {
        // If queue is empty, return NULL.
        if (this.front == null)
                        
            return;
 
        // Store previous front and
        // move front one node ahead
        this.front = this.front.next;
 
        // If front becomes NULL,
        // then change rear also as NULL
        if (this.front == null)
                        
            this.rear = null;
    }
}
 
// Driver code
public class Test {
    public
                          static void Main(String[] args)
    {
        Queue q = new Queue();
        q.enqueue(10);
        q.enqueue(20);
        q.dequeue();
        q.dequeue();
        q.enqueue(30);
        q.enqueue(40);
        q.enqueue(50);
        q.dequeue();
        Console.WriteLine("Queue Front : " + ((q.front != null) ? (q.front).key : -1));
        Console.WriteLine("Queue Rear : " + ((q.rear != null) ? (q.rear).key : -1));
    }
}
 
// This code has been contributed by Rajput-Ji

                  

              
            

Javascript

              
                
                    <script>
// JavaScript program for linked-list implementation of queue
class QNode
{
    constructor(key)
    {
        this.key = key;
        this.next = null;
    }
}
 
let front = null, rear = null;
 
function enqueue(key)
{
    // Create a new LL node
        let temp = new QNode(key);
   
                        
        // If queue is empty, then new node is front and rear both
        if (rear == null) {
            front = rear = temp;
            return;
        }
   
                        
        // Add the new node at the end of queue and change rear
        rear.next = temp;
        rear = temp;
}
 
 
function dequeue()
{
    // If queue is empty, return NULL.
        if (front == null)
            return;
   
                        
        // Store previous front and move front one node ahead
        let temp = front;
        front = front.next;
   
                        
        // If front becomes NULL, then change rear also as NULL
        if (front == null)
            rear = null;
                        
}
 
 
enqueue(10);
enqueue(20);
dequeue();
dequeue();
enqueue(30);
enqueue(40);
enqueue(50);
dequeue();
document.write("Queue Front : " +  ((front != null) ? (front).key : -1) +"<br>");
document.write("Queue Rear : " +  ((rear != null) ? (rear).key : -1) +"<br>");
 
 
// This code is contributed by avanitrachhadiya2155
</script>

                  

              
            

输出

队列前面：40
队列后方：50

时间复杂度： O(1)，enqueue()和dequeue()操作的时间复杂度都是O(1)，因为它只改变两个操作中的几个指针辅助空间：O(1)，两个操作的
辅助空间enqueue() 和 dequeue() 的复杂度为 O(1)，因为需要恒定的额外空间

相关文章：
队列简介及数组实现