Cấu trúc dữ liệu ngăn xếp - Stack (Cấu trúc dữ liệu và giải thuật)

Một ngăn xếp là một cấu trúc dữ liệu trừu tượng (Abstract Data Type – được viết tắt là ADT), hầu như được sử dụng phổ biến trong hầu hết mọi ngôn ngữ lập trình. Đặt tên là ngăn xếp bởi vì nó hoạt động giống như một ngăn xếp trong đời sống thực tế, ví dụ như một chồng đĩa hay một cỗ bài, …

Trong đời sống thực tế, ngăn xếp chỉ cho phép những hoạt động ở vị trí trên cùng của ngăn xếp. Ví dụ, chúng ta chỉ có thể đặt hoặc thêm một chiếc đĩa hay một lá bài vào trên cùng của ngăn xếp. Do đó, cấu trúc dữ liệu trừu tượng về ngăn xếp chỉ cho phép thực hiện những thao tác dữ liệu ở vị trí trên cùng. Tại bất cứ thời điểm nào, chúng ta cũng chỉ có thể truy cập vào phần tử trên cùng của ngăn xếp.

Đặc điểm này đã làm cho ngăn xếp trở thành một cấu trúc dữ liệu dạng LIFO. LIFO - là viết tắt của Last-In-First-Out. Ở đây, phần tử được đặt vào (được thêm, được chèn vào) cuối cùng cũng sẽ được truy cập đầu tiên. Trong thuật ngữ ngăn xếp, hoạt động xóa được gọi là hoạt động POP và hoạt động chèn được gọi là hoạt động PUSH.

Biểu diễn cấu trúc dữ liệu ngăn xếp (Stack)

Sau đây là sơ đồ minh họa một ngăn xếp và những hoạt động diễn ra trên ngăn xếp.

Một ngăn xếp có thể được triển khai theo phương thức của Mảng (Array), Cấu trúc (Struct), Danh sách liên kết (Linked List) và Con trỏ (Pointer). Ngăn xếp có khi là ở dạng kích cỡ cố định hoặc có khi có thể thay đổi kích cỡ. Phần dưới chúng ta sẽ triển khai ngăn xếp thông qua việc dùng các mảng với việc triển khai các ngăn xếp cố định.

Các hoạt động cơ bản trên cấu trúc dữ liệu ngăn xếp

Những hoạt động cơ bản trên ngăn xếp có thể liên quan đến việc khởi tạo ngăn xếp, dùng nó và sau đó xóa bỏ nó. Ngoài những hoạt động cơ bản này, một ngăn xếp còn có 2 hoạt động nguyên sơ liên quan đến khái niệm, đó là:

• Hoạt động push (): lưu giữ 1 phần tử từ ngăn xếp.

• Hoạt động pop (): xóa 1 phần tử từ ngăn xếp.

Khi dữ liệu đã được PUSH lên trên ngăn xếp:

Để sử dụng ngăn xếp một cách hiệu quả nhất thì chúng ta cũng cần phải kiểm tra kỹ trạng thái của ngăn xếp. Để phục vụ cho mục đích này, sau đây là một số tính năng hỗ trợ khác của ngăn xếp:

• Hoạt động peek (): lấy phần tử dữ liệu ở trên cùng của ngăn xếp, mà không xóa phần tử này.

• Hoạt động isFull (): Kiểm tra xem ngăn xếp đã đầy hay chưa.

• Hoạt động isEmpty (): kiểm tra xem ngăn xếp còn trống hay không.

Tại các thời điểm khác nhau, chúng ta có thể duy trì một con trỏ tới phần tử dữ liệu vừa được PUSH cuối cùng vào trên ngăn xếp. Vì con trỏ này luôn biểu diễn vị trí trên cùng của ngăn xếp cũng chính vì thế mà nó được đặt tên là top. Con trỏ top cung cấp cho chúng ta giá trị của phần tử trên cùng của ngăn xếp mà không cần phải thực hiện bất kỳ hoạt động xóa bào ở trên (hoạt động pop).

