Giới thiệu
Hàng đợi là một tập hợp các mục, trong đó mục đầu tiên được thêm vào danh sách, phải là mục đầu tiên được xóa tiếp theo. Vì vậy, khi các mục được thêm vào bộ sưu tập, nó ngày càng lớn về kích thước, tức là nó đang tăng về chiều dài. Bất cứ khi nào cần xóa bất kỳ mục nào, thì mục đó phải là mục đầu tiên được thêm vào. Nếu các mục được loại bỏ liên tục, thì mục tiếp theo bị loại bỏ, là mục thứ hai; thứ ba được gỡ bỏ sau đó, v.v.
Sau khi mục đầu tiên của danh sách ban đầu đã bị xóa, mục thứ hai trở thành mục đầu tiên. Sau khi mục thứ hai đã bị loại bỏ, mục thứ ba trở thành mục đầu tiên, v.v.
Một ví dụ thực tế tốt về hàng đợi là khi mọi người xếp hàng để chờ dịch vụ hoặc hàng hóa. Người đầu tiên được phục vụ trước trước người cuối cùng. Tuy nhiên, hàng đợi được nói đến trong hướng dẫn này là hàng đợi phần mềm, như được thiết kế trong C ++.
FIFO
FIFO là viết tắt của First-In, First-Out. Đó là một cách khác để đánh giá cao hàng đợi. Điều này có nghĩa là, mục đầu tiên vào danh sách, là mục đầu tiên cần được loại bỏ, bất cứ khi nào việc loại bỏ diễn ra. Phần đầu của danh sách được gọi là phần đầu hoặc phía trước; phần cuối của danh sách được gọi là phần sau hoặc phần đuôi.
Hoạt động cần thiết
Hàng đợi phần mềm phải có ít nhất các hoạt động sau:
xô
Thao tác này, thêm một phần tử mới ở phía sau hàng đợi. Thao tác này được gọi chính thức là enqueue.
sự thay đổi
Thao tác này loại bỏ phần tử đầu tiên của hàng đợi và phần tử thứ hai trở thành phần tử đầu tiên mới. Thao tác này chính thức được gọi là dequeue. Nó được gọi là pop trong C ++.
Bài viết này giải thích cách sử dụng cấu trúc dữ liệu hàng đợi C ++. Bạn nên biết con trỏ và tham chiếu C ++ để hiểu phần còn lại của bài viết này.
Lớp và Đối tượng
Lớp là một tập hợp các biến và hàm hoạt động cùng nhau, trong đó các biến không có giá trị được gán cho. Khi các giá trị được gán cho các biến, lớp sẽ trở thành một đối tượng. Các giá trị khác nhau được cung cấp cho cùng một lớp dẫn đến các đối tượng khác nhau; nghĩa là, các đối tượng khác nhau là cùng một lớp với các giá trị khác nhau. Tạo một đối tượng từ một lớp được cho là khởi tạo đối tượng.
Tên, hàng đợi, là một lớp. Một đối tượng được tạo từ lớp hàng đợi có tên do người lập trình chọn.
Một hàm thuộc về một lớp là cần thiết để khởi tạo một đối tượng từ lớp đó. Trong C ++, hàm đó có cùng tên với tên của lớp. Các đối tượng được tạo (khởi tạo) từ lớp có các tên khác nhau do người lập trình đặt cho chúng.
Tạo một đối tượng từ lớp có nghĩa là xây dựng đối tượng; nó cũng có nghĩa là tức thời.
Một chương trình C ++ sử dụng lớp hàng đợi, bắt đầu bằng các dòng sau ở đầu tệp:
#bao gồm#bao gồm
sử dụng không gian tên std;
Dòng đầu tiên là đầu vào / đầu ra. Dòng thứ hai là cho phép chương trình sử dụng tất cả các tính năng của lớp hàng đợi. Dòng thứ ba cho phép chương trình sử dụng các tên trong không gian tên chuẩn.
Quá tải một chức năng
Khi hai hoặc nhiều chữ ký chức năng khác nhau có cùng tên, tên đó được cho là quá tải. Khi một hàm được gọi, số lượng và kiểu đối số sẽ xác định hàm nào thực sự được thực thi.
Sự thi công
xếp hàng<kiểu>Tên()Khai báo sau khởi tạo một hàng đợi có tên, hàng kiểu int.
xếp hàng<NS>điều đó;Hàng đợi trống. Khai báo bắt đầu bằng từ dành riêng, hàng đợi theo sau là dấu ngoặc nhọn với kiểu dữ liệu. Sau đó, bạn có tên lập trình viên cho hàng đợi.
Xây dựng với Danh sách Bộ khởi tạo
Định nghĩa sau đây cho thấy cách tạo hàng đợi với danh sách trình khởi tạo:
xếp hàng<trôi nổi>điều đó({1.1, 2,2, 3,3, 4.4});Hủy hàng đợi
Để hủy một hàng đợi, chỉ cần để nó ra khỏi phạm vi.
Quyền truy cập phần tử hàng đợi
đẩy (giá trị)
Hàng đợi là danh sách Nhập trước - Xuất trước. Vì vậy, mỗi giá trị được thêm vào từ phía sau. Đoạn mã sau tạo một hàng đợi trống, sau đó năm giá trị float được thêm vào từ phía sau:
xếp hàng<trôi nổi>điều đó;điều đó.xô(1.1);
điều đó.xô(2,2);
điều đó.xô(3,3);
điều đó.xô(4.4);
điều đó.xô(5.5);
size () const
Điều này trả về số phần tử trong hàng đợi. Đoạn mã sau minh họa:
xếp hàng<trôi nổi>điều đó;điều đó.xô(1.1);điều đó.xô(2,2);điều đó.xô(3,3);điều đó.xô(4.4);điều đó.xô(5.5);
Giá cả<<điều đó.kích thước() << ' ';
Đầu ra là 5.
đằng trước()
Điều này trả về một tham chiếu đến phần tử đầu tiên của hàng đợi, mà không xóa phần tử. Đầu ra của đoạn mã sau là 1.1.
xếp hàng<trôi nổi>điều đó;điều đó.xô(1.1);điều đó.xô(2,2);điều đó.xô(3,3);điều đó.xô(4.4);điều đó.xô(5.5);
Giá cả<<điều đó.đằng trước() << ' ';
Phần tử không bị xóa khỏi hàng đợi.
front () const
Khi cấu trúc hàng đợi được đặt trước bởi const, biểu thức front () const được thực thi thay vì front (). Ví dụ, nó được sử dụng trong đoạn mã sau.
hăng sôxếp hàng<trôi nổi>điều đó({1.1, 2,2, 3,3, 4.4, 5.5});Giá cả<<điều đó.đằng trước() << ' ';
Một tham chiếu không đổi được trả về. Phần tử không bị xóa khỏi vectơ. Không thể thay đổi các phần tử của hàng đợi.
mặt sau()
Điều này trả về một tham chiếu đến phần tử cuối cùng của hàng đợi, mà không xóa phần tử. Đầu ra của đoạn mã sau là 5.5.
xếp hàng<trôi nổi>điều đó;điều đó.xô(1.1);điều đó.xô(2,2);điều đó.xô(3,3);điều đó.xô(4.4);điều đó.xô(5.5);
Giá cả<<điều đó.mặt sau() << ' ';
back () const
Khi cấu trúc hàng đợi được đặt trước bởi const, biểu thức back () const được thực thi thay vì back (). Ví dụ, nó được sử dụng trong đoạn mã sau.
hăng sôxếp hàng<trôi nổi>điều đó({1.1, 2,2, 3,3, 4.4, 5.5});Giá cả<<điều đó.mặt sau() << ' ';
Một tham chiếu không đổi được trả về. Phần tử không bị xóa khỏi hàng đợi. Với const trước để xây dựng hàng đợi, các phần tử trong hàng đợi không thể thay đổi.
Dung lượng hàng đợi
size () const
- xem ở trên
rỗng () const
Điều này trả về 1 cho true nếu không có phần tử nào trong hàng đợi, hoặc 0 cho false nếu hàng trống. Đoạn mã sau minh họa điều này:
xếp hàng<trôi nổi>that1({1.1, 2,2, 3,3, 4.4, 5.5});Giá cả<<đó1.trống() << ' ';
xếp hàng<trôi nổi>that2;
Giá cả<<đó2.trống() << ' ';
Đầu ra là:
01
Công cụ sửa đổi hàng đợi
nhạc pop ()
Hàng đợi là FIFO, vì vậy bất kỳ phần tử nào bị xóa phải được xóa khỏi phần trên cùng (đầu) của hàng đợi. Hàm thành viên này loại bỏ phần tử đầu tiên mà không trả lại nó. Đoạn mã sau minh họa điều này:
xếp hàng<trôi nổi>điều đó({1.1, 2,2, 3,3, 4.4, 5.5});Giá cả<<điều đó.đằng trước() << ' ';
điều đó.nhạc pop();
Giá cả<<điều đó.kích thước() << ' ';
Đầu ra là:
1.14
a. hoán đổi (b)
Hai hàng đợi có thể được hoán đổi, như được minh họa trong đoạn mã này:
xếp hàng<trôi nổi>that1({1.1, 2,2, 3,3, 4.4, 5.5});xếp hàng<trôi nổi>that2({10, hai mươi});
đó1.tráo đổi(that2);
Giá cả<< 'Phần tử đầu tiên và kích thước của que1:
'<<đó1.đằng trước() <<','<<đó1.kích thước() << ' ';
Giá cả<< 'Phần tử đầu tiên và kích thước của que2'<<
đó2.đằng trước() <<','<<đó2.kích thước() << ' ';
Đầu ra là:
Phần tử đầu tiên và kích thước của que1: 10, 2
Phần tử đầu tiên và kích thước của que2: 1.1, 5
Lưu ý rằng độ dài của hàng đợi được tăng lên nếu cần. Ngoài ra, các giá trị không có giá trị thay thế sẽ được thay thế bằng một số giá trị mặc định. Các kiểu dữ liệu phải cùng kiểu.
Toán tử bình đẳng và quan hệ cho hàng đợi
Đối với các ký tự thông thường trong C ++, theo thứ tự tăng dần, các số đứng trước chữ hoa, trước chữ thường. Ký tự khoảng trắng đứng trước số 0 và tất cả chúng.
Các nhà điều hành bình đẳng
Trả về 1 cho true và 0 cho false.
Toán tử ==
Trả về 1 nếu hai hàng đợi có cùng kích thước và các phần tử tương ứng bằng nhau; nếu không nó trả về 0. Ví dụ:
xếp hàng<hăng sô char*>that1({'Tốt bụng', 'thứ gì khác'});xếp hàng<hăng sô char*>that2({'xấu xa'});
NStrên một=that1==that2;
Giá cả<<trên một<< ' ';
Đầu ra là: 0.
Toán tử! =
- ngược lại với điều trên. Thí dụ:
xếp hàng<hăng sô char*>that1({'Tốt bụng', 'thứ gì khác'});xếp hàng<hăng sô char*>that2({'xấu xa'});
NStrên một=that1! =that2;
Giá cả<<trên một<< ' ';
Đầu ra là: 1.
Toán tử quan hệ
Trả về 1 cho true và 0 cho false.
Các
Trả về 1 nếu hàng đợi đầu tiên là tập hợp con ban đầu của hàng đợi thứ hai, với các phần tử của hai phần bằng nhau giống nhau và theo cùng một thứ tự. Nếu cả hai hàng đợi có cùng kích thước hoặc kích thước khác nhau và di chuyển từ trái sang phải, một phần tử gặp phải trong hàng đợi đầu tiên nhỏ hơn phần tử tương ứng trong hàng thứ hai, thì 1 sẽ vẫn được trả về. Nếu không thì 0 được trả về. Thí dụ:
xếp hàng<hăng sô char*>that1({'Tốt bụng', 'thứ gì khác'});xếp hàng<hăng sô char*>that2({'xấu xa'});
NStrên một=that1<that2;
Giá cả<<trên một<< ' ';
Đầu ra là 1. Nhà điều hành> - ngược lại với điều trên. Thí dụ: Đầu ra: 0 Các<= Operator - giống như Đầu ra: 1 Toán tử> = - ngược lại với điều trên. Thí dụ: Đầu ra: 0 Giá trị là một kiểu dữ liệu, vì một đối tượng khởi tạo là một lớp. Cấu trúc hàng đợi cũng có thể chấp nhận một lớp làm kiểu dữ liệu. Chương trình sau minh họa điều này: Đầu ra là 5. Danh sách hàng đợi về mặt kỹ thuật được gọi là danh sách liên kết. Có hai loại danh sách được liên kết cho hàng đợi: danh sách được liên kết đơn và danh sách được liên kết kép. Một phần tử danh sách được liên kết đơn lẻ có thể được thực hiện bởi một cấu trúc gồm hai thành viên. Một thành viên giữ một con trỏ đến phần tử tiếp theo và thành viên còn lại giữ mức dữ liệu (số ít cho dữ liệu). Một phần tử danh sách được liên kết kép có thể được thực hiện bởi một cấu trúc gồm ba thành viên. Thành viên giữa giữ dữ liệu, trong khi thành viên thứ nhất và thứ ba giữ con trỏ đến các phần tử liền kề của chúng. Hàng đợi là một cấu trúc dữ liệu nhập trước xuất trước. Có những tình huống trong máy tính khi dữ liệu đến dưới dạng hàng đợi, đòi hỏi hành vi nhập trước xuất trước. Tài nguyên trong máy tính là bất kỳ thành phần vật lý hoặc ảo nào có tính khả dụng hạn chế. Chúng bao gồm CPU, thẻ video, ổ cứng và bộ nhớ. Chia sẻ một tài nguyên như vậy cần một hàng đợi. Các thiết bị ngoại vi của máy tính thỉnh thoảng cần ngắt máy tính. Các ngắt phải được xử lý giống như cách mà chúng đã đến. Điều này cần một hàng đợi. Ví dụ, hàng đợi có thể được sử dụng để quản lý các tệp ứng dụng cho một công việc, nếu các tệp được lưu trữ trong máy tính. Hàng đợi là một cấu trúc dữ liệu danh sách, là danh sách được liên kết đơn lẻ hoặc danh sách được liên kết kép. Theo quy luật, phần tử đầu tiên đi vào danh sách là phần tử đầu tiên xuất hiện. C ++ cung cấp cấu trúc dữ liệu hàng đợi trong thư viện chuẩn của nó. Các loại hàm thành viên và toán tử có sẵn cho cấu trúc này là xây dựng hàng đợi, truy cập phần tử hàng đợi, dung lượng hàng đợi, công cụ sửa đổi hàng đợi và toán tử nạp chồng hàng đợi. Bất kỳ cấu trúc dữ liệu hàng đợi nào cũng phải cung cấp ít nhất, các hàm thành viên push () và pop (). push () có nghĩa là, gửi một phần tử mới ở phía sau hàng đợi; và pop () có nghĩa là, loại bỏ phần tử ở phía trước hàng đợi. Thật không may, trong C ++, các hàm này không trả về giá trị được đẩy hoặc bật ra. Vì vậy, để biết phần tử cuối cùng trước khi push, bạn phải sử dụng thêm hàm back (); và để biết phần tử đầu tiên trước khi xuất hiện, phải sử dụng thêm hàm front (). Giá trị là một kiểu dữ liệu, vì một đối tượng khởi tạo là một lớp. Vì vậy, một lớp cụ thể có thể được sử dụng làm kiểu dữ liệu cho việc khởi tạo mẫu hàng đợi. Các đối tượng khác nhau cho lớp trở nên giống như các giá trị khác nhau cho lớp. Hàng đợi có ứng dụng trên máy tính. Ví dụ, nó có thể được sử dụng để quản lý các tệp ứng dụng cho một công việc, nếu các tệp được lưu trữ trong máy tính. Chrys
xếp hàng<hăng sô char*>that2({'xấu xa'});
NStrên một=that1>that2;
Giá cả<<trên một<< '
';
xếp hàng<hăng sô char*>that2({'xấu xa'});
NStrên một=that1<=that2;
Giá cả<<trên một<< '
';
xếp hàng<hăng sô char*>that2({'xấu xa'});
NStrên một=that1> =that2;
Giá cả<<trên một<< '
'; Lớp và các đối tượng khởi tạo của nó
#bao gồm
sử dụng không gian tên std;
lớp TheCla
{
công cộng:
NStrên một;
tĩnh charch;
vô hiệuhàm số(charkhông, hăng sô char *P)
{
Giá cả<< 'Có ' <<trên một<< 'sách đáng giá' <<không<<P<< ' trong cửa hàng.' << '
';
}
tĩnh vô hiệuniềm vui(charch)
{
nếu như (ch== 'đến')
Giá cả<< 'Chức năng thành viên tĩnh chính thức' << '
';
}
};
NSchủ chốt()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
xếp hàng<TheCla>điều đó;
điều đó.xô(obj1);điều đó.xô(obj2);điều đó.xô(obj3);điều đó.xô(obj4);điều đó.xô(obj5);
Giá cả<<điều đó.kích thước() << '
';
trở lại 0;
} Danh sách liên kết
Các ứng dụng của hàng đợi
Chia sẻ tài nguyên máy tính
Xử lý ngắt
Quản lý thông tin.
Phần kết luận