Bài tập ctdlgt-bt05

Chú ý:
Khi làm các bài tập sau, cần tải (up) mã nguồn lên Bitbucket repository vào (project) ctdlgt-bt05.
Bài 2a cần demo vào buổi thực hành tuần sau.

Bài 1

Lấy mã nguồn chương trình và dữ liệu về các cài đặt (implementation) khác nhau của hai cấu trúc Stack và Queue tại link mã nguồn môn học. Chạy lại chương trình với dữ liệu test.
Chú ý: Thư viện algs4.jar

Bài 2

a) Tự cài đặt lại cấu trúc dữ liệu Stack các số nguyên bằng cách sử linked list.
b) Tự cài đặt lại cấu trúc dữ liệu Queue các String (chuỗi) bằng cách sử dụng array.
(Sinh viên có thể tham khảo mã nguồn mẫu, nhưng sau đó cần có khả năng hoàn toàn tự mình xây dựng được Stack và Queue).

Bài 3 - Reverse polish notation calculator

Bạn cần viết một hàm tính giá trị biểu thức viết ở dạng biểu thức Ba Lan ngược (Reverse Polish notation).
Ví dụ, biểu thức 5 1 2 + 4 * + 3 - (tương đương 5 + ((1 + 2) * 4) - 3 ở dạng bình thường) có giá trị 14.
Để đơn giản, bạn có thể giả thiết rằng luôn có kí tự trắng nằm giữa các số và các phép toán, ví dụ biểu thức 1 3 + hợp lệ, nhưng 1 3+ không hợp lệ.
Biểu thức rỗng có giá trị 0.
Các phép toán hợp lệ là +, -, *, /.
Bạn có thể giả thiết rằng dữ liệu vào luôn luôn hợp lệ.
Chạy test tại đây (bạn cần account tại codewars.com).

Bài 4 - Double Cola

Sheldon, Leonard, Penny, Rajesh và Howard xếp hàng mua một lon "Double Cola" ở máy bán hàng tự động; ngoài họ ra không còn ai khác đang xếp hàng. Người đứng đầu hàng (Sheldon) mua một lon, uống cạn nó, và biến thành hai người! Hai chàng Sheldon này đi xuống cuối hàng xếp hàng tiếp. Người tiếp theo (Leonard) mua một lon, uống cạn, rồi biến thành hai, hai Leonard lại quay xuống cuối hàng, cứ tiếp tục như vậy.
Ví dụ, sau khi Penny uống lon cola thứ ba, hàng đợi sẽ như sau:

Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard, Penny, Penny

Hãy viết một chương trình trả về tên của người uống lon cola thứ n.
Chú ý rằng khởi đầu, hàng đợi có trạng thái như sau:

Sheldon, Leonard, Penny, Rajesh, Howard

Input
Dữ liệu vào gồm một mảng chứa 5 cái tên, và một số nguyên n, với (1 ≤ n ≤ 1000000000).
Thứ tự các tên trong mảng đầu vào chính là thứ tự trong hàng đợi ban đầu.
Output
Trả về một xâu kí tự nằm trên 1 dòng - tên của người uống lon thứ n. Biết rằng các lon cola được đánh số từ 1.
Chạy test tại đây (bạn cần account tại codewars.com).