e447 - queue 練習

🔗 前往 ZeroJudge 原題

題目描述

題目要求實作一個佇列 (queue) 並處理一系列的操作。操作包括將元素加入佇列尾端、輸出佇列前端的元素，以及刪除佇列前端的元素。如果嘗試從空佇列中獲取或刪除元素，則需要處理相應的邊界情況。

解題思路

本題的核心是使用佇列資料結構來模擬題目描述的操作。使用 C++ 的 std::queue 容器來儲存整數元素。程式首先讀取操作次數 N，然後迴圈 N 次，每次讀取操作類型 k。

• 如果 k 等於 1，則讀取一個整數 x 並將其加入佇列尾端。
• 如果 k 等於 2，則檢查佇列是否為空。如果佇列不為空，則輸出佇列前端的元素；否則，輸出 -1。
• 如果 k 等於 3，則檢查佇列是否為空。如果佇列不為空，則刪除佇列前端的元素；否則，忽略該操作。

複雜度分析

• 時間複雜度: O(N)，其中 N 是操作次數。因為每個操作（push, front, pop）在佇列上的時間複雜度都是 O(1)，而迴圈執行 N 次。
• 空間複雜度: O(N)，在最壞的情況下，佇列可能儲存 N 個元素。

程式碼

#include <stdio.h>
#include <queue>
int main() {
    int a=0;
    std::queue<int> st;
	scanf("%d",&a);
    while(scanf("%d",&a)>0) {
    	if(a==1){
    		scanf("%d",&a);
    		st.push(a);
		}
		else if(a==2){
			if(st.empty()==1)
				printf("-1\n");
			else
    			printf("%d\n",st.front());
    	}
        else{
        	if(st.empty()!=1)
				st.pop();
		}
    }
}