Bài 15: Stack trong C

Ngăn xếp (Stack) là một danh sách có thứ tự mà phép chèn và xóa được thực hiện tại đầu cuối của danh sách và người ta gọi đầu cuối này là đỉnh (top) của stack

Bạn đang đọc: Bài 15: Stack trong C

stack

Trong bài này tất cả chúng ta tìm hiểu và khám phá cách thiết lập Stack trên mảng và trên con trỏ

Tóm Tắt

1. Stack setup trên mảng

#define Max 100 //so phan tu toi da cua Stack
typedef int item; //kieu du lieu cua Stack
struct Stack
{
	int Top; //Dinh Top
	item Data[Max]; //Mang cac phan tu
};

1.1 Khởi tạo list rỗng, kiểm tra list rỗng, đầy

void Init (Stack &S) //khoi tao Stack rong
{
	S.Top = 0; //Stack rong khi Top la 0
}

int Isempty(Stack S) //kiem tra Stack rong
{
	return (S.Top == 0);
}

int Isfull(Stack S) //kiem tra Stack day
{
	return (S.Top == Max); //
}

1.2 Thêm thành phần vào Stack ( Push )

Để chèn thêm phần tử vào Stack ta chèn vào vị trí Top, và tang Top lên 1 đơn vị
push

void Push(Stack &S, item x) //them phan tu vao Stack
{
	if (!Isfull(S))
	{
		S.Data[S.Top] = x; //Gan du lieu
		S.Top ++; //Tang Top len 1
	}
}

1.3 Lấy tài liệu tại Top nhưng không xóa ( Peak )

int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
	return S.Data[S.Top-1]; //Lay du lieu tai Top
}

1.4 Xóa và lấy tài liệu tại Top ( Pop )

pop

int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
	if (!Isempty(S))
	{
		S.Top --; //Giam Top
		return S.Data[S.Top]; //Lay du lieu tai Top
	}
}

1.5 Code hàng loạt chương trình ( full )

#include 
#include 

#define Max 100 //so phan tu toi da cua Stack
typedef int item; //kieu du lieu cua Stack
struct Stack
{
	int Top; //Dinh Top
	item Data[Max]; //Mang cac phan tu
};

void Init (Stack &S); //khoi tao Stack rong
int Isempty(Stack S); //kiem tra Stack rong
int Isfull(Stack S); //kiem tra Stack day
void Push(Stack &S, item x); //them phan tu vao Stack
int Peak(Stack S); //Lay phan tu o dau Stack nhung khong xoa
int Pop(Stack &S); //Loai bo phan tu khoi Stack
void Input (Stack &S); //Nhap Stack
void Output(Stack S); //Xuat Stack

void Init (Stack &S) //khoi tao Stack rong
{
	S.Top = 0; //Stack rong khi Top la 0
}

int Isempty(Stack S) //kiem tra Stack rong
{
	return (S.Top == 0);
}

int Isfull(Stack S) //kiem tra Stack day
{
	return (S.Top == Max); //
}

void Push(Stack &S, item x) //them phan tu vao Stack
{
	if (!Isfull(S))
	{
		S.Data[S.Top] = x; //Gan du lieu
		S.Top ++; //Tang Top len 1
	}
}

int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
	return S.Data[S.Top-1]; //Lay du lieu tai Top
}

int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
	if (!Isempty(S))
	{
		S.Top --; //Giam Top
		return S.Data[S.Top]; //Lay du lieu tai Top
	}
}

void Input (Stack &S)
{
	int n;
	item x;
	do
	{
		printf("Nhap so phan tu cua Stack (<%d) :",Max);
		scanf("%d",&n);
	} while (n>Max || n<1);
	for (int i=0; i=0; i--)
		printf("%d   ",S.Data[i]);
	printf("\n");
}

