Skip to main content

Cài đặt stack trong C#

Stack hay còn gọi là ngăn xếp, là một cấu trúc dữ liệu trừu tượng hoạt động theo nguyên lý "vào sau ra trước" (Last In First Out (LIFO).

Kiểu dữ liệu trừu tượng ngăn xếp

Một ngăn xếp là một cấu trúc dữ liệu dạng thùng chứa (container) của các phần tử (thường gọi là các nút (node)) và có hai phép toán cơ bản : push and pop. Push bổ sung một phần tử vào đỉnh (top) của ngăn xếp, nghĩa là sau các phần tử đã có trong ngăn xếp. Pop giải phóng và trả về phần tử đang đứng ở đỉnh của ngăn xếp. Trong stack, các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi stack.

Cài đặt

Ở đây mình sẽ cài đặt Stack bằng cách sử dụng mảng vòng. Mặc dù trong C# có hỗ trợ kiểu dữ liệu Stack<T> nhưng vì việc sử dụng mảng vòng có lợi riêng, nên tùy thuộc vào bài toán cụ thể, bạn có thể sử dụng linh hoạt stack theo ý riêng của bạn.

Khai báo Interface

Bạn định nghĩa 2 phương thức cơ bản nhất là Push() và Pop().
    interface IStack<T>
    {
        void Push(T elem);
        T Pop();
    }

Thực thi phương thức

    public class Stack<T>: IStack<T>
    {
        private int _max, _top;
        private T[] _stack;
        public int Count { get; private set; }

        public Stack(int n = 0)
        {
            Init(n);
        }

        public void Init(int n)
        {
            _max = n;
            _stack = new T[_max];
            Count = _top = 0;
        }

        public void Push(T elem)
        {
            _stack[_top] = elem;
            if (Count < _max) Count++;
            _top = (_top + 1) % _max;            
        }

        public T Pop()
        {
            if (Count == 0) throw new NullReferenceException("Empty List");
            if (_top == 0) _top = _max - 1;
            else
                --_top;
            var elem = _stack[_top];
            Count--;
            return elem;            
        }
    }
Ví dụ: Bạn cài đặt stack lưu trữ các phần tử kiểu int
        static void Main(string[] args)
        {
            var stack = new DataStructuresAndAlgorithms.Stack<int>(100);
            stack.Push(1);
            stack.Push(2);
            stack.Push(3);
            stack.Push(5);
            stack.Push(8);
            stack.Push(13);
            while (true)
            {
                Console.WriteLine(stack.Pop());
                if (stack.Count == 0) break;
            }
            Console.ReadKey();
        }
Lưu ý: Bạn ghi rõ <tên namespace>.<tên class>, vì stack được định nghĩa sẵn trong lớp System.Collection. (lớp này được add vào khi bạn thêm file class mới)
Output:
13
8
5
3
2
1
Bạn có thể phát triển cài đặt thêm các hàm như hàm Peek-lấy phần tử ở đầu stack nhưng không gỡ nó ra khỏi stack, Clear()-xóa hết mọi phần tử trong Stack...

Comments

Popular posts from this blog

Lập trình đa luồng với Task

Bài viết được đăng trên Jou Lập trình
Trong phiên bản .NET framework 4.0, Microsoft đã bổ sung nhiều thư viện hỗ trợ việc xử lý đa luồng (multi-threading), nhằm đơn giản hóa việc lập trình lẫn hiệu suất của chương trình. Trong bài viết này, tôi xin hướng dẫn các bạn sử dụng lớp System.Threading.Task.

Tìm hiểu về IdentityServer 4

Trong bài viết này, mình sẽ hướng dẫn các bạn làm quen với thư viện Identity Server 4, và tích hợp các service In-Memory của Identity Server 4 vào Project Web API trong .NET Core.

[ASP.NET MVC] Authentication và Authorize

Một trong những vấn đề bảo mật cơ bản nhất là đảm bảo những người dùng hợp lệ truy cập vào hệ thống. ASP.NET đưa ra 2 khái niệm: Authentication và Authorize
Authentication xác nhận bạn là ai. Ví dụ: Bạn có thể đăng nhập vào hệ thống bằng username và password hoặc bằng ssh.
Authorization xác nhận những gì bạn có thể làm. Ví dụ: Bạn được phép truy cập vào website, đăng thông tin lên diễn đàn nhưng bạn không được phép truy cập vào trang mod và admin.