i213 - stack 練習

🔗 前往 ZeroJudge 原題

題目描述

題目要求實作一個堆疊 (stack) 的基本操作，包含插入元素、輸出堆疊頂端元素以及刪除堆疊頂端元素。輸入包含多個操作，根據操作碼執行相應的堆疊操作，並在需要時輸出堆疊頂端元素。

解題思路

這題主要考驗對堆疊資料結構的理解和應用。使用一個整數陣列 a 作為堆疊的儲存空間，sz 記錄堆疊的頂端索引。

• 當輸入操作碼為 1 時，讀取一個整數 k 並將其推入堆疊，sz 增加。
• 當輸入操作碼為 2 時，判斷堆疊是否為空。如果非空，則輸出堆疊頂端的元素 a[sz-1]；如果空，則輸出 -1。
• 當輸入操作碼為 3 時，判斷堆疊是否為空。如果非空，則將堆疊頂端元素移除，sz 減小；如果空，則忽略該操作。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入的操作次數。因為每個操作都只需要常數時間。
• 空間複雜度: O(n)，因為最壞情況下，堆疊可能儲存 n 個元素。

程式碼

#include <iostream>
using namespace std;
int a[100005],n,is,sz,k;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> is;
		if(is==1){
			cin >> k;
			a[sz++]=k;
		}
		else if(is==2){
			if(sz){
				cout << a[sz-1] << "\n";
			}
			else{
				cout << "-1\n";
			}
		}
		else{
			if(sz){
				--sz;
			}
		}
	}

}