DSA-chuong 2 - Bai Tap Stack - Queue [PDF]

Zitiervorschau

Bài tập về Stack, Queue Data structures and Algorithms

1

Bài tập 1. Cài đặt cấu trúc FIFO (Queue) bằng cấu trúc lưu trữ tuần tự 2. Cài đặt danh sách tổng quát bằng CTLT tuần tự (với danh sách tổng quát, việc bổ sung và lấy ra một phần tử có thể thực hiện ở một vị trí bất kỳ trong danh sách) 3. Viết chương trình chuyển đổi 1 số từ cơ số 10 sang cơ số 2 sử dụng cấu trúc Stack. 4. Ứng dụng stack trong tính giá trị biểu thức dạng hậu tố

2

BT3. Đổi cơ số từ thập phân sang nhị phân Procedure CHANGE(N) m = N; // tính số dư và nạp vào Stack S Do R = m mod 2 Push(R,S) m = m div 2 While(m!=0) // hiển thị chữ số nhị phân While (!isEmpty(S)) X=Pop(S) Write (X) End.

void CHANGE(int N, Stack &S) { int m = N; int R; int X; // tính số dư và nạp vào Stack S do { R = m % 2; Push(R,S); m = m / 2; } while(m!=0) // hiển thị chữ số nhị phân while (!isEmpty(S)) X=Pop(S) printf(“%d”, X); } 3

BT 1. Cài đặt Queue (FIFO) bằng CTLT tuần tự • -

Các thao tác trên cấu trúc dữ liệu hàng đợi: Thêm một phần tử vào hàng đợi: enQueue() Xóa một phần tử khỏi hàng đợi: deQueue() Lấy một phần tử ở đầu hàng đợi và không xóa phần tử: peek() Kiểm tra hàng đợi đầy hay không: QueueIsFull() Kiểm tra hàng đợi rỗng hay không: QueueIsEmpty()

• Định nghĩa cấu trúc dữ liệu hàng đợi typedef struct { Type info [MAX]; //MAX là kích thước hàng đợi int F; //chỉ số phần tử đầu int R; // chỉ số phần tử đuôi } Queue;

• Thao tác khởi tạo hàng đợi rỗng void InitializeQ (Queue & Q){ Q.F=0; Q.R=-1; }

• Thao tác kiểm tra hàng đợi rỗng bool IsEmpty (Queue Q){ return (Q.R