b923 - stack 堆疊的模板題

🔗 前往 ZeroJudge 原題

題目描述

題目要求實作一個基本的堆疊 (stack) 資料結構，並根據輸入的指令執行以下操作：刪除堆疊頂端元素、輸出堆疊頂端元素、以及將整數加入堆疊。

解題思路

這題主要考驗對堆疊資料結構的理解和使用。程式碼使用 C++ 的 std::stack 容器來實現堆疊。程式首先讀取一個整數 n，然後迴圈 n 次，每次讀取一個指令。如果指令是 3，則讀取一個整數並將其推入堆疊；如果指令是 2，則輸出堆疊頂端的元素；如果指令是 1，則從堆疊中彈出一個元素。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入的指令數量。因為每個指令的操作（push, pop, top）在堆疊上都是常數時間，而迴圈執行 n 次。
• 空間複雜度: O(n)，在最壞的情況下，所有輸入的數字都推入堆疊，因此堆疊的大小可能達到 n。

程式碼

#include <stdio.h>
#include <stack>
int main() {
    int a=0;
    std::stack<int> st;
	scanf("%d",&a);
    while(scanf("%d",&a)>0) {
    	if(a==3){
    		scanf("%d",&a);
    		st.push(a);
		}
		else if(a==2)
    		printf("%d\n",st.top());
        else
        	st.pop();
    }
}