Một cấu trúc dữ liệu Stack được hiểu là một danh sách các phần tử được sắp xếp theo nguyên tắc First-In-First-Out (FIFO)1.
Nếu chúng ta coi Queue
là một ống dẫn với 2 đầu với 1 chiều truyền dữ liệu, thì dữ liệu đi vào từ đầu này sẽ đi ra ở đầu kia.
Queue
có rất nhiều ứng dụng trong thực tế, bạn có thể dễ dàng hình dung ra tính ứng dụng của nó trong thế giới thật. Ví dụ như một hàng đợi thanh toán trong siêu thị, hoặc hàng đợi mua vé trong rạp chiếu phim.
Cách triển khai
Bên trong Queue chúng ta có thể biểu diễn với dạng kiểu dữ liệu slice
của Golang. Ở đây tôi sẽ liệt kê những thao tác chính chúng ta có thể làm với một Queue
.
New()
: đóng vai trò như một phương thức khởi tạo mộtslice
nội bộ lưu trữ dữ liệu, trước khi chúng ta có thể sử dụng cấu trúc này.Enqueue()
: thêm một phần tử vào cuốiQueue
.Dequeue()
: lấy ra phần tử đầu tiên ở đầuQueue
.Front()
: trở lại phần tử đầu tiên củaQueue
nhưng không xóa đi.IsEmpty()
: kiểm tra queue hiện tại có đang rỗng hay không.Size()
: trả về kích thước hiện tại của queue.
Codes
|
|
Test
|
|
Ứng dụng
- Xử lý các chuỗi lệnh trong máy tính 1 cách tuần tự.
- Kiểm tra chuỗi
Palindrome
: Một chuỗi được gọi là có tính chấtPalindrome
nếu nó có tính chât đối xứng, tức là viết xuôi cũng giống viết ngược, ví dụ nhưaaAaa
. Để kiểm tra tính chất này của một chuỗi bất kì, ta đọc chuỗi bởi 2 cấu trúc riêng biệt là stack và queue. Sau đó, lấy ra từng phần tử trong stack và queue để so sánh với nhau. Nếu tất cả các phần tử trong stack đều giống với phần tử trong queue ở vị trí tương ứng thì chuỗi đó có tính chấtPalindrome
.
Vào trước ra trước. ↩︎