[CTDL] Queue – Hàng đợi | Phần 2. Cài đặt Queue bằng Linked List

Queue – Linked List Implementation

Bởi

8 Tháng Mười, 2020

895

🔥CHỌN LỌC TOP NHỮNG KHOÁ HỌC LẬP TRÌNH ONLINE NHIỀU NGƯỜI THEO HOC TẠI ĐÂY🔥

Chào ace, bài này chúng ta sẽ tìm hiểu về Cài đặt Queue bằng Linked List trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.

Trong bài học trước, chúng ta đã được giới thiệu về Queue và tìm hiểu cách cài đặt Queue bằng mảng một chiều. Trong bài này chúng ta sẽ tìm hiểu về cách cài đặt Queue bằng Linked List.

Khi cài đặt Queue bằng Linked List, chúng ta phải duy trì hai con trỏ, front và rear. Con trỏ front trỏ đến phần tử đầu tiên của Queue, và con trỏ rear trỏ đến phần tử cuối cùng của Queue. Hai thao tác xử lý dữ liệu chính sẽ được cài đặt là:

– enQueue(): Chèn thêm một node mới vào sau node rear và di chuyển con trỏ rear node tiếp theo (tức là làm cho con trỏ rear trỏ tới node tiếp theo)

– deQueue(): Xóa node front (node nằm ở đầu Queue) và di chuyển con trỏ front tới node tiếp theo (tức là làm cho con trỏ front trỏ tới node tiếp theo)

Dưới đây là các đoạn code cài đặt Queue bằng Linked List và hai thao tác xử lý dữ liệu chính là enqueue và dequue, được mô tả bằng các ngôn ngữ lập trình khác nhau:

ĐOẠN CODE CÀI ĐẶT QUEUE BẰNG LINKED LIST SỬ DỤNG C++ C JAVA PYTHON3 C#

C++

#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); 
    } 
}; 
  
// Driven Program 
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)->data << endl; 
    cout << "Queue Rear : " << (q.rear)->data; 
}


// 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 Program to test anove functions 
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->key); 
    printf("Queue Rear : %d", q->rear->key); 
    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 class 
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.key); 
        System.out.println("Queue Rear : " + q.rear.key); 
    } 
}

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)) 
    print("Queue Rear " + str(q.rear.data))

// 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 { 
    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 
        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(); 
        Console.WriteLine("Queue Front : " + q.front.key); 
        Console.WriteLine("Queue Rear : " + q.rear.key); 
    } 
}

Kết quả in ra là:

Queue Front : 40
Queue Rear : 50

Độ phức tạp về thời gian: Độ phức tạp về thời gian của cả hai thao tác enqueue() và dequeue() là O(1) bởi vì chúng ta chỉ thay đổi một vài con trỏ trong cả hai thao tác. Không có vòng lặp nào được sử dụng trong cả hai thao tác trên.

Nguồn và Tài liệu tiếng anh tham khảo:

Tài liệu từ cafedev:

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

Chào thân ái và quyết thắng!

[CTDL] Queue – Hàng đợi | Phần 2. Cài đặt Queue bằng Linked List

Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!

BÀI VIẾT TIÊU BIỂU

Tutorial | Làm thế nào để xây dựng một ứng dụng...

Tips | Tối ưu quá trình phát triển của bạn: các...

Tip | Chia sẻ cách lựa chọn Framework Frontend đúng đắn:...

BÀI VIẾT PHỔ BIẾN

Tổng hợp toàn bộ tài liệu học hướng đối tượng và...

Tổng hợp và chọn lọc bài tập SQL full hướng dẫn...

Giới thiệu chi tiết về CI-CD và những điều cần thiết...

MỤC XEM NHIỀU