+ cấu trúc dữ liệu :

1-định nghĩa :

• Một stack là một cấu trúc dữ liệu mà việc thêm vào và loại bỏ được thực hiện tại một đầu (gọi là đỉnh - top của stack).

• Là một dạng vào sau ra trước - LIFO (Last In First Out)

2-biểu diễn dữ liệu

a .BiÓu diÔn b»ng mảng

Lưu trữ Stack bằng một vectơ có n phần tử kế

tiếp. Phân tử có giá trị là Item, đỉnh của Stack

được lưu trữ bởi biến Top.

b .BiÓu diÔn b»ng danh s¸ch mãc nèi

Trong cách biểu diễn này mỗi phần tử của Stack sẽ có hai phần, một để lưu trữ giá trị của phần tử, một để lưu trữ địa chỉ của phần tử tiếp theo. Ta sử dụng một con trỏ để chỉ đến đầu danh sách.

3-các phép toán :

A khởi tạo

b.Kiểm tra stack đầy

cThêm 1 phần tử

d.Loại bỏ một phần tử

e.Kiểm tra stack rỗng

- tư tưởng :

• Các toán h¹ng được đọc vào trước và đẩy vào stack

• Khi đọc vào toán tử, lấy hai toán hạng ra từ stack, tính toán với toán tử này, rồi đẩy kết quả vào stack

• LÆp ®Õn khi kÕt thóc biÓu thøc ,gi¸ trÞ cña biÓu thøc lµ phÇn tö cuèi cïng trong stack

- thủ tục :

- độ phức tạp thuật toán :

Th1: chi có một phép tính:

nhập c1, c2 và toán hạng-> đẩy vào stack 3 phần tử

T(n)=3;

Th 2: giả sử có k phần tử: trong đó có n toán hạng => phải có n-1 toán tử-> nhập k=2*n-1 phần tử

T(n)=O(2*n-1).

Ta thực hiện n-1 phép tính-> t(n)=O(n-1).=> T(n)=O(max(n-1,2*n-1))=O(2*n-1).

Vậy: T(n)=O(2*n-1)