PHẦN 1 : KHÁI NIỆM VÀ CÁC PHƯƠNG PHÁP CÀI ĐẶT STACK

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.

StackDemo_6StackDemo_5

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.

StackDemo_3

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

StackDemo_1

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

StackDemo_2

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

StackDemo_4

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 :

Code

View source
  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. //hàm khởi tạo
  8. public ArrayStack(int MaxCount)
  9. {
  10.     max_count = MaxCount;
  11.     elements = new int[max_count];
  12.     top = -1;
  13. }
  14. //lấy phần tử ra khỏi stack
  15. public int Pop()
  16. {
  17.     if (top == -1) throw new Exception(“Stack rỗng”);
  18.     return elements[top–];
  19. }
  20. //thêm phần tử vào stack
  21. public void Push(int Value)
  22. {
  23.     if (top == max_count – 1) throw new Exception(“Stack đầy”);
  24.     elements[++top] = Value;
  25. }
  26. //lấy giá trị của phần tử ở đỉnh stack
  27. public int Peek()
  28. {
  29.     if (top == -1) throw new Exception(“Stack rỗng”);
  30.     return elements[top];
  31. }
  32. //xóa hết stack
  33. public void Clear()
  34. {
  35.     top = -1;
  36. }
  37. //kiểm tra stack có rỗng không
  38. public bool IsEmpty()
  39. {
  40.     return (top == -1);
  41. }
  42. }

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 tại đây.

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ư PopPeek,IsEmpty,…

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

Code

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

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 : Download

Phần 2: Ứng dụng stack

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: