Ngăn xếp (stack) là gì? Cách xây dựng ngăn xếp

1. Ngắn xếp (stack) là gì?

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

2. Xây dựng ngăn xếp bằng mảng

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 <iostream>
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<<"Stack is full";
	}else{
		Top++;
		Stack[Top] = V;
	}
}

int pop(){
	if (Top == -1){
		cout<<"Stack is empty";
		return -1;
	}else{
		int res = Stack[Top];
		Top--;
		return res;
	}
}

int empty(){
	if(Top == -1){
		return 0;//stack is empty
	}
	return 1;//stack isnot empty
}

int size(){
	return Top+1;//size of stack
}

//return value at Top
int top(){
	if (Top == -1){
		cout<<"Stack is empty";
		return -1;
	}else{
		int res = Stack[Top];
		return res;
	}
}
int main(){
	//init Stack
	StackInit();
	//push to Stack
	push(5);
	push(21);
	push(10);
	push(99);
	push(101);
	//size of Stack
	cout<<"Size of Stack = "<<size()<<endl;
	//pop from Stack
	cout<<pop()<<endl;
	cout<<pop()<<endl;
	//size of Stack after pop
	cout<<"Size of Stack after pop = "<<size()<<endl;
	system("pause");
}

Kết quả

Size of Stack = 5
101
99
Size of Stack after pop = 3

Nhận xét: Khuyết điểm của việc xây dựng stack bằng mảng (array) là mảng sẽ bị tràn nếu số lượng phần tử trong stack vượt quá số lượng phần tử tối đa trong mảng. Chúng ta sử dụng danh sách liên kết đơn (linked list) để xây dựng stack nhằm khắc phục khuyết điểm này.

3. Xây dựng ngăn xếp bằng danh sách liên kết đơn

Khi cài đặt stack bằng danh sách liên kết đơn, ta bỏ qua việc kiểm tra stack bị tràn. Đồng thời, phần tử đầu tiên trong danh sách liên kết đơn được xem là phần tử cuối cùng được thêm vào stack. Tức là, hàm push() của stack thì xử lý là thêm node vào đầu danh sách liên kết đơn. Còn hàm pop() của stack là hủy phần tử đầu tiên trong danh sách.

#include <iostream>
using namespace std;

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

node *Top;

void StackInit() {
	Top = NULL;
}

void push(int V){
	node *p;
	p = new node;
	p->data = V;
	if(Top != NULL){
		p->next = Top;
		Top = p;
	}else{
		p->next = NULL;
		Top = p;
	}
}
int pop(){
	if(Top == NULL){
		cout<<"Stack is empty";
		return -1;
	}else{
		int res = Top->data;
		node *p = Top->next;
		delete Top;
		Top = p;
		return res;
	}
}

int empty(){
	if(Top == NULL){
		return 0;//stack is empty
	}
	return 1;//stack isnot empty
}

int size(){
	if(Top == NULL){
		return 0;
	}else{
		int sizeStack = 0;
		node *p;
		p = Top;
		while(p!=NULL){
			sizeStack++;
			p = p->next;
		}
		return sizeStack;//size of stack
	}
}

//return value at Top
int top(){
	if (Top == NULL){
		cout<<"Stack is empty";
		return -1;
	}else{
		int res = Top->data;
		return res;
	}
}

int main(){
	//init Stack
	StackInit();
	//push to Stack
	push(5);
	push(21);
	push(10);
	push(99);
	push(101);
	//size of Stack
	cout<<"Size of Stack = "<<size()<<endl;
	//pop from Stack
	cout<<pop()<<endl;
	cout<<pop()<<endl;
	//size of Stack after pop
	cout<<"Size of Stack after pop = "<<size()<<endl;
	system("pause");
}

Kết quả

Size of Stack = 5
101
99
Size of Stack after pop = 3