Ngăn xếp (Stack) trong ngôn ngữ lập trình C/C++

Ngăn xếp (Stack) là một danh sách mà các phép toán thêm vào hoặc loại bỏ chỉ được thực hiện ở cùng một đầu của danh sách. Đầu này gọi là đỉnh của ngăn xếp. Như vậy phần tử thêm vào đầu tiên sẽ được lấy ra cuối cùng. Vậy thì làm thế nào để biễu diễn ngăn xếp bằng danh sách liên kết, các phép toán thao tác trên ngăn xếp và ngăn xếp có những ứng dụng gì? Cùng Isinhvien tìm hiểu qua bài viết dưới đây nhé!

Biểu diễn ngăn xếp bằng danh sách liên kết

Xét ngăn xếp các sinh viên gồm họ tên, chiều cao, cân nặng tiêu chuẩn.

Ta dùng danh sách liên kết để chứa các phần tử trong ngăn xếp. Một phần tử trong danh sách liên kết chứa một phần tử trong ngăn xếp theo thứ tự là phần tử đầu tiên trong danh sách liên kết chứa phần tử ở đỉnh của ngăn xếp

typedef char infor1[15];
typedef float infor2;
typedef int infor3;
struct element
{ 
   infor1 ht;
   infor2 cc;
   infor3 cntc;
   element *next;
};
typedef element *Stack;
Stack S;

Trong đó:

• Stack là kiểu con trỏ chỉ đến 1 phần tử trong danh sách
• Biến con trỏ S chỉ đến phần tử đầu tiên trong danh sách

Các phép toán trên ngăn xếp được biểu diễn bằng danh sách liên kết

Dưới đây là các phép toán thường hay dùng trên ngăn xếp được biểu diễn bằng danh sách liên kết. (Ở đây Isinhvien viết bằng ngôn ngữ C nhé!)

1. Khởi tạo ngăn xếp

Khi mới khởi tạo, ngăn xếp là rỗng ta cho S nhận giá trị NULL.

void Create(Stack &S)
{ 
   S=NULL;
}

2. Liệt kê các phần tử trong ngăn xếp

Liệt kê lần lượt các phần tử trong ngăn xếp

void Display(Stack S)
{ 
   Stack p;
   p=S;
   while (p != NULL)
   { 
      printf("\n %15s %7.2f %7d", (p).ht , (p).cc , (p).cntc); 
      p=(p).next;
   }
}

3. Thêm một phần tử vào ngăn xếp

Thêm một phần tử có họ tên x, chiều cao y và cân nặng z vào đầu ngăn xếp.

void InsertStack(Stack &S, infor1 x, infor2 y, infor3 z)
{ 
   Stack p;
   p=new element;
   strcpy((p).ht,x); (p).cc=y; (p).cntc=z; (p).next=S;
   S=p;
}

4. Xóa một phần tử trong ngăn xếp

Xóa phần tử đầu tiên khỏi ngăn xếp

void DeleteStack(Stack &S)
{ 
   Stack p;
   if (S!=NULL)
   { 
     p=S;
     S=(*p).next;
     delete p;
   }
}

Ứng dụng của ngăn xếp

Ngăn xếp có rất nhiều ứng dụng trong thực tế, ví dụ như các ứng dụng sau:

• Đảo ngược xâu. Ta sẽ nhập xâu vào stack, sau đó lấy lần lượt các phần tử của stack ra tại đỉnh của nó. Và do đó ta có xâu đã đảo ngược.
• Đổi một số n từ hệ cơ số thập phân sang hệ nhị phân. Ta sẽ lấy số dư n%2 lưu vào stack, và gán n=n/2. Đến khi nào n=1 thì cũng lưu vào stack. Ta lại lấy lần lượt các phần tử của stack -> xâu biểu diễn nhị phân của n.
• Thao tác trên stack tổng quát cùng với các thao tác duyệt stack , tìm kiếm trên stack có rất nhiều ứng dụng.
• ….. Và còn rất nhiều ứng dụng khác nữa

Qua bài viết này, Isinhvien hi vọng các bạn sẽ hiểu rõ hơn về ngăn xếp trong ngôn ngữ C/C++. Nếu thấy bài viết hay, bổ ích thì hãy chia sẻ nó đến với mọi người và đừng quên theo dõi Isinhvien để có thêm nhiều kiến thức bổ ích mỗi ngày. Chúc các bạn nhiều sức khỏe và thành công trong cuộc sống!