Phần tiếp theo chúng ta sẽ tìm hiểu về những phương thức để hỗ trợ những tính năng của ngăn xếp.

Phương thức peek () của cấu trúc dữ liệu ngăn xếp

Giải thuật của hàm peek ():

Bắt đầu hàm peek
return stack [top]
kết thúc hàm

Sự triển khai của hàm peek () trong ngôn ngữ C:

int peek () {
return stack [top];
}

Phương thức isFull () của cấu trúc dữ liệu ngăn xếp

Giải thuật của hàm isFull ():

Bắt đầu hàm isfull
if top bằng MAXSIZE
return true
else
return false
kết thúc if
kết thúc hàm

Sự triển khai của hàm isFull () trong ngôn ngữ C:

bool isfull () {
if (top == MAXSIZE)
return true; 
else
return false; 
}

Phương thức isEmpty () của cấu trúc dữ liệu ngăn xếp

Giải thuật của hàm isEmpty ():

bắt đầu hàm isempty
if top nhỏ hơn 1
return true
else
return false
kết thúc if
kết thúc hàm

Sự triển khai của hàm isEmpty () trong ngôn ngữ C khác hơn một chút. Chúng ta thực hiện khởi tạo top tại -1, giống như chỉ mục của mảng bắt đầu từ 0. Vì thế chúng ta kiểm tra nếu top là dưới 0 hoặc -1 thì ngăn xếp là trống. Dưới đây là phần code:

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

Hoạt động PUSH trong cấu trúc dữ liệu ngăn xếp

Tiến trình đặt (thêm) một phần tử dữ liệu mới vào trên ngăn xếp còn được biết đến với cái tên Hoạt động PUSH. Hoạt động push bao gồm những bước dưới đây:

• Bước 1: kiểm tra xem ngăn xếp đã được đầy hay chưa.

• Bước 2: nếu ngăn xếp đã được xếp đầy, tiến trình bị lỗi và thoát ra.

• Bước 3: nếu ngăn xếp chưa đầy, tăng top để trỏ đến phần bộ nhớ trống kế tiếp.

• Bước 4: thêm phần tử dữ liệu vào vị trí nơi mà top đang trỏ tới trên ngăn xếp.

• Bước 5: trả về success.

Nếu Danh sách liên kết được dùng để triển khai để ngăn xếp, thì ở bước 3 chúng ta cần phải cấp phát một không gian động.

Giải thuật cho hoạt động PUSH của cấu trúc dữ liệu ngăn xếp

Từ trên, ta có thể suy ra rằng một giải thuật đơn giản cho hoạt động PUSH trong cấu trúc dữ liệu ngăn xếp như sau đây:

bắt đầu hoạt động push: stack, data
if stack là đầy
return null
kết thúc if
top ← top + 1
stack [top] ← data
kết thúc hàm

Sự triển khai của giải thuật này trong ngôn ngữ C là:

void push (int data) {
if (!isFull ()) {
top = top + 1; 
stack [top] = data; 
}else {
printf ("Khong the chen them du lieu vi Stack da day. \n");
}
}

Để tìm hiểu về chương trình C minh họa đầy đủ những hoạt động trên của ngăn xếp, mời bạn click chuột vào chương: .

Hoạt động POP của cấu trúc dữ liệu ngăn xếp

Việc truy cập nội dung phần tử trong khi thực hiện thao tác xóa nó từ ngăn xếp còn được gọi là Hoạt động POP. Trong sự triển khai Mảng của hoạt động pop (), phần tử dữ liệu chưa thực sự bị xóa hết, thay vào đó top sẽ bị giảm về vị trí thấp hơn trong ngăn xếp để đưa con trỏ đến giá trị tiếp theo. Nhưng trong sự triển khai Danh sách liên kết, hoạt động pop () đã thực sự xóa hết phần tử xữ liệu và xóa nó khỏi không gian của bộ nhớ.

