HÀNG ĐỢI QUEUE
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

Cài đặt hàng đợi Queue bằng danh sách liên kết

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách cài đặt hàng đợi Queue bằng danh sách liên kết. Đây là một trong hai cách hiệu quả nhất để cài đặt hàng đợi Queue.

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu cho Queue và thực hiện tạo các hàm cơ bản trên hàng đợi. Sau đó sử dụng các hàm đã tạo viết một chương trình nhập xuất đơn giản trong C++.

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

1. Cấu trúc dữ liệu của hàng đợi Queue

Hàng đợi là một cấu trúc trừu tượng, vì vậy để làm việc với nó ta cần tạo cấu trúc dữ liệu cho nó. Trong hướng dẫn này mình sử dụng danh sách liên kết để tạo Queue vì vậy đầu tiên ta cần có cấu trúc của một Node trong danh sách liên kết.

/* tạo cấu trúc của Node trong danh sách liên kết */
struct Node{
	Node *next;
	int data;
};

Tiếp đến là hai hàm khởi tạo rỗng cho Node và hàm tạo mới một Node, đây là những hàm mà chúng ta đã học ở các bài về danh sách liên kết

/* khởi tạo rỗng cho Node trong danh sách liên kết */
void Init( Queue &q ){
	q.head = q.tail = NULL;
}
/* hàm tạo một Node mới */
Node *createNode( int x ){
	Node *p = new Node;
	if(!p) exit(1);
	p->next = NULL;
	p->data = x;
	return p;
}

Cuối cùng là tạo một cấu trúc của hàng đợi Queue bằng cách sử dụng Node để tạo, bao gồm hai con trỏ là head và tail để quản lý phần tử đầu và phần tử cuối.

/* tạo cấu trúc của hàng đợi Queue */
struct Queue{
	Node *head, *tail;
};

2. Các hàm cơ bản trong hàng đợi Queue

Trong phần này mình sẽ thực hiện tạo một số hàm cơ bản cần thiết trong hàng đợi Queue: Push(), Top(), Pop().

Hàm Push

Hàm Push() là hàm để thêm các phần tử vào đầu hàng đợi, đây là một hàm rất quan trọng vì nếu không có dữ liệu trong hàng đợi thì ta không thể thực hiện các thao tác khác.

Việc đầu tiên ta sẽ kiểm tra xem hàng đợi có rỗng hay không, nếu trong Queue không tồn tại phần tử nào thì phần tử được thêm vào chính là pHead và pTail. Ngược lại nếu trong Queue đã tồn tại phần tử thì ta cho pNext của pTail trỏ tới node p.

/* hàm thêm phần tử vào đầu trong hàng đợi Queue */
void Push(Queue &q, Node *p ){
  //kiểm tra nếu hàng đợi rỗng thì phần tử thêm vào chính là pHead và pTail
	if(!q.head) q.head = q.tail = p;
  //Nếu trong danh sách đã tồn tại phần tử thì cho pNext của pTail trỏ tới node p
  //khi đó node p chính là pTail
	else{
		q.tail->next = p;
		q.tail = p;
	}
}

Hàm Top

Hàm Top() là hàm để lấy phần tử đầu tiên trong hàng đợi Queue nhưng không xóa nó khỏi Queue. Hay nói cách khác là nó chỉ hiển thị phần tử đầu tiên trong Queue.

Ta thực hiện kiểm tra nếu hàng đợi tồn tại phần tử thì return phần tử đó, ngược lại nếu trong hàng đợi rỗng thì return 0 và kết thúc hàm.

int Top(Queue q ){
  //kiểm tra nếu hàng đợi tồn tại phần tử thì ta thực hiện return phần tử đầu tiên
	if(q.head){
		return q.head->data;
	}
  //Nếu trong hàng đợi rỗng thì return 0 và kết thúc hàm
	else return 0;
}

Hàm Pop

Hàm Pop() là hàm xóa phần tử đầu tiên trong hàng đợi, đây là một hàm cũng khá quan trọng vì trong một số trường hợp ta cần phải xóa phần tử khỏi Queue.

Việc đầu tiên ta sẽ kiểm tra xem trong Queue có tồn tại phần tử hay không, nếu có tồn tại phần tử thì thực hiện các bước sau:

  • Tạo mới một Node p (là Node thay thế cho Node cần xóa).
  • Trỏ con trỏ Next đến phần tử tiếp theo để có thể xóa phần tử đầu.
  • Gán data cho p và return nó.
  • Thực hiện xóa p khỏi hàng đợi.
/* hàm xóa phần tử đầu trong hàng đợi */
int Pop(Queue &q ){
  //kiểm tra nếu hàng đợi tồn tại thì thực hiện các câu lệnh
	if(q.head){
    //tạo mới một Node p (là node thay thế cho node cần xóa)
		Node *p = q.head;
    //trỏ con trỏ Next đến phần tử tiếp theo để có thể xóa phần tử đầu
		q.head = q.head->next;
    //gán data cho p và return nó
		return p->data;
    //sau khi return thì thực hiện xóa nó khỏi hàng đợi
		delete p;
	}
	return 0;// tuong duong queue rong
}

3. Ví dụ về hàng đợi Queue

Trong ví dụ này mình sẽ sử dụng các hàm đã tạo ở trên để thêm một số phần tử và hàng đợi, sau đó tạo một menu với các thao tác như:

  • Thêm phần tử vào Queue.
  • Xuất các phần tử trong Queue.
  • Lấy phần tử đầu tiên trong Queue.
  • Xóa phần tử đầu tiên trong Queue.

