Stack thường được nhắc đến rất nhiều
trong tin học, nhất là trong lập trình. Đây là một trong những cấu trúc
dữ liệu quan trọng mà bạn cần phải học đầu tiên khi mới bước chân vào
thế giới lập trình. Dưới đây là định nghĩa một cách ngắn gọn về Stack.

1. Stack là gì ?

Stack (ngăn xếp) đơn
giản chỉ là một danh sách mà việc thêm và xóa các phần tử chỉ diễn ra ở
một đầu của danh sách. Stack được thiết kế theo nguyên lý Last-In-First-Out (LIFO), nghĩa là vào sau, ra trước. Phần tử nào được thêm vào sau cùng sẽ là phần tử được lấy ra đầu tiên.

Bạn có thể bắt gặp trong cuộc sống rất
nhiều hình ảnh của Stack. Ví dụ điển hình là băng đạn của súng ngắn,
bạn chỉ có thể thêm đạn vào một đầu và cũng chỉ có thể lấy đạn ra ở
chính đầu đó. Muốn lấy một viên đạn ở dưới, bạn phải lấy tất cả các viên
đạn ở trên cùng ra trước. Một hình ảnh khác về Stack là các đồng xu
được xếp chồng lên nhau hay một chồng đĩa CD.









2. Đặc điểm của Stack

Mọi phần tử trong Stack phải cùng kiểu dữ liệu và có thể là bất kỳ kiểu dữ liệu nào, kể cả struct hay object. Một Stack gồm có phần đáy (bottom) và phần đỉnh (top). Phần tử nằm ở đỉnh Stack được gọi là Top Item. Mọi thao tác thêm, xóa phần tử đều diễn ra ở đỉnh Stack.



Như đã nói ở trên, Stack đơn giản chỉ
là một danh sách. Do đó, nó có hầu hết các thao tác như trên danh sách
như thêm, xóa,... tuy nhiên cách cài đặt sẽ khác đi một chút. Các thao
tác cơ bản nhất của Stack là :

Push : chèn một phần tử vào Stack



Pop : lấy một phần tử ra khỏi Stack



Peek : lấy giá trị của phần tử ở đỉnh Stack



IsEmpty : kiểm tra Stack có rỗng hay không

Clear : xóa hết phần tử trong Stack

3. Cài đặt Stack trong C#

Để cài đặt Stack, chúng ta có thể dùng
mảng hoặc danh sách liên kết. Trong phần này chúng ta sẽ lần lượt đi
qua cả 2 cách cài đặt này và phân tích xem phương pháp nào hiệu quả hơn.

Thực ra, C# đã hỗ trợ cho chúng ta lớp Stack nằm trong namespace System.Collections.Generic. Tuy nhiên, để hiểu rõ cơ chế hoạt động của Stack, bạn nên tìm hiểu các phương pháp cài đặt dưới đây.


a. Cài đặt bằng mảng

Ta sẽ dùng một mảng một chiều S để lưu
trữ Stack. Quy ước lấy phần tử đầu tiên S[0] làm đáy Stack, các phần tử
tiếp theo sẽ được thêm vào ở vị trí S[1], S[2],...

Do mảng là cấu trúc có kích thước cố
định nên số phần tử mà Stack có thể lưu cũng cố định. Ta gọi số phần tử
tối đa của Stack là MaxCount. Ngoài ra, ta sẽ dùng 1 con trỏ Top để chỉ ra vị trí của đỉnh Stack và quy ước như sau :

• Top = -1 nếu Stack rỗng
  
• Top = MaxCount-1 nếu Stack đầy
  

Dưới đây là cài đặt minh họa :

[You must be registered and logged in to see this link.]

1. 
   //Lớp Stack cài đặt bằng mảng một chiều
   
2. 
   class ArrayStack
   
3. 
   {
   
4. 
   private int[] elements; //mảng chứa các phần tử của stack
   
5. 
   private int max_count; //số phần tử tối đa của stack
   
6. 
   private int top; //chỉ số của phần tử ở đỉnh stack
   
7. 
   
8. 
   //hàm khởi tạo
   
9. 
   public ArrayStack(int MaxCount)
   
10. 
    {
    
11. 
    max_count = MaxCount;
    
12. 
    elements = new int[max_count];
    
13. 
    top = -1;
    
14. 
    }
    
15. 
    //lấy phần tử ra khỏi stack
    
16. 
    public int Pop()
    
17. 
    {
    
18. 
    if (top == -1) throw new Exception("Stack rỗng");
    
19. 
    return elements[top--];
    
20. 
    }
    
21. 
    //thêm phần tử vào stack
    
22. 
    public void Push(int Value)
    
23. 
    {
    
24. 
    if (top == max_count - 1) throw new Exception("Stack đầy");
    
25. 
    elements[++top] = Value;
    
26. 
    }
    
27. 
    //lấy giá trị của phần tử ở đỉnh stack
    
28. 
    public int Peek()
    
29. 
    {
    
30. 
    if (top == -1) throw new Exception("Stack rỗng");
    
31. 
    return elements[top];
    
32. 
    }
    
33. 
    //xóa hết stack
    
34. 
    public void Clear()
    
35. 
    {
    
36. 
    top = -1;
    
37. 
    }
    
38. 
    //kiểm tra stack có rỗng không
    
39. 
    public bool IsEmpty()
    
40. 
    {
    
41. 
    return (top == -1);
    
42. 
    }
    
43. 
    }
    

b. Cài đặt bằng danh sách liên kết đơn (DSLK đơn)

