Bài viết
Cấu trúc dữ liệu và giải thuật: Ngăn xếp (Stack) trong Swift
1. Ngăn xếp(stack) là gì
- Ngăn xếp là 1 dạng đặc biệt của danh sách liên kết mà việc bổ sung hay loại bỏ 1 phần tử đều thực hiện ở 1 đầu của danh sách gọi là đỉnh.
- Ngăn xếp có 2 thao tác cơ bản: thêm phần tử vào được gọi là push và loại bỏ phần tử được gọi là pop.
- Việc loại bỏ phần tử sẽ tiến hành loại bỏ phần tử mới nhất được đưa vào danh sách, chính vì tính chất này mà ngăn xếp còn được gọi là kiểu dữ liệu LIFO(last in first out – Vào sau ra trước)
2. Khởi tạo stack
2.1 . Định nghĩa kiểu dữ liệu stack
- Vì stack là 1 dạng đặc biệt của danh sách liên kết nên ta có thể dùng kiểu dữ liệu Node đã trình bày ở bài danh sách liên kết để biểu diễn kiểu dữ liệu của stack
|
1
2
3
4
5
6
|
class Node < T > {
var key : T !
var next : Node ?
}
|
- Định nghĩa 1 class Stack với kiểu dữ liệu generic T và 1 node trên cùng gọi là top
|
1
2
3
4
5
|
class Stack < T > {
var top = Node < T > ( )
}
|
2.2. Thêm 1 phần tử vào ngăn xếp (push)
- Kiểm tra xem ngăn xếp có nil không, nếu nil thì gán đỉnh ngăn xếp vào phần tử muốn thêm vào.
- Nếu đỉnh ngăn xếp không nil, tạo 1 nút mới, gán phần tử muốn thêm vào nút đó, gán đỉnh ngăn xếp vào nút vừa tạo.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func push ( key : T ) {
// neu ngan xep chua co dinh
if top == nil {
top = Node < T > ( )
}
// neu dinh ngan xep rong
if top . key == nil {
top . key = key
return
} else { // khong thi tao 1 nut moi roi gan nut do vao dinh
let newNode = Node < T > ( )
newNode . key = key
newNode . next = top
top = newNode
}
}
|
2.3. Lấy 1 phần tử ra khỏi danh sách(pop)
- Kiểm tra danh sách đỉnh có rỗng không, nếu rỗng thì kết thúc.
- Nếu đỉnh danh sách không rỗng, kiểm tra nút đỉnh trỏ đến có rỗng không nếu rỗng thì gán đỉnh danh sách bằng nil( trường hợp danh sách chỉ có 1 phần sau khi lấy 1 phần tử ra thì danh sách trở thành rỗng), còn không gán đỉnh của danh sách vào nút tiếp theo.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func pop ( ) -> T ? {
// kiem tra xem dinh danh sach co rong khong
// neu rong thi ket thuc
guard let popItem = top . key else {
return
}
// kiem tra xem nut tiep theo cua dinh co rong khoong
if let nextNode = top . next {
top = nextNode
} else {
top = nil
}
return popItem
}
|
2.4. Xem phần tử đầu danh sách
- Kiểm tra xem đỉnh của danh sách có rỗng không, nếu rỗng thì trả về nil còn không trả về giá trị của đỉnh danh sách.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
func peek ( ) -> T ? {
// kiem tra xem dinh dach sach co rong khong
guard let topItem = top . key else {
// neu rong thi tra ve nil
return nil
}
// con khong tra ve gia tri dinh danh sach
return topItem
}
|
2.5. Test thử danh sách
2.5.1. Test build stack
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
func buildStack ( ) {
let numberList = [ 1 , 4 , 7 , 9 , 10 , 12 , 20 ]
for number in numberList {
stack . push ( number )
}
printStack ( )
}
func printStack ( ) {
var top = stack . top
print ( top . key )
while top . next != nil {
top = top . next
print ( top . key )
}
}
|
2.5.2. Test push stack
|
1
2
3
4
5
6
7
|
func pushStack ( ) {
stack . push ( 40 )
printStack ( )
}
|
2.5.3 Test pop stack
|
1
2
3
4
5
6
|
func popStack ( ) {
let item = stack . pop ( )
print ( item )
}
|
3. Một số ứng dụng của ngăn xếp
3.1. Đảo ngược xâu ký tự
- Bài toán đảo ngược xâu ký tự yêu cầu hiển thị các ký tự của 1 xâu ký tự theo chiều ngược lại.
- Ký tự cuối cùng của xâu sẽ được hiển thị trước, tiếp theo là ký tự sát ký tự cuối … và ký tự đầu tiên sẽ được hiển thị đầu tiên.
- Để giải quyết bài toán, ta chỉ cần duyệt từ đầu đến cuối xâu, lần lượt cho các ký tự vào ngăn xếp.
- Khi đó, các ký tự đầu tiên sẽ vào trước, tiếp theo đến ký tự thứ 2 … ký tự cuối cùng vào sau cùng. Sau khi đã cho toàn bộ ký tự của xâu vào ngăn xếp, lần lượt lấy các phần tử ra khỏi ngăn xếp và hiển thị lên màn hình.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
func reverseString ( stringInput : String ) -> String {
let stringStack = Stack < String > ( )
for s in stringInput . characters {
stringStack . push ( String ( s ) )
}
var newString = ""
var item = stringStack . top
newString += item . key
while item . next != nil {
item = item . next
newString += item . key
}
return newString
}
|
3.2. Tính giá trị biểu thức dạng hậu tố
3.2.1. Bài toán
- Một biểu thức toán học thông thường bao gồm các toán tử: + – * / , các toàn hạng và dấu ngoặc cho biết thứ tụ tính toán.
- Chẳng hạn 1 biểu thức toán học: (3 * (((5 – 2) * (7 + 1)) – 6)) Như chúng ta đã thấy trong biểu thức trên , các toán tử bao h cũng nằm giữa 2 toàn hạng. Do vậy, cách viết trên được gọi là cách viết trung tố (infix). Để tính toán giá trị biểu thức trên, ta phải tính toán giá trị các phép toán trong ngoặc trước. Đôi khi ta cần lưu các kết quả tính toán này như 1 kết quả trung gian, sau đó sử dụng chúng như toán hạng tiếp theo. Ví dụ ở biểu thức trên, đầu tiên ta tính 5 – 2 = 3, lưu kết quả này lại. Trong các biểu thức dạng này, vị trí dấu ngoặc rất quan trọng. Nếu vị trí các dấu ngoặc thay đổi thì giá trị biểu thức cũng thay đổi theo. Đối với con người, cách trình bày biểu thức toán học theo dạng này có vẻ như là hợp lý nhất, nhưng đối với máy tính, việc tính toán nhũng biểu thức như vậy là tương đối phức tạp. Để dễ dạng cho máy tính trong việc tính toán các biểu thức, người ta đưa ra 1 cách trình bày khác cho biểu thức toán học, đó là dạng hậu tố (postfix).
- Theo cách trình bày nay, toán tử không nằm giữa 2 toán hạng mà nằm ở ngay phía sau 2 toán hạng. Chẳng hạn ở biểu thức trên ta có thể viết dưới dạng hậu tố như sau: 3 5 2 – 7 1 + * 6 – * Toán tử – nằm ngay sau 2 toán hạng 5 và 2 nên lấy 5 – 2 = 3, lưu kết quả 3. Toán tử + nằm ngay sau 2 toán hạng 7 và 1 nên lấy 7 + 1 = 8, lưu kết quả 8. Toán tử * nằm ngay sau 2 kết quả vừa lưu nên lấy 3 * 8 = 24, lưu kết quả 24. Toán tử – nằm ngay sau kết quả vừa lưu và 6 nên lấy 24 – 6 = 18 Toán tử * nằm ngay sau kết quả vừa lưu và 3 nên lấy 3 * 18 = 54 là kết quả cuối cùng của biểu thức.
3.2.2. Cách thực hiện
Chuyển đổi biểu thức tiền tố sang hậu tố:
- Duyệt từ trái qua phải.
- Nếu gặp dấu mở ngoặc thì bỏ qua.
- Nếu gặp số thì đưa vào biểu thức mới.
- Nếu gặp toán tử thì đưa vào ngăn xếp.
- Nếu gặp dấu đóng ngoặc thì lấy toán tử ra đưa vào biểu thức mới.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
func convertInfixToPostfixExpression ( infixExpression : String ) -> String {
let stackOperator = Stack < String > ( )
var postfixExpression = ""
for s in infixExpression . characters {
let x = String ( s )
if numbers . rangeOfString ( x ) != nil {
postfixExpression += x
} else if operators . rangeOfString ( x ) != nil {
stackOperator . push ( x )
} else if x == ")" { // gap dau dong ngoac lay toan tu ra dua vao bieu thuc moi
let _operator = stackOperator . pop ( )
postfixExpression += _operator !
} else { // dau mo ngoac bo qua
}
}
return postfixExpression
}
|
Tính toán biểu thức hậu tố:
- Duyệt biểu thức từ trái qua phải.
- Nếu gặp toán hạng thì đưa vào ngăn xếp.
- Nếu gặp toán tử, lấy ra 2 toán hạng từ ngăn xếp, sử dụng toán tử để tính, sau đó đưa kết quả vào ngăn xếp.
|
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
|
func calculateInfixExpression ( ) {
let infixExpression = "(3*(((5-2)*(7+1))-6))"
let resultStack = Stack < Int > ( )
let postfixExpression = convertInfixToPostfixExpression ( infixExpression )
for s in postfixExpression . characters {
let x = String ( s )
if numbers . rangeOfString ( x ) != nil {
resultStack . push ( Int ( x ) ! )
} else if operators . rangeOfString ( x ) != nil {
let number1 = resultStack . pop ( ) !
let number2 = resultStack . pop ( ) !
let result = calculate ( number1 , number2 : number2 , _operator : x )
resultStack . push ( result )
} else {
}
}
print ( resultStack . top . key )
}
|
4. Demo
Có thể bạn chưa biết:
- Các giai đoạn ứng dụng nền tảng điện toán di động (mobility) trong doanh nghiệp
- App chăm sóc thú cưng, dịch vụ thú y
- Quản lý thông minh, tiết kiệm chi phí, tăng doanh thu trên kênh phân phối
- Microsoft thừa nhận tablet và mobile đang chiếm ưu thế hơn destop và laptop
- Tại sao Nodejs chạy nhanh hơn Apache?
- Nền tảng mạng xã hội nguồn mở cho giáo dục - Elgg
- Lập trình viên đừng ở trong bóng tối?
- Cuộc chiến giữa Google và Uber mới chỉ bắt đầu?
- Khám phá những điều bí ẩn của vũ trụ
- Cách xoá tất cả hình ảnh trên iPhone và iPad cùng lúc
- Microsoft trình làng Python Language Server dành cho Visual Studio Code
- Sổ tay Git cơ bản cần phải biết khi đi làm
DVMS chuyên:
- Tư vấn, xây dựng, chuyển giao công nghệ Blockchain, mạng xã hội,...
- Tư vấn ứng dụng cho smartphone và máy tính bảng, tư vấn ứng dụng vận tải thông minh, thực tế ảo, game mobile,...
- Tư vấn các hệ thống theo mô hình kinh tế chia sẻ như Uber, Grab, ứng dụng giúp việc,...
- Xây dựng các giải pháp quản lý vận tải, quản lý xe công vụ, quản lý xe doanh nghiệp, phần mềm và ứng dụng logistics, kho vận, vé xe điện tử,...
- Tư vấn và xây dựng mạng xã hội, tư vấn giải pháp CNTT cho doanh nghiệp, startup,...
Vì sao chọn DVMS?
- DVMS nắm vững nhiều công nghệ phần mềm, mạng và viễn thông. Như Payment gateway, SMS gateway, GIS, VOIP, iOS, Android, Blackberry, Windows Phone, cloud computing,…
- DVMS có kinh nghiệm triển khai các hệ thống trên các nền tảng điện toán đám mây nổi tiếng như Google, Amazon, Microsoft,…
- DVMS có kinh nghiệm thực tế tư vấn, xây dựng, triển khai, chuyển giao, gia công các giải pháp phần mềm cho khách hàng Việt Nam, USA, Singapore, Germany, France, các tập đoàn của nước ngoài tại Việt Nam,…
Quý khách xem Hồ sơ năng lực của DVMS tại đây >>
Quý khách gửi yêu cầu tư vấn và báo giá tại đây >>