Cấu Trúc Dữ Liệu Trong Java Bài 2: Ngăn Xếp (Stack) Và Các Thao Tác Cơ Bản Trên Ngăn Xếp

1. Định nghĩa

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.Ngăn xếp hoạt động theo nguyên lý "vào sau ra trước" .

Ngăn xếp có hai phép toán cơ bản: push and pop.Push bổ sung một phần tử vào đỉnh (top) của ngăn xếp, nghĩa là sau các phần tử đã có trong ngăn xếp. Pop giải phóng và trả về phần tử đang đứng ở đỉnh của ngăn xếp. Trong stack, các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi ngăn xếp.

2. Stack cài đặt trên mảng

1 2 3 4 5 6 7

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

2.1 Khởi tạo danh sách rỗng, kiểm tra danh sách rỗng, đầy

01 02 03 04 05 06 07 08 09 10 11 12 13 14

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); // }

2.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ị

1 2 3 4 5 6 7 8

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     } }

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

1 2 3 4

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

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

1 2 3 4 5 6 7 8

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     } }

3. 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ả.

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

01 02 03 04 05 06 07 08 09 10

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

2.2.2 Khởi tạo danh sách rỗng, kiểm tra danh sách rỗng, độ dài danh sách

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21

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.2.3 Tạo 1 Node

1 2 3 4 5 6 7

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

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

1 2 3 4 5 6

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

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

1 2 3 4

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

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

1 2 3 4 5 6 7 8 9

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;     } }