DSLK đơn là một loại
cấu trúc cực kỳ linh động. Khác với mảng, DSLK đơn được cấp phát động
nên số phần tử của nó là không giới hạn, chỉ phụ thuộc vào giới hạn của
bộ nhớ. Đây là một lợi thế khi cài đặt Stack bằng DSLK. Để hiểu rõ phần
này, bạn phải biết cách cài đặt DSLK. Có thể tham khảo [You must be registered and logged in to see this link.].

Ngược với mảng, ở đây ta quy ước phần tử cuối danh sách (Tail) làm đáy Stack. Các thao tác thêm xóa sẽ diễn ra ở đầu danh sách (Head). Điều này là do DSLK đơn không cho phép truy xuất ngược, mà chỉ có thể truy xuất tuần tự từ phần tử Head tới phần tử Tail.

Ta cũng chỉ cần 2 thao tác chính trên DSLK đơn là : thêm vào đầu (AddHead) và xóa phần tử đầu (RemoveHead) danh sách. Đồng thời bổ sung thêm các thao tác đặc trưng của Stack như Pop, Peek, IsEmpty,...

Dưới đây là cài đặt :

[You must be registered and logged in to see this link.]

1. 
   //Lớp chứa một phần tử của stack
   
2. 
   class Node
   
3. 
   {
   
4. 
   public int Value { get; set; } //giá trị của phần tử
   
5. 
   public Node Next { get; set; } //con trỏ Next trỏ tới phần tử kế tiếp
   
6. 
   
7. 
   //hàm khởi tạo
   
8. 
   public Node(int ivalue)
   
9. 
   {
   
10. 
    Value = ivalue;
    
11. 
    Next = null;
    
12. 
    }
    
13. 
    }
    
14. 
    
15. 
    //Lớp Stack
    
16. 
    class ListStack
    
17. 
    {
    
18. 
    public Node Head { get; set; } //con trỏ Head, trỏ tới phần tử đầu ds
    
19. 
    public Node Tail { get; set; } //con trỏ Tail, trỏ tới phần tử cuối ds
    
20. 
    
21. 
    //hàm khởi tạo
    
22. 
    public ListStack()
    
23. 
    {
    
24. 
    Head = Tail = null;
    
25. 
    }
    
26. 
    //thêm phần tử vào stack
    
27. 
    public void Push(int value)
    
28. 
    {
    
29. 
    Node p = new Node(value); //tạo node mới
    
30. 
    if (p == null) throw new Exception("Không thể thêm vào stack");
    
31. 
    //nếu stack rỗng
    
32. 
    if (Head == null)
    
33. 
    Tail = p;
    
34. 
    else
    
35. 
    p.Next = Head;
    
36. 
    Head = p;
    
37. 
    }
    
38. 
    //lấy phần tử ra khỏi stack
    
39. 
    public int Pop()
    
40. 
    {
    
41. 
    if (Head == null) throw new Exception("Stack rỗng");
    
42. 
    //lấy giá trị và tách phần tử đầu stack ra khỏi danh sách
    
43. 
    Node p = Head;
    
44. 
    Head = p.Next;
    
45. 
    int temp = p.Value;
    
46. 
    //giải phóng bộ nhớ
    
47. 
    p.Next = null;
    
48. 
    GC.Collect();
    
49. 
    //trả về giá trị
    
50. 
    return temp;
    
51. 
    }
    
52. 
    //lấy giá trị phẩn tử ở đỉnh stack
    
53. 
    public int Peek()
    
54. 
    {
    
55. 
    if (Head == null) throw new Exception("Stack rỗng");
    
56. 
    return Head.Value;
    
57. 
    }
    
58. 
    //xóa hết stack
    
59. 
    public void Clear()
    
60. 
    {
    
61. 
    //lấy các phần tử ra khỏi stack đến khi stack rỗng
    
62. 
    while (!IsEmpty()) Pop();
    
63. 
    }
    
64. 
    //kiểm tra stack có rỗng hay không
    
65. 
    public bool IsEmpty()
    
66. 
    {
    
67. 
    return (Head == null);
    
68. 
    }
    
69. 
    }
    

c. Nhận xét

Hai phương pháp cài đặt trên đều có ưu và nhược điểm riêng :

• Cài đặt bằng mảng :
  đơn giản, tuy nhiên với đặc trưng của Stack là mọi thao tác chỉ diễn ra ở
  một đầu nên không phát huy lợi thế về khả năng truy xuất trực tiếp so
  với DSLK đơn. Bên cạnh đó, số lượng phần tử Stack là cố định. Điều này
  gây khó khăn trong một vài trường hợp vì dữ liệu luôn biến động.
  
• Cài đặt bằng DSLK đơn : cài đặt phức tạp hơn mảng một chút (không đáng kể), nhưng mang lại hiệu quả cao. Với cách này, Stack trở nên linh động hơn.
  

4. Một số ứng dụng của Stack

Stack có rất nhiều ứng dụng trong tin học như :

• Khử đệ quy
  
• Chuyển đổi các cơ số (nhị phân, thập phân, bát phân,...)
  
• Chuyển biểu thức trung tố sang hậu tố, tính toán các biểu thức hậu tố,...
  

Ở phần sau, chúng ta sẽ ứng dụng Stack để giải quyết một số bài toán cụ thể, bao gồm cả những ứng dụng được liệt kê trên đây.

Project mẫu : [You must be registered and logged in to see this link.]

Chúc các bạn thành công