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...