int main()
{
    Stack S;
    Init(S);
    Input(S);
    Output(S);

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("\n1: Kiem tra Stack rong");
    printf("\n2: Kiem tra Stack day");
    printf("\n3: Them phan tu vao Stack");
    printf("\n4: Xoa phan tu trong Stack");
    printf("\n5: Xuat Stack");
    printf("\n6: Thoat");
    do
    {
        printf("\nBan chon: ");
        scanf("%d",&lua_chon);
		switch (lua_chon)
		{
			case 1:
			{
				if (Isempty(S)) printf("Stack rong !");
				else printf ("Stack khong rong !");
				break;
			}
			case 2:
			{
				if (Isfull(S)) printf("Stack day !");
				else printf ("Stack chua day !");
				break;
			}
			case 3:
			{
				item x;
				printf ("Nhap phan tu can chen vao DS: ");
				scanf("%d",&x);
				Push(S,x);
				break;
			}
			case 4:
			{
				Pop(S);
				break;
			}
			case 5: 
			{
				Output(S);
				break;
			}
			case 6: break;
		}
    }while (lua_chon !=6);
    return 0;
}

link dự trữ

2. Stack thiết lập trên con trỏ

Stack trên con trỏ vẫn là stack thông thường nhưng link hoạt hơn vì nó dùng con trỏ để cấp phép và quản trị, không bị thừa hoặc thiếu gì cả .

stack pointer

2.1 Xây dựng cấu trúc

typedef int item; //kieu du lieu
struct Node
{
	item Data; //du lieu
	Node *Next; //link
};
typedef struct Stack
{
	Node *Top;
};

2.2 Khởi tạo list rỗng, kiểm tra list rỗng, độ dài list

void Init (Stack &S) //khoi tao Stack rong
{
	S.Top = NULL;
}

int Isempty(Stack S) //kiem tra Stack rong
{
	return (S.Top == NULL);
}

int Len (Stack S)
{
	Node *P = S.Top;
	int i=0;
	while (P != NULL) //trong khi chua het Stack thi van duyet
	{
		i++;
		P = P->Next;
	}
	return i;
}

2.3 Tạo 1 Node

Node *MakeNode(item x) //tao 1 Node
{
	Node *P = (Node*) malloc(sizeof(Node));
	P->Next = NULL;
	P->Data = x;
	return P;
}

2.4 Chèn thành phần vào Stack ( Push )

Để chèn phần tử vào Stack thì chỉ cần cho con trỏ Note đó trỏ và Top, rồi Top trỏ lại nó là xong

Xem thêm: Cách kiểm tra iPhone được kích hoạt ngày nào siêu dễ ai làm cũng được

push

void Push(Stack &S, item x) //them phan tu vao Stack
{
	Node *P = MakeNode(x);
	P->Next = S.Top;
	S.Top = P;
}

2.5 Lấy tài liệu tại Top nhưng không xóa ( Peak )

int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
	return S.Top->Data;
}

2.6 Xóa và lấy tài liệu tại Top ( Pop )

Ta chỉ cần cho con trỏ Top trỏ đến vị trí thứ 2 thôi .

pop

int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
	if (!Isempty(S))
	{
		item x = S.Top->Data; //luu lai gia tri
		S.Top = S.Top->Next; //Xoa phan tu Top
		return x;
	}
}

2.7 Chương trình hoàn hảo ( full code )

#include 
#include 

typedef int item; //kieu du lieu
struct Node
{
	item Data; //du lieu
	Node *Next; //link
};
typedef struct Stack
{
	Node *Top;
};

void Init (Stack &S); //khoi tao Stack rong
int Isempty(Stack S); //kiem tra Stack rong
int Len (Stack S); //Do dai Stack
void Push(Stack &S, item x); //them phan tu vao Stack
int Peak(Stack S); //Lay phan tu o dau Stack nhung khong xoa
int Pop(Stack &S); //Loai bo phan tu khoi Stack
void Input (Stack &S); //Nhap Stack
void Output(Stack S); //Xuat Stack
Node *MakeNode(item x); //Tao 1 Node

void Init (Stack &S) //khoi tao Stack rong
{
	S.Top = NULL;
}

int Isempty(Stack S) //kiem tra Stack rong
{
	return (S.Top == NULL);
}

int Len (Stack S)
{
	Node *P = S.Top;
	int i=0;
	while (P != NULL) //trong khi chua het Stack thi van duyet
	{
		i++;
		P = P->Next;
	}
	return i;
}

