khoahoc.vietjack.com
Xin chào! Vào học

Câu hỏi:

12/07/2024 303 Lưu

Lan xếp các đĩa CD thành một cọc (Hình 1). Mỗi lần lấy đĩa ra khỏi cọc, Lan sẽ lấy lần lượt tùng đĩa một từ trên xuống. Mỗi lần bổ sung. Lan cũng lần lượt xếp từng đĩa mới vào cọc. Em hãy: 

a) Cho biết với đĩa nằm ở đáy và đĩa nằm ở đỉnh cọc, đĩa nào được thêm vào cọc trước. 

b) So sánh quy tắc thực hiện thao tác thêm vào và lấy đĩa ra khỏi cọc với thao tác thêm vào và lấy ra phần tử khỏi hàng đợi đã được học ở bài trước.

Quảng cáo

Trả lời:

verified Giải bởi Vietjack

Lan xếp các đĩa CD thành một cọc (Hình 1). Mỗi lần lấy đĩa ra khỏi cọc, Lan sẽ lấy lần lượt tùng đĩa một từ trên xuống. Mỗi lần bổ sung. Lan cũng lần lượt xếp từng đĩa mới vào cọc.

a) Theo nguyên tắc LIFO thì đĩa nào được thêm vào cọc sau cùng thì sẽ được lấy ra đầu tiên. Đĩa nằm ở đáy là  đĩa được thêm vào cọc đầu tiên. Đĩa nằm ở đỉnh cọc là đĩa được thêm vào cọc sau cùng. Như vậy, đĩa nằm ở đáy cọc được thêm vào trước so với đĩa nằm ở đỉnh cọc.

b) So sánh quy tắc thực hiện thao tác thêm vào và lấy đĩa ra khỏi cọc (stack) với thao tác thêm vào và lấy ra phần tử khỏi hàng đợi (queue) như sau:

* Quy tắc hoạt động:

1. Stack (Cọc):

- Thêm vào (Push): Thêm phần tử vào đỉnh của cọc.

- Lấy ra (Pop): Lấy phần tử từ đỉnh của cọc.

- Quy tắc: LIFO (Last In, First Out) - phần tử được thêm vào sau cùng sẽ được lấy ra đầu tiên.

2. Queue (Hàng đợi):

- Thêm vào (Enqueue): Thêm phần tử vào cuối hàng đợi.

- Lấy ra (Dequeue): Lấy phần tử từ đầu hàng đợi.

- Quy tắc: FIFO (First In, First Out) - phần tử được thêm vào đầu tiên sẽ được lấy ra đầu tiên.

* So sánh:

- Thao tác thêm:

+ Stack: Thêm vào đỉnh cọc (mới nhất).

+ Queue: Thêm vào cuối hàng đợi (mới nhất).

- Thao tác lấy ra:

+ Stack: Lấy từ đỉnh cọc (mới nhất).

+ Queue: Lấy từ đầu hàng đợi (cũ nhất).

Đang tải chế độ Học...

Dành cho bạn Hot

Lớp 12 Vật lý
208 người thi tuần này

Trắc nghiệm Mô hình động học phân tử chất khí lớp 12 (có đáp án)

15 câu 1.9 K lượt thi Thi ngay →
Lớp 12 Tiếng Anh
133 người thi tuần này

Đề cương ôn tập giữa kì 1 Tiếng Anh 12 Global Success có đáp án

45 câu 1.3 K lượt thi Thi ngay →
Lớp 12 Sinh học
189 người thi tuần này

10 câu trắc nghiệm Sinh học 12 Kết nối tri thức Bài 8 có đáp án

10 câu 2 K lượt thi Thi ngay →
Lớp 12 Lịch sử
2,190 người thi tuần này

20 câu trắc nghiệm Lịch sử 12 Kết nối tri thức Bài 1 có đáp án

20 câu 22.4 K lượt thi Thi ngay →
Lớp 12 Địa lý
364 người thi tuần này

