Cấu trúc dữ liệu và giải thuật: Ngăn xếp (Stack)

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át 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

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

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.

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.

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.

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

    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

func pushStack() {
        stack.push(40)

        printStack()
    }

2.5.3 Test pop stack

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.

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.

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.

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

https://github.com/pqhuy87it/MonthlyReport/tree/master/StackAndQueue

5. Tài liệu tham khảo

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks and Queues/Stacks and Queues.html https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues