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ột slice 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ối Queue.
  • Dequeue(): lấy ra phần tử đầu tiên ở đầu Queue.
  • Front(): trở lại phần tử đầu tiên của Queue 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

package queue

import "sync"

type IntQueue struct {
	items []*int64
	lock  sync.RWMutex
}

// New creates a new queue
func New() *IntQueue {
	s := &IntQueue{}
	s.items = []*int64{}
	return s
}

// Enqueue adds an Item to the end of the queue
func (s *IntQueue) Enqueue(t int64) {
	s.lock.Lock()
	defer s.lock.Unlock()
	s.items = append(s.items, &t)
}

// Dequeue removes an Item from the start of the queue
func (s *IntQueue) Dequeue() *int64 {
	s.lock.Lock()
	defer s.lock.Unlock()

	if s.IsEmpty() {
		return nil
	}

	item := s.items[0]
	s.items = s.items[1:len(s.items)]
	return item
}

// Front returns the item next in the queue, without removing it
func (s *IntQueue) Front() int64 {
	s.lock.RLock()
	defer s.lock.RUnlock()
	item := s.items[0]
	return *item
}

// IsEmpty returns true if the queue is empty
func (s *IntQueue) IsEmpty() bool {
	return len(s.items) == 0
}

// Size returns the number of Items in the queue
func (s *IntQueue) Size() int {
	return len(s.items)
}

Test

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

package queue

import (
	"fmt"
	"testing"
)

func Test_IntQueue(t *testing.T) {
	st := New()
	st.Enqueue(9)
	st.Enqueue(8)
	st.Enqueue(7)
	st.Enqueue(6)

	fmt.Printf("current size: %v\n", st.Size())
	fmt.Printf("front item: %v\n", st.Front())
	for  {
		item := st.Dequeue()
		fmt.Printf("item: %v - len: %v\n", *item, st.Size())
		if st.IsEmpty() {
			break
		}
	}
}

Ứ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ất Palindrome 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ất Palindrome.

  1. Vào trước ra trước. ↩︎