Các bạn có thể tham khảo code của mình dưới đây, trong đó mình đã có chú thích rõ ràng.

Full code:

/**** Tạo hàng đợi Queue bằng danh sách liên kết đơn ****/
#include<iostream>
using namespace std;
/* tạo cấu trúc của Node trong danh sách liên kết */
struct Node{
	Node *next;
	int data;
};
/* tạo cấu trúc của hàng đợi Queue */
struct Queue{
	Node *head, *tail;
};
/* khởi tạo rỗng cho Node trong danh sách liên kết */
void Init( Queue &q ){
	q.head = q.tail = NULL;
}
/* hàm tạo một Node mới */
Node *createNode( int x ){
	Node *p = new Node;
	if(!p) exit(1);
	p->next = NULL;
	p->data = x;
	return p;
}
/* hàm thêm phần tử vào đầu trong hàng đợi Queue */
void Push(Queue &q, Node *p ){
  //kiểm tra nếu hàng đợi rỗng thì phần tử thêm vào chính là pHead và pTail
	if(!q.head) q.head = q.tail = p;
  //Nếu trong danh sách đã tồn tại phần tử thì cho pNext của pTail trỏ tới node p
  //khi đó node p chính là pTail
	else{
		q.tail->next = p;
		q.tail = p;
	}
}
/* hàm lấy phần tử đầu trong hàng đợi, nhưng không xóa nó */
int Top(Queue q ){
  //kiểm tra nếu hàng đợi tồn tại phần tử thì ta thực hiện return phần tử đầu tiên
	if(q.head){
		return q.head->data;
	}
  //Nếu trong hàng đợi rỗng thì return 0 và kết thúc hàm
	else return 0;
}
/* hàm xóa phần tử đầu trong hàng đợi */
int Pop(Queue &q ){
  //kiểm tra nếu hàng đợi tồn tại thì thực hiện các câu lệnh
	if(q.head){
    //tạo mới một Node p (là node thay thế cho node cần xóa)
		Node *p = q.head;
    //trỏ con trỏ Next đến phần tử tiếp theo để có thể xóa phần tử đầu
		q.head = q.head->next;
    //gán data cho p và return nó
		return p->data;
    //sau khi return thì thực hiện xóa nó khỏi hàng đợi
		delete p;
	}
	return 0;// tuong duong queue rong
}
/* hàm nhập các phần tử vào hàng đợi */
void nhap(Queue &q ){
	int n, x;
  cout<<"Nhập số phần tử bạn muốn thêm vào trong Queue: ";
	cin>> n;
	while(n--){
		cout<<"\nNhập phần tử trong hàng đợi: "; cin>> x;
		Node *p = createNode(x);
		Push(q,p);
	}
}
/* hàm xuất các phần tử trong hàng đợi */
void xuat(Queue q ){
	Node *p = q.head;
	while(p){
		cout<<p->data << "\t";
		p = p->next;
	}
	cout<< endl;
}
/* hàm menu để hiển thị menu và gọi các hàm đã tạo */
void menu(Queue q){
  int lc;
  do{
        cout << "\n\n\t\t ============== Menu ==============";
        cout << "\n\t1. Nhập phần tử cho hàng đợi";
        cout << "\n\t2. Xuất phần tử trong hàng đợi";
        cout << "\n\t3. Hiển thị phần tử đầu tiên của hàng đợi";
        cout << "\n\t4. Xóa phần tử đầu tiên của hàng đợi";
        cout << "\n\t0. Thoát";
        cout << "\n\n\t\t ============== End ==============";
    cout<<"\nNhập lựa chọn bạn muốn chọn: ";
        cin>> lc;
        switch(lc){
            case 0: break;
            case 1: 
              nhap(q);
              break;
            case 2:
              cout<<"Các phần tử trong hàng đợi Queue là: ";
              xuat(q);
              break;
            case 3:
              cout<<"Phần tử đầu tiên của hàng đợi là: "<<Top(q);
              break;
            case 4:
              Pop(q);
              cout<<"Xóa thành công, vui lòng nhập 2 để kiểm tra lại!!";
              break;
            default: cout<<"\nNhập sai, vui lòng nhập lại!";
        }
    } while(lc);
}
/* hàm main để hiển thị menu*/
int main(){
	Queue q;
	Init(q);
  int lc;
  menu(q);
  cout<<"\n---------------------------------\n";
  cout<<"Chương trình này được đang tại Freetuts.net";
}

Kết quả: Mình đã sử dụng thao tác 1 và 2 trong menu, các bạn có thể kiểm tra các thao tác khác nhé.

queue dlsk PNG

4. Kết luận

Như vậy là chúng ta đã tìm hiểu xong cách cài đặt hằng đợi Queue bằng danh sách liên kết, cũng như tạo các hàm cơ bản trong Queue. Các bạn hãy luyện tập nó thật nhiều để có thể ghi nhớ nhớ thật lâu nhé. Ở bài tiếp theo mình sẽ hướng dẫn các bạn cách cài đặt Queue bằng mảng một chiều, hãy chú ý theo dõi nhé !!

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Tìm kiếm phần tử k trong danh sách liên kết đôi

Tìm kiếm phần tử k trong danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu cách tìm kiếm một phần tử k trong…

Top