Node *MakeNode(item x) //tao 1 Node
{
	Node *P = (Node*) malloc(sizeof(Node));
	P->Next = NULL;
	P->Data = x;
	return P;
}

void Push(Stack &S, item x) //them phan tu vao Stack
{
	Node *P = MakeNode(x);
	P->Next = S.Top;
	S.Top = P;
}

int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
	return S.Top->Data;
}

int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
	if (!Isempty(S))
	{
		item x = S.Top->Data; //luu lai gia tri
		S.Top = S.Top->Next; //Xoa phan tu Top
		return x;
	}
}

void Input (Stack &S) //nhap danh sach
{
    int i=0; 
    item x;
    do
    {
        i++;
        printf ("Nhap phan tu thu %d : ",i);
        scanf("%d",&x);
        if (x != 0) Push(S,x);
    } while(x != 0); //nhap 0 de ket thuc
}

void Output(Stack S)
{
	Node *P = S.Top;
	while (P != NULL)
	{
		printf("%d   ",P->Data);
		P = P->Next;
	}
	printf("\n");
}

int main()
{
    Stack S;
    Init(S);
    Input(S);
    Output(S);

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("\n1: Kiem tra Stack rong");
    printf("\n2: Do dai Stack");
    printf("\n3: Them phan tu vao Stack");
    printf("\n4: Xoa phan tu trong Stack");
    printf("\n5: Xuat Stack");
    printf("\n6: Thoat");
    do
    {
        printf("\nBan chon: ");
        scanf("%d",&lua_chon);
		switch (lua_chon)
		{
			case 1:
			{
				if (Isempty(S)) printf("Stack rong !");
				else printf ("Stack khong rong !");
				break;
			}
			case 2:
			{
				printf("Do dai Stack: %d",Len(S));
				break;
			}
			case 3:
			{
				item x;
				printf ("Nhap phan tu can chen vao DS: ");
				scanf("%d",&x);
				Push(S,x);
				break;
			}
			case 4:
			{
				Pop(S);
				break;
			}
			case 5: 
			{
				Output(S);
				break;
			}
			case 6: break;
		}
    }while (lua_chon !=6);
    return 0;
}

link dự trữ

3. Sử dụng Stack có sẵn trong C + +

Trong C + + đã xây dựng sẵn những phương pháp ( hàm ) tương quan đến Stack, ta chỉ việc khai báo và sử dụng

#include  // io
#include  // use stack

using namespace std;

int main() {
	stack  S; // khai bao Stack voi kieu du lieu la int
	
	for (int i = 0; i < 10; i++) {
		S.push(i*78 + 26); // chen cac phan tu vao stack
	}
	
	cout << "Do dai stack: " << S.size() << "\n";
	
	// xuat tat ca phan tu trong stack
	while (!S.empty()) { 	// trong khi stack chua trong
		int x = S.top(); 	// lay gia tri top
		S.pop(); 			// loai bo khoi stack
		cout << x << "  ";
	}
	cout << "\n";
	
	return 0;
}

4. VÍ dụ về ứng dụng của Stack

Stack có nhiều ứng dụng, sau đây là 1 ứng dụng trong chuyển đổi cơ số. Code sau sẽ chuyển số cơ số 10 sang cơ số x nhập từ bàn phím

Xem thêm: Hướng dẫn cách mở khóa iPhone bị vô hiệu hóa (iPhone is disabled)

#include  // io
#include  // use stack

using namespace std;

int main() {
	char num[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
	stack  S; // khai bao Stack voi kieu du lieu la int
	
	int coSo, so, du;
	
	cout << "Nhap so can chuyen: ";
	cin >> so;
	
	cout << "Nhap co so can chuyen: ";
	cin >> coSo;
	
	// chuyen doi bang cach dua vao Stack
	while(so) {
		du = so % coSo;
		S.push(num[du]);
		so /= coSo;
	}
	
	// Xuat ra
	while(!S.empty()) {
		cout << S.top();
		S.pop();
	}
	
	return 0;
}

[ rps-include post = ” 2703 ″ shortcodes = ” false ” ]

Bạn hoàn toàn có thể sẽ thích :

Source: https://final-blade.com
Category: Kiến thức Internet

admin

final-blade.com