Hoạt động POP có thể bao gồm những bước dưới đây:

• Bước 1: kiểm tra xem ngăn xếp là trong trạng thái trống hay không.

• Bước 2: nếu ngăn xếp là trống thì tiến trình bị lỗi và thoát ra.

• Bước 3: nếu ngăn xếp là không trống, truy cập vào phần tử dữ liệu tại top đang trỏ tới.

• Bước 4: giảm giá trị của top đi 1.

• Bước 5: trả về success.

Giải thuật cho hoạt động POP

Từ trên ta có thể suy ra rằng giải thuật cho hoạt động POP trên cấu trúc dữ liệu ngăn xếp như dưới đây:

bắt đầu hàm pop: stack
if stack là trống
return null
kết thúc if
data ← stack [top]
top ← top - 1
return data
kết thúc hàm

Sự triển khai giải thuật trong ngôn ngữ C như dưới đây:

int pop (int data) {
if (!isempty ()) {
data = stack [top];
top = top - 1; 
return data; 
}else {
printf ("Khong the lay du lieu, Stack la trong. \n");
}
}

Để tìm hiểu về chương trình C minh họa đầy đủ những hoạt động trên của ngăn xếp, mời các bạn click chuột vào chương: .

Ứng dụng của ngăn xếp

- Xử lý gọi hàm trong C/C++ - Trong máy tính, dùng để tính giá trị biểu thức, xử lý ngắt - Trong những chương trình biên dịch - Trong trình duyệt web, trình soạn thảo văn bản - Định giá biểu thức + Biểu thức trung tố: toán tử 2 ngôi đứng giữa 2 toán hạng, toán tử 1 ngôi đứng trước toán hạng + Biểu thức hậu tố: toán tử đứng sau toán hạng + Biểu thức tiền tố: toán tử đứng trước toán hạng

VD định giá biểu thức A = b + c * d /e – f Trung tố a* (b-c)/d Hậu tố abc-*d/ Tiền tố /*a-bcd

Duyệt biểu thức hậu tố:

- Gặp toán hạng: đẩy vào stack - Gặp toán tử 1 ngôi: lấy ra 1 toán hạng trong stack, áp dụng toán tử lên toán hạng và đấy kết quả trở lại stack - Gặp toán tử 2 ngôi: lấy 2 toán hạng ở đỉnh stack theo thứ tự, áp dụng toán tử lên 2 toán hạng đó, kết quả lại đẩy vào stack - Kết thúc, đưa ra kết quả là giá trị ở đỉnh stack - Vd định giá biểu thức hậu tố

Chuyển biểu thức dạng trung tố sang hậu tố

- Duyệt lần lượt biểu thức trung tố từ trái qua phải - Gặp toán hạng: viết sang biểu thức kết quả - Gặp toán tử có độ ưu tiên dưới 6 + Nếu stack rỗng hoặc đỉnh stack là toán tử có độ ưu tiên nhỏ hơn hoặc là ' (' đẩy toán tử đang xét vào stack + Ngược lại: lấy các toán tử ở đỉnh stack có độ ưu tiên lớn hơn hoặc bằng toán tử đang xét lần lượt đưa vào biểu thức kết quả và đẩy toán tử đang xét vào stack - Gặp toán tử có độ ưu tiên 6 hoăc ' (' thì đẩy vào stack - Gặp ')' lấy tất cả những toán tử trong stack cho đến khi nào gặp ' (' đầu tiên, đưa sang biểu thức kết quả theo đúng thứ tự và đẩy một kí hiệu ' (' ra khỏi stack - Nếu duyệt hết biểu thức trung tố, lấy nốt các toán tử trong stack đưa sang biểu thức kết quả theo đúng thứ tự