 Bài tập 2: Kiểm tra một xâu kí tự có chứa các dấu ngoặc tương xứng không?

 Thuật toán:

 Sử dụng Stack lưu trữ các dấu ngoặc.

 Duyệt xâu lần lượt qua các dấu ngoặc như sau:

• Nếu gặp '(' thì nạp '(' vào Stack.

• Nếu gặp ')' thì xóa một phần tử ra khỏi Stack.

 Nếu Stack rỗng trước khi duyệt xong xâu hoặc duyệt xong mà Stack vẫn còn phần tử thì xâu đã cho không thỏa mãn, ngược lại thỏa mãn.

Function KiemTraDauNgoacTuongXung

(str: string): boolean;

Var

S: Stack;

n, d: integer;

KiemTra: boolean;

x: char;

Begin

n := length(str);

d := 1;

KiemTra := true;

StackInit(S);

while (d

begin

if str[d] = '(' then PushS(str[d], S)

else

if not EmptyS(S) then PopS(S, x)

else KiemTra := false;

inc(d);

end;

if EmptyS(S) and KiemTra then

KiemTraDauNgoacTuongXung := true

else

KiemTraDauNgoacTuongXung := false;

end;

 Bài tập 3: Dùng các phép toán của hàng đợi và ngăn xếp, viết thuật toán đảo ngược các phần tử của hàng đợi.

 Thuật toán:

 Lấy từng phần tử của Queue nạp vào Stack.

 Hiển thị các phần tử trong Stack.

Procedure DoiNguoc(Q: Queue);

var S: Stack;

x: ElementType;

begin

StackInit(S);

while not EmptyQ(Q) do

begin

PopQ(Q, x);

PushS(S, x);

end;

writeln('Hien thi Q theo thu tu dao nguoc: ');

while not EmptyS(S) do

begin

PopS(S, x);

writeln(x, ' ');

end;

end;

 Bài tập 4: Đọc các kí tự của xâu kí tự vào Stack và Queue. Dùng các phép toán của Stack và Queue kiểm tra xem xâu đó có đối xứng không?

 Thuật toán:

 Đọc các kí tự vào Stack và Queue.

 Duyệt Stack và Queue:

• Lấy phần tử ra khỏi Stack và Queue.

• Nếu hai phần tử vừa lấy ra không bằng nhau thì xâu không đối xứng, thoát.

 Khi duyệt xong nếu không có vấn đề gì thì xâu đã cho đối xứng.

Function DoiXung(xau: string): boolean;

var S: Stack;

Q: Queue;

ch1, ch2: char;

l, i: integer;

begin

StackInit(S);

QueueInit(Q);

l := length(xau);

for I := 1 to l do

begin

PushS(xau[i], S);

PushQ(xau[i], Q);

end;

while not EmptyS(S) do

begin

PopS(S, ch1);

PopQ(Q, ch2);

if (ch1 ch2) then

begin

DoiXung := false;

exit; {Thoat khoi chuong trinh con}

end;

end;

DoiXung := true;

end;

Bài 1: Sử dụng các phép toán căn bản trên Stack: Empty, StackInit, Push, Pop để lập giải thuật:

a) Lấy ra một phần tử ở đáy ngăn xếp nhưng để lại nguyên nội dung còn lại của ngăn xếp.

b) Lấy ra phần tử thứ n (đếm từ trên xuống) của ngăn xếp, nhưng để lại nguyên nội dung còn lại của ngăn xếp.

b) Gợi ý thuật toán bài 1:

a) Để giải bài toán này, trước hết chúng ta khởi tạo 1 ngăn xếp tạm.

b) Để lấy ra phần tử ở đáy mà vẫn bảo toàn các phần tử còn lại, chúng ta dùng ngăn xếp tạm để lưu tạm thời các phần tử nằm trên.

Rồi đẩy chúng vào ngăn xếp ban đầu sau khi đã lấy phần tử ở đáy ngăn xếp ban đầu ra

Procedure Bai1A;

1. StackInit(tam); {khởi tạo một ngăn xếp tạm}

2. {đẩy các phần tử vào ngăn xếp tạm}

while not Empty(S) do begin

Pop(i,S); {Lấy phần tử ở đỉnh của S}

Push(i,Tam); {Đẩy và ngăn xếp tạm}

end;

3.{đẩy phần tử ở đỉnh stack tạm (hay chính là phần tử đáy của stack S) ra khỏi stack}

Pop(i,Tam); write(i:1);

4.{đẩy lần lượt các phần tử từ stack Tạm về lại stack S}

while not Empty(Tam) do

begin

Pop(i, Tam);

Push(i, S);

end;

5.return

Procedure Bai1B;

1. readln(n);{nhập vào một số nguyên dương n}

2. StackInit(tam);

3. Count := 1;

4. {đẩy (n-1) phần tử ra khỏi stack S}

while (not Empty(S) and (count

Pop(i,S);

Push(i,tam);

inc(count);

end;

5. {lấy phần tử thứ n ra khỏi stack S}

Pop(i,S);write(i);

6. {đẩy trả lại các phần tử từ stack Tạm về stack S}

while not Empty(Tam) do begin

Pop(i,Tam};

Push(i,S);

end;

7. return

Bài 2: Sử dụng các phép toán căn bản trên QUEUE: Empty, Create, EnQueue, DeQueue để lập giải thuật:

a) Lấy ra một phần tử ở cuối hàng đợi, nhưng để lại nguyên nội dung còn lại của hàng đợi.

b) Lấy ra phần tử thứ n của hàng đợi, nhưng để lại nguyên nội dung còn lại của hàng đợi.

b) Gợi ý thuật toán bài 1:

a) Để giải bài toán này, trước hết chúng ta khởi tạo 1 ngăn xếp tạm.

b) Để lấy ra phần tử ở đáy mà vẫn bảo toàn các phần tử còn lại, chúng ta dùng ngăn xếp tạm để lưu tạm thời các phần tử nằm trên.

c) Rồi đẩy chúng vào ngăn xếp ban đầu sau khi đã lấy phần tử ở đáy ngăn xếp ban đầu ra.

Bài 2:

Tương tự như lời giải của bài tập 1 cùng với các thao tác trên hàng đợi và sử dụng thêm hàng đợi tạm. Bạn đọc tự tìm hiểu và cài đặt thuật toán.

Bài 1. Viết chương trình nhập vào một xâu kí tự và in ra xâu ngược lại bằng stack.

Bài 2. Cho 6 kí tự sau: (, ), {, }, [, ]. Viết chương trình nhập vào 3 trong 6 kí tự trên rồi in ra các kí tự đối xứng của nó.