CTDL và giải thuật - Nhập, xuất hàng đợi

Nhập vào một số nguyên dương n, tiếp theo nhập n số nguyên lần lượt là các phần tử của queue. Cuối cùng nhập vào một số tự nhiên k.

Một phép biến đổi sẽ dịch chuyển phần tử đầu tiên ra sau phần tử cuối cùng của dãy, hãy trả về dãy sau khi đã biến đổi k lần. In tất cả các phần tử ra màn hình, sau mỗi phần tử có đúng một khoảng trắng.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    4
    1 2 3 4
    1

    2 3 4 1

    Với queue = [1, 2, 3, 4] và k = 1, thì kết quả mong muốn là: "2 3 4 1 ".

     
  • Test mẫu 2:
     
    Input Output

    3
    1 3 2
    2

    2 1 3

    Với queue = [1, 3, 2] và k = 2,
    thì kết quả mong muốn là "2 1 3 ".

Giới thiệu về queue:

Queue(hàng đợi) là một loại container, được thiết kế để hoạt động theo kiểu FIFO (First- in first – out) (vào trước ra trước), tức là một kiểu danh sách mà việc bổ sung được thực hiển ở cuối danh sách và loại bỏ ở đầu danh sách.

Trong queue, có hai vị trí quan trọng là vị trí đầu danh sách (front), nơi phần tử được lấy ra, và vị trí cuối danh sách (back), nơi phần tử cuối cùng được thêm vào.

 

Khai báo (C++)

#include<queue>

Các phương thức (ngôn ngữ C++):

Capacity
size() Trả về số lượng phần tử của queue
empty() Trả về true(1) nếu queue rỗng, ngược lại là false (0)
Element access:  
front() Truy xuất phần tử ở đầu queue (phần tử đầu tiên được thêm vào)
back() Truy xuất phần tử ở cuối queue (phần tử cuối cùng được thêm vào)
Modifier:
push (const x) Thêm phần tử có giá trị x vào cuối queue. Kích thước queue tăng thêm 1.
pop () Loại bỏ phần tử ở đầu queue. Kích thước queue giảm đi 1.

 

Hướng dẫn bài tập.

Bài này có nhiều cách làm, một trong số đó có thể dùng hàng đợi.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>
#include<queue>

using namespace std;

int main(){
    queue<int> q;
    int n, k, temp;
    cin >> n;
    for (int i = 0; i < n; i++){
    	cin >> temp;
    	q.push(temp);
	}
	cin >> k;
    for (int i = 0; i < k; i++){
        int x = q.front();
        q.pop();
        q.push(x);
    }
    while (!q.empty()){
        cout << q.front() << " ";
        q.pop();
    }
    
    return 0;
}