Tạo bài viết
Đăng ký
01/10/2018, 22:41

Lập trình C: Bài 15 – Cài đặt ngăn xếp (Stack)

Lập trình C: Bài 15 – Cài đặt ngăn xếp (Stack) Tháng Một 20, 2018 nguyenvanquan7826 TUT Cấu trúc dữ liệu 43 responses 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à ...

Lập trình C: Bài 15 – Cài đặt ngăn xếp (Stack)

Tháng Một 20, 2018 nguyenvanquan7826 TUT Cấu trúc dữ liệu 43 responses

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

stack

Trong bài này chúng ta tìm hiểu cách cài đặt Stack trên mảng và trên con trỏ

1. Stack cài đặt 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 danh sách rỗng, kiểm tra danh sách 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 phần tử 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 dữ 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 dữ 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 toàn bộ chương trình (full)

#include <stdlib.h>
#include <stdio.h>

#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<n; i++)
	{
		printf("Nhap phan tu thu %d : ", i+1);
		scanf("%d",&x);
		Push(S,x);
	}
}

void Output(Stack S)
{
	for (int i=S.Top-1; i>=0; i--)
		printf("%d   ",S.Data[i]);
	printf("
");
}

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

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("
1: Kiem tra Stack rong");
    printf("
2: Kiem tra Stack day");
    printf("
3: Them phan tu vao Stack");
    printf("
4: Xoa phan tu trong Stack");
    printf("
5: Xuat Stack");
    printf("
6: Thoat");
    do
    {
        printf("
Ban 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ự phòng

2. Stack cài đặt trên con trỏ

Stack trên con trỏ vẫn là stack bình thường nhưng link hoạt hơn vì nó dùng con trỏ để cấp phát và quản lý, 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 danh sách rỗng, kiểm tra danh sách rỗng, độ dài danh sách

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 phần tử 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

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 dữ 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 dữ 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 chỉnh (full code)

#include <stdlib.h>
#include <stdio.h>

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("
");
}

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

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("
1: Kiem tra Stack rong");
    printf("
2: Do dai Stack");
    printf("
3: Them phan tu vao Stack");
    printf("
4: Xoa phan tu trong Stack");
    printf("
5: Xuat Stack");
    printf("
6: Thoat");
    do
    {
        printf("
Ban 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ự phòng

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

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

#include <iostream> // io
#include <stack> // use stack

using namespace std;

int main() {
	stack <int> 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() << "
";
	
	// 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 << "
";
	
	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

#include <iostream> // io
#include <stack> // 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 <char> 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”]

Trần Trung Dũng

15 chủ đề

2610 bài viết

Có thể bạn quan tâm
0
Các chủ đề đang được quan tâm
phần mềm lập trình php | lập trình web php + mysql | khóa học lập trình php | tự học lập trình php | học php cơ bản thachpham | Code24h | Cho thuê phòng trọ hà nội | Cho thuê phòng trọ bình thạnh | Cho thuê phòng trọ | Cho thuê nhà trọ
Đăng ký

Đăng ký nhận thông báo

Các bài học thú vị sẽ được gửi đến inbox của bạn

HỖ TRỢ HỌC VIÊN
VỀ CODE24H
HỢP TÁC VÀ LIÊN KẾT
KẾT NỐI VỚI CHÚNG TÔI
TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI

CCode 24h, code mọi lúc, mọi nơi

© Copy right 2018 - 2024