Cấu trúc dữ liệu - Stack

Hiroshi · March 27, 2019, 3:33pm

I. STACK là gì?

stack (ngăn xếp) là cấu trúc dữ liệu trừu tượng được sử dụng khá phổ biến trong lập trình. Gọi là ngăn xếp vì nó chỉ cho phép thao tác dữ liệu tại vị trí trên cùng của ngăn xếp. Trong thực tế ngăn xếp xuất hiện khá phổ biến. Ví dụ như một chồng đĩa; ta chỉ có thể thêm đĩa mới vào trên cùng của chồng và truy xuất, lấy ra đĩa ở trên cùng. Dữ liệu ở đây cũng vậy.
=> Đặc điểm này khiến cho cấu trúc dữ liệu của stack có dạng LIFO (Last-in First-out): phần tử được thêm vào cuối cùng sẽ được truy cập đầu tiên.

II. Các hoạt động với stack.

Hoạt động push(): Thêm phần tử vào stack.
Hoạt động pop(): Xóa phần tử khỏi stack.

Ngoài các hoạt động cơ bản trên thì còn có các hoạt động phụ khác như:

Hoạt động isEmpty(): kiểm tra xem stack có rỗng không.
Hoạt động isFull(): Kiểm tra xem stack đã đầy chưa.
Hoạt động peek(): lấy ra phần tử cuối cùng trong stack mà không xóa phần tử này.

TẠi mọi thời điểm ta thường duy trì một con trỏ trỏ tới phần tử cuối cùng của ngăn xếp (con trỏ top).

Hoạt động isEmpty():

Ta thường khởi tạo con trỏ top với giá trị ban đầu là -1. Nên ta chỉ cần kiểm tra nếu top < 0 là ngăn xếp trống. Code hàm theo c++:

bool isEmpty()
   {
    if (top == -1) return true;
    else return false;
   }

Hoạt động isFull():

Do ban đầu top=-1 nên ngăn xếp đầy khi top=MAX_SIZE -1. Code mẫu:

bool isFull()
    {
    if(top == MAX-1) return true; 
    else return false;
    }

Hoạt động peek():

Để truy xuất ra phần tử cuối cùng của ngăn xếp ta chỉ cần lấy ra phần tử thứ top của ngăn.(Cần kiểm tra xem trong ngăn còn phần tử không).

Code mẫu:

int peek()
   {
    if(!isEmpty())
    return stack[top];
    else cout << "mang khong co phan tu";
   }

Hoạt động push():

Để có thể thêm được phần tử vào vị trí cuối của ngăn xếp ta cần:

B1: Kiểm tra xem ngăn xếp đã đầy chưa.
B2: Nếu ngăn xếp đã đầy thông báo lỗi và thoát ra khỏi hàm.
B3: Nếu ngăn xếp chưa đầy thì tăng con trỏ top lên 1 để trỏ tới vị trí tiếp theo.
B4: Thêm dữ liệu cho phần tử mà con trỏ top trỏ đến trong ngăn xếp.

Code mẫu c++:

void push(int data)
   {
    if(!isFull())
    {
        top = top + 1;
        stack[top] = data;
    }
    else cout<<"ngan da day!";
   }

Hoạt động pop():

Để xóa phần tử của ngăn xếp ta cần:

B1: Kiểm tra xem ngăn xếp có phần tử hay chưa.
B2: Nếu chưa có phần tử nào thì thông báo lỗi rồi thoát.
B3: Nếu còn phần tử thì giảm con trỏ top xuống 1 đơn vị.

Code mẫu:

void push(int data)
   {
    if(!isFull())
    {
        top = top + 1;
        stack[top] = data;
    }
    else cout<<"ngan da day!";
   }

III. Toàn bộ code:

#include <iostream>
using namespace std;

const int MAX = 10;
int stack[MAX];
int top = -1;

bool isFull()
{
    if(top == MAX-1) return true; 
    else return false;
}
bool isEmpty()
{
    if (top == -1) return true;
    else return false;
}
int peek()
{
    if(!isEmpty())
    return stack[top];
    else cout << "mang khong co phan tu";
}
void push(int data)
{
    if(!isFull())
    {
        top = top + 1;
        stack[top] = data;
    }
    else cout<<"ngan da day!";
}
void pop()
{
    if(!isEmpty()) top--;
    else cout << "mang da het phan tu!";
}
    
int main()
{
    push(5);
    cout << top << endl;
    cout << peek() << endl;
    cout << isEmpty() << endl;
    cout << isFull() << endl;
    pop();
}

IV. Code stack theo hướng đối tượng OOP:

#include <iostream>
using namespace std;

const int MAX = 10;

class Stack
{
	private:
		int top = -1;
	public:
		int stack[MAX];
		bool isFull();
		bool isEmpty();
		int peek();
		int size();
		void push(int data);
		void pop();
};
bool Stack::isEmpty()
{
	if(top == -1) return true;
	return false;
}

bool Stack::isFull()
{
	if(top == MAX -1 ) return true;
	else return false;
}
int Stack::peek(){
	if(!isEmpty())
	return stack[top];
	else{
		cout << "mang khong co phan tu";
		return -1;
	}
}
int Stack::size(){
	return top+1;
}
void Stack::push(int data)
{
	if(!isFull())
	{
		top = top + 1;
		stack[top] = data;
	}
	else cout<<"ngan da day!";
}
void Stack::pop()
{
	if(!isEmpty()) top--;
	else 
		cout << "mang da het phan tu!";
}
int main()
{
}

Trên đây là lí thuyết cơ bản về stack. Có nhiều thiếu xót mong các bạn góp ý; sửa chữa và bổ sung để có thể hoàn thiện kiến thức hơn.
Chân thành cám ơn!!!

 
                                                           Writer 
                                                             KT

vanhieu · March 27, 2019, 3:04am

Cảm ơn chia sẻ bổ ích của bạn!

Nhân topic này, mình cũng xin đóng góp một bài chia sẻ của mình về Ngăn xếp - Stack cài đặt bằng ngôn ngữ C/C++

Ở bài này mình có bổ sung thêm các cách cài đặt khác nhau bao gồm cả cài đặt bằng mảng, cài đặt bằng danh sách liên kết và kèm theo cả hướng dẫn sử dụng Stack trong STL.

Mình rất sẵn lòng nhận góp ý từ mọi người!

Hung_Hung · December 5, 2019, 1:59am

Mình đang gặp một vấn đề khi swap 2 stack,tùy nó ra kết quả nhưng giáo viên vẫn không cho là đúng hoàn toàn
Bạn có thể giúp mình được không ạ
phần khai báo

class MyStack
{
private:
	int TOP = -1;
	int *S;
	int capacity;
public:

phần swap

	{
		int topTemp
		int *sTemp;
		sTemp = new int[100];
		
		topTemp = s1.TOP;
		sTemp = s1.S;
		
		s1.TOP = s2.TOP;
		s1.S = s2.S;
			
		s2.TOP = topTemp;
		s2.S = sTemp;
	}

SITUVN.gcd · December 5, 2019, 5:19am

Còn capacity nữa kìa!