Golang Data Structures: Stack

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 Last-In-First-Out (LIFO)¹.

Nếu chúng ta coi stack như 1 chiếc ống có 1 đầu ra thì, chúng ta chỉ có thể thêm hoặc bỏ những phần tử ở trên cùng (top) và không thể thêm phần tử mới vào cuối ống.

Đây là một trong những cấu trúc dữ liệu cơ bản và cực kỳ quan trọng trong lập trình. Stack có rất nhiều ứng dụng, để trực quan các bạn có thể tưởng tượng một chồng sách, bạn chỉ có thể lấy ra quyển sách ở trên cùng của chồng sách, nếu bạn muốn lấy ra cuốn sách cuối cùng, bạn phải lấy ra hết các cuốn sách ở phía trên nó.

Cách triển khai

Bên trong Stack 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 Stack.

• 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.
• Push(item): thêm một phần tử mới ở vị trí trên cùng.
• Pop(): lấy ra phần tử trên cùng.
• Len(): trả về số lượng phần tử còn lại trong stack.

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

package stack

import "sync"

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

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

// Push adds an Item to the top of the stack
func (s *IntStack) Push(i int64) {
	s.lock.Lock()
	defer s.lock.Unlock()
	s.items = append(s.items, &i)
}

// Pop removes an Item from the top of the stack
func (s *IntStack) Pop() *int64 {
	s.lock.Lock()
	defer s.lock.Unlock()

	if s.Len() == 0 {
		return nil
	}

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

	return item
}

// Len returns current length of the stack
func (s *IntStack) Len() 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

import (
	"fmt"
	"testing"
)

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

	fmt.Printf("current len: %v\n", st.Len())
	for  {
		item := st.Pop()
		if item == nil {
			break
		}
		fmt.Printf("item: %v - len: %v\n", *item, st.Len())
	}
}

Ứng dụng

• Tính giá trị biểu thức đại số hậu tố: Biểu thức đại số hậu tố là biểu thức có toán tử nằm sau 2 toán hạng của nó, cũng không có dấu ngoặc. Ví dụ như biểu thức hậu tố của ((4 + 2) / 3) + 5 sẽ là 4 2 + 3 / 5 +. Đầu tiên, duyệt biểu thức theo thứ tự từ trái sang phải, khi gặp toán hạng thì đẩy vào stack. Sau đó, khi gặp toán tử, ta lấy 2 toán hạng trên cùng trong stack ra và thực hiện phép toán rồi lại đẩy kết quả vào stack.