Hàng đợi là gì?
đuôi là các cấu trúc dữ liệu được sử dụng để lưu trữ và truy xuất các phần tử theo một thứ tự được xác định trước. Nó là một cấu trúc dữ liệu tuyến tính giống như một ngăn xếp và tuân theo FIFO (Nhập trước, Xuất trước) luật lệ. Nó có thể được so sánh với một danh sách chờ hoặc một hàng mà người đến đầu tiên được phục vụ trước. Các thành phần hiện có được loại bỏ từ phía trước của xếp hàng , và các yếu tố mới được thêm vào phía sau.
Triển khai hàng đợi trong Golang
Việc thực hiện một xếp hàng trong Go rất đơn giản và hiệu quả và có thể được triển khai bằng bốn phương pháp sau.
1: Lát
Trong Go, một lát cắt là một mảng động có thể thay đổi kích thước. Để thực hiện một xếp hàng sử dụng một lát cắt , chúng ta có thể thêm các phần tử vào mặt sau của lát cắt sử dụng chức năng nối thêm tích hợp và xóa các phần tử khỏi mặt trước của lát cắt sử dụng cắt lát.
Cách tiếp cận này rất dễ xây dựng và mang lại hiệu suất tốt cho các hoạt động chắp thêm và cắt nhờ các lát tích hợp sẵn của Go. Tuy nhiên, phương pháp cắt, bao gồm việc sao chép các phần tử sang một mảng mới bên dưới có thể trở nên không hiệu quả nếu xếp hàng mở rộng và yêu cầu các hoạt động xếp hàng lặp đi lặp lại.
Đoạn mã sau định nghĩa xếp hàng triển khai bằng cách sử dụng một lát cắt trong Go.
gói chính
nhập khẩu 'fmt'
chức năng chính ( ) {
xếp hàng := làm ( [ ] giao diện { } , 0 )
xếp hàng = nối thêm ( xếp hàng , 'Tiếng Anh' )
xếp hàng = nối thêm ( xếp hàng , 'tiếng urdu' )
xếp hàng = nối thêm ( xếp hàng , 'toán học' )
nếu như chỉ một ( xếp hàng ) > 0 {
mục := xếp hàng [ 0 ]
xếp hàng = xếp hàng [ 1 : ]
fmt. Println ( mục )
}
nếu như chỉ một ( xếp hàng ) == 0 {
fmt. Println ( 'Hàng đợi trống' )
} khác {
fmt. Println ( xếp hàng )
}
}
Mã Go ở trên sử dụng một lát cắt để xây dựng một cách đơn giản xếp hàng cấu trúc dữ liệu. Các nối thêm () chức năng được sử dụng để liệt kê các phần tử vào xếp hàng lát cắt và thao tác cắt lát loại bỏ phần tử ban đầu được sử dụng để loại bỏ chúng. Với fmt.Println() , phần tử dequeued được in. Đoạn mã sau đó sử dụng chỉ một() để xác định xem hàng đợi có trống không và nếu có, nó viết “ Xếp hàng trống” bằng cách sử dụng hàm fmt.Println().
đầu ra
2: Danh sách liên kết
Các nút mang một giá trị và một con trỏ tới nút tiếp theo trong danh sách tạo thành một danh sách được liên kết. Với hai con trỏ, một trỏ đến phía trước (đầu) của danh sách và một trỏ đến phía sau (đuôi), chúng ta có thể thực hiện một xếp hàng sử dụng danh sách liên kết. Xóa một mục khỏi hàng đợi (dequeuing) liên quan đến việc xóa nút ở đầu danh sách trong khi thêm một mục vào hàng đợi (enqueuing) liên quan đến việc thêm một nút mới vào cuối danh sách.
Phương pháp này cho phép thực hiện các hoạt động xếp hàng và xếp hàng hiệu quả vì chỉ cần thay đổi con trỏ đầu và đuôi, trái ngược với giải pháp dựa trên lát cắt nơi các phần tử sẽ cần được sao chép.
Sử dụng danh sách liên kết để thực hiện xếp hàng bằng cách sử dụng mã được cung cấp dưới đây:
gói chínhnhập khẩu 'fmt'
gõ nút cấu trúc {
giao diện giá trị { }
Kế tiếp * Nút
}
loại hàng đợi cấu trúc {
cái đầu * Nút
đuôi * Nút
}
chức năng chính ( ) {
xếp hàng := & Xếp hàng { cái đầu : không , đuôi : không }
nút mới := & Nút { giá trị : 'Tiếng Anh' , Kế tiếp : không }
xếp hàng. đuôi = nút mới
xếp hàng. cái đầu = nút mới
nút mới = & Nút { giá trị : 'tiếng urdu' , Kế tiếp : không }
xếp hàng. đuôi . Kế tiếp = nút mới
xếp hàng. đuôi = nút mới
nút mới = & Nút { giá trị : 'toán học' , Kế tiếp : không }
xếp hàng. đuôi . Kế tiếp = nút mới
xếp hàng. đuôi = nút mới
nếu như xếp hàng. cái đầu != không {
mục := xếp hàng. cái đầu . giá trị
xếp hàng. cái đầu = xếp hàng. cái đầu . Kế tiếp
fmt. Println ( mục )
}
nếu như xếp hàng. cái đầu == không {
fmt. Println ( 'Hàng đợi trống' )
}
}
Cấu trúc Nút đại diện cho từng mục trong hàng đợi và chứa hai trường: trường giá trị để lưu trữ giá trị của mục và trường tiếp theo để trỏ đến mục tiếp theo trong hàng đợi. Cấu trúc Queue sử dụng các thuộc tính head và tail để lần lượt theo dõi mặt trước và mặt sau của hàng đợi. Các đuôi mục đầu tiên được chỉ định bởi thuộc tính head, trong khi mục cuối cùng của nó được chỉ định bởi thuộc tính tail.
Các tham số đầu và đuôi ban đầu được đặt thành không khi mới xếp hàng được thiết lập trong hàm main(). Con trỏ đầu và đuôi được cập nhật để thêm ba nút vào xếp hàng với các giá trị “tiếng anh”, “tiếng urdu”, Và 'toán học'. Các 'Tiếng Anh' mục là sau đó “xếp hàng” (đã loại bỏ) từ phía trước của xếp hàng bằng cách hiển thị giá trị của nó và tiến con trỏ đầu tới nút sau trong xếp hàng . Sau khi dequeuing, nếu phần đầu trở thành null, điều đó có nghĩa là hàng đợi trống và thông báo “ Xếp hàng trống” được in ra.
đầu ra
3: Cấu trúc
Trong Go, bạn có thể tạo cấu trúc dữ liệu tùy chỉnh được gọi là cấu trúc đại diện cho một xếp hàng . Cái này cấu trúc có thể có các trường để lưu trữ xếp hàng các phần tử và phương thức để thêm và xóa các mục, kiểm tra xem hàng đợi có trống không và lấy kích thước hàng đợi hiện tại.
Cách này để tạo ra một xếp hàng in Go cung cấp một triển khai thuận tiện và gói gọn với các phương pháp dễ sử dụng có thể được mở rộng và tùy chỉnh với nhiều tính năng hơn. Đó là một cách tiếp cận linh hoạt cho phép thực hiện các thay đổi đối với việc triển khai hoặc thêm các khả năng mới bất cứ khi nào cần thiết.
Tạo tùy chỉnh cấu trúc với các phương thức liên quan đến việc viết mã bổ sung so với hai cách còn lại, điều này có thể làm tăng độ phức tạp. Tuy nhiên, nó cũng cung cấp sự linh hoạt và kiểm soát hơn đối với việc thực hiện các xếp hàng .
Ví dụ sau minh họa việc tạo một cấu trúc dữ liệu để biểu diễn một xếp hàng trong Go.
gói chínhnhập khẩu 'fmt'
loại hàng đợi cấu trúc {
mặt hàng [ ] giao diện { }
}
chức năng ( q * Xếp hàng ) xếp hàng ( giao diện mục { } ) {
q. mặt hàng = nối thêm ( q. mặt hàng , mục )
}
chức năng ( q * Xếp hàng ) xếp hàng ( ) giao diện { } {
nếu như chỉ một ( q. mặt hàng ) == 0 {
trở lại không
}
mục := q. mặt hàng [ 0 ]
q. mặt hàng = q. mặt hàng [ 1 : ]
trở lại mục
}
chức năng ( q * Xếp hàng ) Không có sản phẩm nào ( ) bool {
trở lại chỉ một ( q. mặt hàng ) == 0
}
chức năng ( q * Xếp hàng ) Kích cỡ ( ) int {
trở lại chỉ một ( q. mặt hàng )
}
chức năng chính ( ) {
xếp hàng := & Xếp hàng { mặt hàng : làm ( [ ] giao diện { } , 0 ) }
xếp hàng. xếp hàng ( 'Tiếng Anh' )
xếp hàng. xếp hàng ( 'tiếng urdu' )
xếp hàng. xếp hàng ( 'toán học' )
mục := xếp hàng. xếp hàng ( )
fmt. Println ( mục )
nếu như xếp hàng. Không có sản phẩm nào ( ) {
fmt. Println ( 'Hàng đợi trống' )
}
kích cỡ := xếp hàng. Kích cỡ ( )
fmt. Println ( 'Kích thước của hàng đợi:' , kích cỡ )
}
Trong đoạn mã trên, một mục được thêm vào lát cắt của mục đó thông qua hàng đợi() phương pháp, mà di chuyển nó đến cuối của xếp hàng . theo dõi Nhập trước, xuất trước (FIFO) nguyên tắc, các Dequeue() phương pháp đưa một mục ra khỏi phía trước của xếp hàng và trả lại nó. Độ dài của lát của mục được kiểm tra như một phần của IsEmpty() kiểm tra của phương pháp để xem nếu xếp hàng trống rỗng. Bằng cách trả về độ dài của lát mục, Kích cỡ() phương thức trả về hiện tại đuôi kích cỡ.
Hàm main() sử dụng cấu trúc hàng đợi để tạo một cái mới xếp hàng , thêm các phần tử vào nó, xóa các mục khỏi nó, xác định xem xếp hàng rỗng và tính kích thước của nó.
đầu ra
4: Kênh
Trong Go, loại kênh tích hợp có thể được sử dụng để triển khai xếp hàng cấu trúc dữ liệu. Kênh có thể được tạo với kích thước bộ đệm để giới hạn số lượng phần tử có thể được xử lý tại bất kỳ thời điểm nào. Để thêm một phần tử vào xếp hàng , nó có thể được gửi đến kênh bằng cách sử dụng <- toán tử, trong khi để xóa một phần tử khỏi hàng đợi, nó có thể được nhận từ kênh bằng cùng một toán tử.
Cách tiếp cận này có thể khá hữu ích trong các trường hợp truy cập đồng thời vào xếp hàng là bắt buộc, vì các kênh vốn đã an toàn để sử dụng đồng thời.
Điều quan trọng cần nhớ là các kênh Go được nhập. Điều này có nghĩa là bạn chỉ có thể gửi các giá trị thuộc một loại cụ thể qua một kênh và bạn chỉ có thể nhận các giá trị thuộc cùng loại đó từ kênh.
Đây là một minh họa về cách sử dụng một kênh để xây dựng một xếp hàng cấu trúc dữ liệu trong Go.
gói chínhnhập khẩu (
'fmt'
'thời gian'
)
loại hàng đợi cấu trúc {
vật phẩm chaninterface { }
}
funcNewQueue ( ) * Xếp hàng {
q := & Xếp hàng {
mặt hàng : làm ( giao diện chan { } ) ,
}
đi q. quá trìnhItems ( )
trở lại q
}
chức năng ( q * Xếp hàng ) quá trìnhItems ( ) {
vì mục := dãy q. mặt hàng {
nếu như mục == 'Tiếng Anh' {
fmt. Println ( 'Xếp hàng:' , mục )
}
}
}
chức năng ( q * Xếp hàng ) xếp hàng ( giao diện mục { } ) {
q. mặt hàng <- mục
}
chức năng chính ( ) {
xếp hàng := Hàng đợi mới ( )
xếp hàng. xếp hàng ( 'Tiếng Anh' )
xếp hàng. xếp hàng ( 'tiếng urdu' )
xếp hàng. xếp hàng ( 'toán học' )
thời gian . Ngủ ( 2 * thời gian . Thứ hai )
}
Đoạn mã trên tạo ra một cấu trúc hàng đợi với một lĩnh vực duy nhất mặt hàng đó là một kênh của giao diện{} kiểu. Các hàng đợi mới() chức năng tạo ra một phiên bản mới của Xếp hàng và khởi tạo nó 'mặt hàng' trường có kênh mới không có bộ đệm. Nó cũng bắt đầu một goroutine mới để xử lý các mục được thêm vào hàng đợi bằng cách sử dụng processItems() chức năng. Các processItems() chức năng kiểm tra xem mục nhận được có bằng không 'Tiếng Anh' và in một thông báo tới bảng điều khiển chỉ cho mục đó. Các hàng đợi() chức năng được sử dụng để thêm các mục mới vào hàng đợi.
đầu ra
Phần kết luận
Hàng đợi là một cấu trúc dữ liệu thiết yếu trong Go được sử dụng để lưu trữ và truy xuất các phần tử theo một thứ tự cụ thể. Việc thực hiện một xếp hàng trong Go an toàn theo luồng, khiến chúng trở thành lựa chọn lý tưởng để triển khai đồng thời trong các chương trình. Nó có thể được thực hiện bằng cách sử dụng các lát, danh sách được liên kết, cấu trúc và kênh. Các chi tiết đầy đủ đã được cung cấp trong các hướng dẫn nêu trên.