Stack c++ là gì

Bài viết sẽ trình bày về 2 cấu trúc dữ liệu khá cơ bản nhưng cực kì quan trong lập trình là Stack và Queue, về cách cài đặt cũng như ứng dụng của 2 cấu trúc dữ liệu này trên thực tế.

Stack và Queue là gì?

Stack [ngăn xếp] là một cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO [Last In First Out], vào sau ra trước. Để dễ hình dung thì nó giống với hình ảnh 1 chông sách, tuy nhiên chồng sách này phải tuân theo một quy tắc đó là khi thêm một cuốn sách mới vào chồng thì phải thêm vào phía trên chồng sách và khi lấy sách ra cũng phải lấy từ phía trên.

[link ảnh: VisuAlgo - Linked List [Single, Doubly], Stack, Queue, Deque]

Tương tự như Stack, Queue [hàng đợi] cũng là một cấu trúc dữ liệu. Về hình ảnh của Queue thì chính tên gọi đã giúp ta tưởng tượng ra nó. Chúng ta có thể hình dung đó là hình ảnh một hàng người đang xếp hàng để mua pizza, và dĩ nhiên tính chất của hàng người này đó là ai đến trước thì được mua trước[dĩ nhiên sẽ có trường hợp có người được ưu tiên mua trước, tuy nhiên chúng ta sẽ nói đến trường hợp này ở một bài viết khác về hàng đợi ưu tiên].

 