20 câu Trắc nghiệm Địa lý 12 Kết nối tri thức Bài 2 có đáp án

25 câu 6 K lượt thi Thi ngay →
Lớp 12 Tin học
556 người thi tuần này

15 câu Trắc nghiệm Tin học 12 Bài 1. Làm quen với Trí tuệ nhân tạo (có đáp án)

15 câu 13.2 K lượt thi Thi ngay →
Lớp 12 Giáo dục Kinh tế và Pháp luật
634 người thi tuần này

15 câu Trắc nghiệm KTPL 12 Bài 1 (có đáp án)

15 câu 8.9 K lượt thi Thi ngay →

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

Chương trình yêu cầu người sử dụng nhập năm số nguyên dương - bất kì từ bàn phím, sau đó in ra màn hình năm số này theo thứ tự đảo ngược của thứ tự nhập vào. Trong chương trình có sử dụng kiểu dữ liệu ngăn xếp và các thao tác đã học trên ngăn xếp.

Muốn viết chương trình này ta sẽ sử dụng cấu trúc dữ liệu ngăn xếp (stack) để lưu trữ các số nguyên dương người dùng nhập vào. Ngăn xếp là một cấu trúc dữ liệu hoạt động theo nguyên lý LIFO (Last In, First Out), tức là phần tử được thêm vào cuối cùng sẽ là phần tử được lấy ra đầu tiên.

Sử dụng ngôn ngữ lập trình Python để thực hiện như sau:

class Stack:

   def __init__(self):

        self.items = []

   def push(self, item):

        self.items.append(item)

   def pop(self):

        if not self.is_empty():

            return self.items.pop()

        else:

            return None

   def is_empty(self):

        return len(self.items) == 0

   def size(self):

        return len(self.items)

def main():

   stack = Stack()

   print("Nhập vào năm số nguyên dương:")

   # Yêu cầu người dùng nhập vào 5 số nguyên dương

   for i in range(5):

        while True:

            try:

                num = int(input(f"Nhập số thứ {i+1}: "))

                if num > 0:

                    stack.push(num)

                    break

                else:

                    print("Vui lòng nhập một số nguyên dương.")

            except ValueError:

                print("Đó không phải là một số nguyên. Vui lòng thử lại.")

   # Lấy các số ra khỏi ngăn xếp và in theo thứ tự đảo ngược

   print("Các số theo thứ tự đảo ngược:")

   while not stack.is_empty():

        print(stack.pop(), end=" ")

if __name__ == "__main__":

   main()

Lời giải

Để cài đặt ngăn xếp với hai thao tác thêm vào (push) và lấy ra (pop), ta có thể dùng mảng một chiều. Khi đó, các phần tử trong mảng sẽ là các phần tử đang có trong ngăn xếp. Ngăn xếp S ở Hình 4a có thể được biểu diễn bởi một mảng một chiều mô phỏng như ở Hình 4b. Các phần tử trong mảng theo thứ tự từ đầu đến cuối sẽ tương ứng với các phần tử trong ngăn xếp theo thứ tự từ đáy lên đỉnh.

1. Thêm vào 13: Ngăn xếp SSS và mảng:

Ngăn xếp: [13,11,9,5,1] [13, 11, 9, 5, 1] [13,11,9,5,1]

Mảng:

Chỉ số

0

1

2

3

4

Giá trị

1

5

9

11

13

2. Thêm vào 15: Ngăn xếp SSS và mảng:

Ngăn xếp: [15,13,11,9,5,1] [15, 13, 11, 9, 5, 1] [15,13,11,9,5,1]

Mảng:

Chỉ số

0

1

2

3

4

5

Giá trị

1

5

9

11

13

15

3. Lấy ra 15: Ngăn xếp SSS và mảng:

Ngăn xếp: [13,11,9,5,1] [13, 11, 9, 5, 1] [13,11,9,5,1]

Mảng:

Chỉ số

0

1

2

3

4

Giá trị

1

5

9

11

13

 

Xem trọn bộ đề thi 6 câu hỏi
Xem thêm