Ngăn xếp (stack) trong C#: cài đặt, ứng dụng, lớp Stack

    0

    Ngăn xếp (stack) là loại cấu trúc dữ liệu tập hợp được sử dụng cực kỳ phổ biến. Ngăn xếp, dù gián tiếp hay trực tiếp, đều luôn có mặt trong lập trình. Bạn có biết, mỗi khi bạn chạy phương thức, khai báo biến cục bộ, là lúc bạn đã làm việc với ngăn xếp? v.v..

    Tuy vậy, ngăn xếp lại rất “khiêm tốn” khiến bạn không hề hay biết về sự giúp đỡ của nó.

    Bài học này sẽ giúp bạn hiểu rõ hơn về cấu trúc và ứng dụng của ngăn xếp trong lập trình. Bạn cũng sẽ học cách cài đặt ngăn xếp đơn giản sử dụng ngôn ngữ C#. Cuối cùng, bạn sẽ làm quen với bản cài đặt “xịn” của ngăn xếp trên .NET framework và ứng dụng để cài đặt một số thuật toán.

    Ngăn xếp – cấu trúc truy xuất giới hạn với các phép toán đặc thù

    Cấu trúc truy xuất ngẫu nhiên và cấu trúc truy xuất giới hạn

    Trong các bài học trước bạn đã biết về các cấu trúc mảngdanh sách. Hai cấu trúc này thuộc về nhóm truy xuất ngẫu nhiên (random access). Lý do là vì mảng và danh sách cho phép truy xuất đến bất kỳ phần tử nào (sử dụng chỉ số).

    Bây giờ hãy tưởng tượng bạn có một chồng đĩa đặt trong hộp có nắp. Bạn chỉ có thể lấy cái đầu tiên trong hộp ngay sát nắp. Rõ ràng, bạn không thể lấy bất kỳ cái nào theo ý muốn được. Đó chính là truy xuất giới hạn.

    Ngăn xếp (học trong bài) này và hàng đợi (học trong bài tiếp theo) thuộc về nhóm cấu trúc dữ liệu truy xuất giới hạn (limited access). Các cấu trúc truy xuất giới hạn không cho phép bạn truy xuất phần tử bất kỳ theo ý muốn.

    Cấu trúc dữ liệu ngăn xếp

    Hãy tưởng tượng bạn có một chồng bao xi măng nặng trịch! Bạn chỉ có thể đặt thêm bao mới lên đầu chồng. Muốn lấy ra cũng phải theo tuần tự từng bao một từ đầu chồng. May ra chỉ có superman mới lấy được bao ở giữa chồng theo kiểu truy xuất ngẫu nhiên!

    Đây là hình ảnh minh họa cho cấu trúc ngăn xếp. Mỗi bao xi măng là một phần tử, nơi chứa dữ liệu. Bao ở trên cùng gọi là đỉnh. Thao tác đặt thêm bao xi măng mới trên đỉnh gọi là push; Thao tác lấy bao đỉnh ra gọi là pop.

    Rất dễ dàng hình dung ra, bao xi cuối cùng đặt vào cũng là bao đầu tiên có thể lấy ra để dùng. Mô hình vào cuối cùng – ra đầu tiên như thế có tên gọi chính thống là LIFO (Last-in, First-out).

    Ngăn xếp là một cấu trúc dữ liệu đệ quy (recursive data structure). Có nghĩa là một ngăn xếp, nếu nó không rỗng, có thể xem nó bao gồm đỉnh và một ngăn xếp con chứa tất cả các phần tử còn lại. Mỗi ngăn xếp con lại có thể tiếp tục được biểu diễn như vậy. Do đó, ngăn xếp rất hay được sử dụng cùng kỹ thuật đệ quy.

    Các phép toán trên ngăn xếp

    Như bạn đã thấy ở trên, Push – “Thêm phần tử vào đầu ngăn xếp” và pop – “lấy phần tử từ đầu ngăn xếp” là hai phép toán cơ bản của ngăn xếp.

    Phép toán Pop và Push trên ngăn xếp stack
    Phép toán Pop và Push trên ngăn xếp

    Để tiện lợi khi sử dụng, ngăn xếp cũng thực thi thêm một số phép toán khác.

    • Peek – mở bao xi ra xem ngay khi nó còn nằm ở đỉnh, nhưng không bỏ nó ra ngoài để dùng. Phép toán này cho phép chúng ta đọc dữ liệu từ phần tử trên đỉnh nhưng không bỏ nó ra khỏi ngăn xếp.
    • Count – đếm số phần tử đang có ngăn xếp.
    • Clear – xóa bỏ tất cả các phần tử của ngăn xếp.

    Cũng để ý rằng, Push có độ phức tạp O(1) nếu dung lượng ngăn xếp không đổi, hoặc O(n) trong trường hợp ngược lại. Pop và Peek đều có độ phức tạp O(1).

    Ngăn xếp quả thực không khó để hiểu đúng không ạ. Vậy nó được ứng dụng ở đâu mà chả khi nào thấy nó khi viết code?

    Một số ứng dụng quan trọng của ngăn xếp

    Ngăn xếp có vai trò vô cùng quan trọng trong các chương trình dịch và phân tích mã của ngôn ngữ lập trình. Dưới đây là một số ứng dụng tiêu biểu của ngăn xếp.

    Chuyển đổi cách biểu diễn, lưu trữ và thực hiện biểu thức toán

    Mỗi biểu thức có thể viết ở dạng prefix (dấu phép toán đi trước các toán hạng), postfix (dấu phép toán đi sau các toán hạng), hoặc infix (dấu phép toán đi giữa các toán hạng). Trong đó infix là dạng thức chúng ta sử dụng bình thường để viết các biểu thức toán. Dạng prefix là thông dụng nhất cho máy tính thực hiện.

    Dạng infix: 1 + 2 <=> Dạng prefix: + 1 2 <=> Dạng postfix: 1 2 +

    Tuy nhiên mỗi cách biểu diễn trên có ưu thế trong những tình huống nhất định. Kiểu infix chúng ta quen dùng nhưng không tiện lợi cho máy tính. Trên thực tế, các chương trình dịch khi gặp các biểu thức toán trong mã nguồn đều phải chuyển về kiểu biểu diễn prefix (hoặc đôi khi là postfix) thì mới thực hiện được tính toán biểu thức đó.

    Stack được dùng để chuyển đổi dạng biểu diễn của biểu thức. Sau khi chuyển đổi dạng biểu diễn, các toán hạng và toán tử tiếp tục được lưu trong một stack để thực hiện tính toán.

    Chúng ta sẽ thực hiện một ví dụ đơn giản về tính toán biểu thức từ chuỗi ở phần cuối của bài.

    Phân tích cú pháp của mã nguồn

    Mã nguồn (viết bằng các ngôn ngữ lập trình), như chúng ta biết, đều là các chuỗi văn bản được viết theo quy tắc nhất định, gọi là cú pháp của ngôn ngữ đó. Để đảm bảo văn bản tuân thủ cú pháp, người ta phải viết các chương trình phân tích cú pháp (parser).

    Một ví dụ về phân tích cú pháp là kiểm tra các dấu ngoặc nhọn mở đầu và kết thúc của các khối code (ví dụ, trong các ngôn ngữ tương tự C, bao gồm cả C#).

    Các trình biên dịch thường sử dụng stack để phân tích cú pháp của các biểu thức, các khối code, v.v., trước khi dịch sang mã cấp thấp.

    Trong lập trình chúng ta cũng thường xuyên cần phân tích một chuỗi ký tự kiểu mã nguồn. Ví dụ, chuỗi ký tự ở dạng JSON cũng có thể xem là một dạng mã nguồn. Khi đó, stack thường được sử dụng để phân tích và xử lý chuỗi.

    Thực thi phương thức/chương trình con

    Khi bạn chạy một phương thức/chương trình con, bạn thường cung cấp tham số và mong muốn nhận lại kết quả. Cái này được gọi là calling convention. Trong phương thức bạn lại có thể tiếp tục gọi các phương thức khác (nesting – gọi lồng nhau) hoặc gọi lại chính phương thức đó (recursive – đệ quy).

    Để lưu trữ thông tin về ai gọi – ai được gọi và chuyển đổi giữa chúng, một stack đặc biệt được sử dụng, gọi là call stack. Call stack lưu trữ thông tin về lời gọi phương thức để thực hiện chuyển đổi quyền điều khiển chương trình và kết quả. Tức là chuyển từ phương thức được gọi về phương thức gọi khi kết thúc phương thức được gọi.

    Các ngôn ngữ lập trình cũng thường sử dụng stack để lưu trữ các biến cục bộ của phương thức. Khi bắt đầu phương thức, không gian bộ nhớ cho các biến cục bộ được cấp phát từ một stack. Khi kết thúc phương thức, không gian này sẽ bị hủy. Vì lý do đó, khi kết thúc phương thức chúng ta không thể nào dùng lại các biến cục bộ của phương thức được nữa.

    Như vậy có thế có đến hai loại stack tham gia vào việc thực thi của phương thức hay chương trình con. Một loại chứa thông tin về phương thức, một loại chứa dữ liệu cục bộ của phương thức.

    Quá trình này được thực hiện ngầm (bởi chương trình dịch). Lập trình viên không trực tiếp điều khiển nó. Chính vì vậy bạn không nhìn thấy stack được sử dụng khi code nhưng thực tế nó đứng sau tất cả các công việc này.

    Cài đặt stack trong C# và .NET framework

    Trong C#, stack có thể được cài đặt sử dụng generic List hoặc danh sách liên kết LinkedList. Cả hai cách đều tương đối đơn giản.

    Cài đặt stack sử dụng List

    using System;
    using System.Collections.Generic;
    
    namespace P01_CustomStack
    {
        class Program
        {
            static void Main(string[] args)
            {
                Console.Title = "Custom Stack with List";
    
                var stack = new CustomStack<string>();
                stack.Push("Hello");
                stack.Push("world");
                stack.Push("from");
                stack.Push("C#");
    
                Console.WriteLine($"Stack count: {stack.Count}");
    
                while (!stack.IsEmpty)
                {
                    var word = stack.Pop();
                    Console.Write($"{word} ");
                }
    
                Console.WriteLine($"\r\nStack count: {stack.Count}");
    
                Console.ReadKey();
            }
        }
    
        class CustomStack<T>
        {
            private int _topIndex;
            private readonly List<T> _list;
    
            public CustomStack()
            {
                _list = new List<T>();
                _topIndex = -1;
            }
    
            public int Count => _list.Count;
    
            public bool IsEmpty => _list.Count == 0;
    
            public void Push(T item)
            {
                _list.Add(item);
                _topIndex++;
            }
    
            public T Pop()
            {
                T temp = _list[_topIndex];
                _list.RemoveAt(_topIndex);
                _topIndex--;
                return temp;
            }
    
            public void Clear()
            {
                _list.Clear();
                _topIndex = -1;
            }
    
            public T Peek()
            {
                return _list[_topIndex];
            }
        }
    }
    
    Kết quả chạy chương trình với lớp CustomStack

    Bản cài đặt stack sử dụng List không có bất kỳ kỹ thuật đặc biệt nào.

    Cài đặt stack sử dụng LinkedList

    using System;
    using System.Collections.Generic;
    
    namespace P02_CustomStack
    {
        class Program
        {
            static void Main(string[] args)
            {
                Console.Title = "Custom Stack with LinkedList";
    
                var stack = new CustomStack<string>();
                stack.Push("Hello");
                stack.Push("world");
                stack.Push("from");
                stack.Push("C#");
    
                Console.WriteLine($"Stack count: {stack.Count}");
    
                while (!stack.IsEmpty)
                {
                    var word = stack.Pop();
                    Console.Write($"{word} ");
                }
    
                Console.WriteLine($"\r\nStack count: {stack.Count}");
    
                Console.ReadKey();
            }
        }
    
        class CustomStack<T>
        {
            private readonly LinkedList<T> _list;
    
            public CustomStack() => _list = new LinkedList<T>();
    
            public int Count => _list.Count;
    
            public bool IsEmpty => _list.Count == 0;
    
            public void Push(T item) => _list.AddFirst(item);
    
            public T Pop()
            {
                T temp = _list.First.Value;
                _list.RemoveFirst();
                return temp;
            }
    
            public void Clear() => _list.Clear();
    
            public T Peek() => _list.First.Value;
        }
    }

    Dịch và chạy thử chương trình sẽ cho ra cùng kết quả như phần trên.

    Có thể thấy, sử dụng LinkedList kết để tạo stack còn đơn giản hơn cả sử dụng List.

    Lớp Stack trong C# và .NET framework

    Ở trên chúng ta đã sử dụng List và LinkedList để tự cài đặt stack. Bản thân .NET framework đã cung cấp sẵn cho chúng ta lớp Stack<T> để sử dụng. Hãy cùng thực hiện một ví dụ nhỏ.

    using System;
    using System.Collections.Generic;
    
    namespace P03_Stack
    {
        class Program
        {
            static void Main(string[] args)
            {
                Console.Title = ".NET framework Stack<T>";
    
                var stack = new Stack<string>();
                stack.Push("Hello");
                stack.Push("world");
                stack.Push("from");
                stack.Push("C#");
    
                Console.WriteLine($"Stack count: {stack.Count}");
    
                while (stack.Count > 0)
                {
                    var word = stack.Pop();
                    Console.Write($"{word} ");
                }
    
                Console.WriteLine($"\r\nStack count: {stack.Count}");
    
                Console.ReadKey();
            }
        }
    }

    Chúng ta làm lại ví dụ đã có nhưng sử dụng lớp Stack<T> “chính thống” của .NET framework. Có thể thấy, sử dụng lớp Stack<T> không có gì khác biệt so với các lớp stack do chúng ta tự viết.

    Một số bài toán đơn giản sử dụng Stack

    Đổi cơ số

    Đổi cơ số là một bài toán khá đơn giản mà bạn đã được học nguyên tắc ở bậc phổ thông. Ở đây chúng ta không nhắc lại nữa mà trực tiếp viết code. Nếu bạn không nhớ, hãy xem hình ảnh minh họa dưới đây.

    Thuật toán đổi cơ số
    Thuật toán đổi cơ số, ví dụ đổi từ hệ 10 sang hệ 2

    Trong ví dụ này chúng ta sẽ sử dụng stack để lưu trữ kết quả của các bước trung gian. Khi kết thúc quá trình, chúng ta lần lượt pop các phần tử của stack này ra và ghép lại thành chuỗi.

    using System;
    using System.Collections.Generic;
    using System.Text;
    
    namespace P04_BaseConversion
    {
        class Program
        {
            static void Main(string[] args)
            {
                Console.Title = "Base Converter";
    
                while (true)
                {
                    Console.Clear();
                    Console.Write("Number: ");
                    var n = int.Parse(Console.ReadLine());
                    Console.Write("Base: ");
                    var b = int.Parse(Console.ReadLine());
                    var bin = Convert(n, b);
                    Console.WriteLine($"{n} (10 base) => {bin} ({b} base)");
    
                    Console.ReadKey();
                }
            }
    
            static string Convert(int number, int @base)
            {
                var digits = new Stack<string>();
                do
                {
                    var d = number % @base;
                    if (d >= 10 && d <= 15 && @base == 16)
                    {
                        var hex = string.Empty;
                        switch (d)
                        {
                            case 10: hex = "A"; break;
                            case 11: hex = "B"; break;
                            case 12: hex = "C"; break;
                            case 13: hex = "D"; break;
                            case 14: hex = "E"; break;
                            case 15: hex = "F"; break;
                        }
                        digits.Push(hex);
                    }
                    else
                        digits.Push(d.ToString());
                    number /= @base;
                } while (number != 0);
                var sb = new StringBuilder();
                while (digits.Count > 0)
                    sb.Append(digits.Pop());
                return sb.ToString();
            }
        }
    }
    Chương trình đổi cơ số dùng Stack
    Chương trình đổi cơ số dùng Stack

    Tính toán chuỗi biểu thức

    Ở phần giới thiệu về ứng dụng của stack chúng ta có nhắc tới ví dụ về phân tích biểu thức (viết ở dạng chuỗi ký tự) và thực hiện tính toán giá trị của biểu thức.

    Hãy cùng nhau thực hiện nào.

    using System;
    using System.Collections.Generic;
    using System.Text;
    
    namespace P05_Calculator
    {
        class Program
        {
            static void Main(string[] args)
            {
                while (true)
                {
                    Console.Clear();
    
                    Console.Write("Expression: ");
                    var expression = Console.ReadLine();
                    Console.WriteLine($"= {Evaluate(expression)}");
    
                    Console.ReadKey();
                }
            }
    
            public static int Evaluate(string expression)
            {
                char[] tokens = expression.ToCharArray();
                // stack chứa toán hạng
                Stack<int> operands = new Stack<int>();
                // stack chứa toán tử
                Stack<char> operators = new Stack<char>();
    
                for (int i = 0; i < tokens.Length; i++)
                {
                    // Bỏ qua các bước còn lại nếu gặp ký tự trắng
                    if (tokens[i] == ' ')
                    {
                        continue;
                    }
    
                    // Nếu gặp ký tự chữ số sẽ quét hết các ký tự chữ số tiếp theo,
                    // chuyển đổi nó về kiểu int và push vào stack cho toán hạng
                    if (tokens[i] >= '0' && tokens[i] <= '9')
                    {
                        StringBuilder digitBuffer = new StringBuilder();
                        // quét các ký tự chữ số tiếp theo  
                        while (i < tokens.Length && tokens[i] >= '0' && tokens[i] <= '9')
                        {
                            digitBuffer.Append(tokens[i++]);
                        }
                        operands.Push(int.Parse(digitBuffer.ToString()));
                    }
    
                    // Nếu gặp dấu mở ngoặc thì push vào stack toán tử
                    else if (tokens[i] == '(')
                    {
                        operators.Push(tokens[i]);
                    }
                    // Nếu gặp dấu đóng ngoặc thì phải giải quyết mớ ở trong ngoặc                
                    else if (tokens[i] == ')')
                    {
                        while (operators.Peek() != '(')
                        {
                            operands.Push(Calculate(operators.Pop(), operands.Pop(), operands.Pop()));
                        }
                        operators.Pop();
                    }
    
                    // Nếu gặp ký tự toán tử (+,-,*,/)
                    else if (tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*' || tokens[i] == '/')
                    {
                        while (operators.Count > 0 && HasPrecedence(tokens[i], operators.Peek()))
                        {
                            operands.Push(Calculate(operators.Pop(), operands.Pop(), operands.Pop()));
                        }
    
                        // Push toán tử vào stack dành cho nó
                        operators.Push(tokens[i]);
                    }
                }
                // Đã kết thúc giai đoạn phân tích chuỗi
    
                // Bắt đầu thực hiện phép toán
                while (operators.Count > 0)
                {
                    operands.Push(Calculate(operators.Pop(), operands.Pop(), operands.Pop()));
                }
    
                return operands.Pop();
            }
    
            // So sánh độ ưu tiên của các phép toán
            public static bool HasPrecedence(char op1, char op2)
            {
                if (op2 == '(' || op2 == ')')
                {
                    return false;
                }
                if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
                {
                    return false;
                }
                else
                {
                    return true;
                }
            }
    
            // Thực hiện các phép toán cơ bản
            public static int Calculate(char @operator, int b, int a)
            {
                switch (@operator)
                {
                    case '+':
                        return a + b;
                    case '-':
                        return a - b;
                    case '*':
                        return a * b;
                    case '/':
                        if (b == 0)
                        {
                            throw new NotSupportedException("Cannot divide by zero");
                        }
                        return a / b;
                }
                return 0;
            }
        }
    }

    Đây là một chương trình nhỏ cho phép bạn nhập vào một biểu thức ở dạng chuỗi. Chương trình sẽ phân tích chuỗi và thực hiện tính giá trị của biểu thức. Chuỗi biểu thức nhập vào theo đúng thói quen sử dụng của chúng ta, có thể chứa đủ 4 phép toán số học và dấu ngoặc đơn.

    Chương trình phân tích và tính giá trị biểu thức sử dụng Stack

    Có một hạn chế nhỏ trong ví dụ này là giữa các toán hạng và toán tử phải có 1 dấu cách để phân tách chúng, chỉ chấp nhận các toán hạng là số nguyên, kết quả trả về cũng là số nguyên. Đương nhiên, bạn có thể tự cải tiến để loại bỏ những hạn chế trên.

    Kết luận

    Bài học này đã điểm qua những vấn đề cơ bản nhất về ngăn xếp và cách thức cài đặt stack trên C#, cũng như cách thức sử dụng lớp Stack<T> do .NET framework cung cấp.

    Cũng lưu ý rằng, nếu có nhu cầu sử dụng cấu trúc dữ liệu này, hãy sử dụng bản cài đặt sẵn của .NET. Không nên sáng tạo lại cái đã có (và còn tốt hơn nữa).

    Trong bài học tiếp theo chúng ta sẽ tiếp tục với hàng đợi.

    Bình luận

    avatar
      Đăng ký theo dõi  
    Thông báo về