[link ảnh: Hundreds of students queue up to get free Domino's pizza | Daily Mail Online]

Chính vì vậy Queue hoạt động theo nguyên tắc FIFO [First In First Out], vào trước ra trước.

[link ảnh: //en.wikipedia.org/wiki/Network_scheduler]

Cài đặt:

Để sử dụng Stack và Queue, chúng ta có thể sử dụng các thư viện hỗ trợ có sẵn của C++[#include với Stack và #include với Queue]. Tuy nhiên chúng ta hoàn toàn có thể xây dựng được 2 cấu trúc dữ liệu này với các cấu trúc dữ liệu đơn giản đã biết như mảng [Array] hay danh sách liên kết đơn [Singly Linked List]. Trong bài viết này mình sẽ trình bày cách xây dựng Stack và Queue sử dụng danh sách liên kết đơn [để hiểu hơn về danh sách liên kết đơn, bạn có thể đọc ở một blog mà mình đã từng chia sẻ: Bạn Hiểu Gì Về Danh Sách Liên Kết Đơn Trong C++ [codelearn.io]]. Ở đây để đơn giản thì mình sẽ sử dụng kiểu dữ liệu số nguyên [int] cho dữ liệu của Stack và Queue.

struct Node{ int data; Node* next; };

Stack:

• Push[]: Thêm 1 phần tử vào Stack. Hàm này tương tự với hàm thêm 1 phần tử vào đầu danh sách liên kết đơn, dĩ nhiên các bạn cũng có thể xây dựng giống với hàm thêm phần tử vào cuối danh sách liên kết đơn. Tuy nhiên, khi xây dựng như vậy thì hàm Pop[], tương ứng với hàm Push[] ấy cũng phải là hàm xóa phần tử ở cuối danh sách, và việc này yêu cầu chi phí là O[n], trong khi hàm xóa 1 phần tử ở đầu danh sách[ứng với hàm xây dựng bên dưới] chỉ là O[1].

node *top = NULL; // dùng biến top để kiểm soát Stack void Push[int data] { Node* temp; temp = new Node; //Trường hợp không cấp phát được bộ nhớ cho temp if [!temp] { cout data = data; temp->link = top; top = temp; }

• Pop[]: Xóa 1 phần tử trong Stack. Tương tự với hàm xóa 1 phần tử ở đầu danh sách liên kết đơn.

void Pop[] { Node* temp; //Kiểm tra trường hợp Stack rỗng if [top == NULL] { cout link = NULL; delete temp; } }

• isEmpty[]: Kiểm tra Stack có rỗng hay không.

int isEmpty[] { return top == NULL; }

• Peek[]: Trả ra giá trị của phần tử ở đỉnh Stack.

int Peek[] { if [!isEmpty[]] return top->data; else exit[1]; }

Queue:

• enQueue[]: Thêm 1 phần tử vào Queue, tương tự với hàm thêm 1 phần tử vào cuối danh sách liên kết đơn. Còn lí do mình chọn thêm vào cuối chứ không phải vào đầu thì lí do tương tự với lí do mình đã nói ở hàm Push[] của phần Stack ở trên.

Node* front = NULL, rear = NULL;// dùng 2 biến front và rear để kiểm soát queue. void enQueue[int x] { Node* temp; temp = new Node; //Trường hợp không cấp phát được bộ nhớ cho temp if [!temp] { cout data = x; temp->next = NULL; //Trường hợp Queue đang rỗng. if [rear == NULL] { front = rear = temp; return; } //Thêm phần tử vào Queue, cập nhập lại rear rear->next = temp; rear = temp; }

• deQueue[]: Xóa 1 phần tử trong Queue, tương tự với hàm xóa 1 phần tử ở đầu danh sách liên kết đơn.

void deQueue[] { //Trường hợp Queue rỗng. if [front == NULL] return; Node* temp = front; front = front->next; //Trường hợp ban đầu Queue chỉ có 1 phần tử if [front == NULL] rear = NULL; delete temp; }

Ứng dụng:

Stack:

Queue:

• Thuật toán Breadth First Search
• Bộ đệm, chứa các yêu cầu cần xử lí theo thứ tự vào trước thì xử lí trước.
• ...

Kết luận:

Trên đây là những chia sẻ của mình về 2 kiểu dữ liệu Stack và Queue. Hi vọng sau bài viết này các bạn sẽ có 1 cái nhìn tổng quan về 2 kiểu dữ liệu trên. Hẹn gặp lại các bạn trong các bài viết tiếp theo!

Stack – Ngăn xếp là cấu trúc dữ liệu quan trọng , là kiến thức không thể thiếu trong khoa học máy tính và được ứng dụng rất nhiều trong lập trình. Nó là kiểu dữ liệu cơ bản để giải những bài toán từ đơn giản đến phức tạp, nhiều bài toán phức tạp đã được đơn giản hóa đi rất nhiều nhờ loại cấu trúc dữ liệu này.

Stack là gì?

Stack là một kiểu cấu trúc dữ liệu và cơ chế của nó là LIFO [Last In First Out] nghĩa là vào sau ra trước, có thể hình dung Stack như một chồng đĩa, chỉ có thể lấy chiếc đĩa ra hoặc thêm một chiếc đĩa khác vào trên đỉnh của nó và chiếc đĩa nằm trên đỉnh đó được gọi là Top.

Các phương thức của Stack

Cài đặt cấu trúc stack

Sử dụng struct để tạo cấu trúc stack.

struct Number { int number; Number *pNextNum; }; Number *top;

Struct tên là Number, trong struct này gồm có một field kiểu int để lưu trữ giá trị của một phần tử và con trỏ kiểu Number để trỏ tới phần tử kế tiếp trên nó trong stack. Con trỏ top kiểu Number dùng để trỏ tới phần tử trên cùng của stack.

isEmpty[]

Phương thức isEmpty[] này giúp kiểm tra stack có rỗng hay không, nếu rỗng sẽ trả về true nếu không rỗng sẽ trả về false.

int isEmpty[] { if [top == NULL] return true; return false; }

Push[]

Phương thức Push[] dùng để thêm một phần tử vào trên cùng của stack.

void pushNum[int value] { Number *ptr = new Number;//tạo mới một phần tử ptr->number = value; //gán giá trị cho phần tử ptr->pNextNum = top; //phần tử này trỏ tới phần tử dưới nó trong stack top = ptr; //đánh dấu phần tử này hiện đang nằm trên đỉnh của stack }

Tạo ra một con trỏ mới kiểu Number và gán giá trị cho phần tử này. Cho phần tử này liên kết đến phần tử nằm ngay dưới nó bằng cách sử dụng field pNextNum trỏ tới phần tử đó. Cuối cùng dùng con trỏ top trỏ tới phần tử vừa được thêm vào stack để có thể lấy phần tử đó ra.

Pop[]

Phương thức Pop[] là lấy một phần tử nằm trên đỉnh của stack.

int popNumber[] { int result = 0; if [isEmpty[]] { return NULL; //nếu stack rỗng thì return về NULL } else { Number *ptr = top; //dùng một con trỏ trỏ tới phần tử đầu tiên của stack result = top->number; //lấy giá trị top = top->pNextNum; //gán con trỏ top cho phần tử ngay dưới nó delete ptr; //delete phần tử vừa được lấy return result; // trả kết quả } }

Nhiệm vụ của phương thức này là lấy một phần tử ở trên đỉnh của stack và trả về giá trị của phần tử đó. Ngay sau khi lấy một phần tử ra thì phải xóa phần tử đó đi để tránh memory leak.

Có thể hình dung stack được xây dựng bằng linked list qua sơ đồ sau:

Ngăn xếp [stack] là một cấu trúc dữ liệu tuyến tính, hoạt động theo cơ chế LIFO [Last In First Out], tạm dịch là “vào sau ra trước”. Có nghĩa là phần tử nào được thêm vào sau trong stack thì sẽ được lấy ra trước.

Có thể hình dung ngăn xếp như hình ảnh một chồng đĩa. Các đĩa được chồng lên nhau, đĩa nào được đặt vào chồng sau cùng sẽ nằm trên tất cả các đĩa khác và sẽ được lấy ra đầu tiên.

Có thể xem ngăn xếp [stack] là một kiểu danh sách có 2 phép toán đặc trưng là:

• • Bổ sung một phần tử vào cuối danh sách
  • Loại bỏ một phần tử cũng ở cuối danh sách

Vị trí cuối danh sách được gọi là đỉnh [top] của stack.

Một stack thông thường có các thao tác như:

• empty[]: kiểm tra stack có rỗng không.
• size[]: cho biết số phần tử trong stack, còn gọi là kích thước của stack.
• top[]: lấy phần tử được thêm vào cuối cùng trong stack.
• push[]: thêm một phần tử vào stack.
• pop[]: lấy một phần tử ra khỏi stack.

Trong lập trình, có 2 cách thường dùng để xây dựng stack là sử dụng mảng [array] và danh sách liên kết [linked list].

Khi xây dựng stack bằng mảng thì chúng ta lưu ý một số vấn đề sau:

• • Thêm một phần tử vào stack có nghĩa là thêm một phần tử vào cuối mảng.
  • Loại bỏ một phần tử khỏi stack có nghĩa là loại bỏ một phần tử ở cuối mảng.
  • Stack bị tràn khi bổ sung phần tử vào mảng đã đầy. Vì mảng có số lượng phần tử cố định, phải được xác định lúc khai báo.
  • Stack là rỗng khi số phần tử thực sự đang chứa trong mảng bằng 0.

Cài đặt các hàm push[], pop[], empty[], size[], top[] cho stack với C++

#include using namespace std; #define max 10000 int Stack[max]; int Top; //init Stack with Top = -1 void StackInit[]{ Top = -1; } void push[int V]{ if[Top > max-1]{ cout