[伯俊/C+]10828号スタック

10828題リンク

質問する

整数を格納するスタックを実装し、入力としてのコマンドを処理するプログラムを作成します.
命令は全部で5種類ある.

push X:整数Xをスタックに入れる演算.

pop:スタックの一番上の整数を抜き、その数字を出力します.スタックに整数がない場合は、-1が出力されます.

size:スタック内の整数の個数を出力します.

empty:スタックが空の場合、1または0を出力します.

top:出力スタックの一番上の整数.スタックに整数がない場合は、-1が出力されます.

入力

1行目に与えられるコマンド数N(1≦N≦10000).2行目からN行目までそれぞれ1つのコマンドがあります.与えられた整数は1以上であり、100000以下である.問題にない命令はない.

しゅつりょく

出力するコマンドが発行されるたびに、各行に1つのコマンドが出力されます.

に答える

スタックは全部で3つの方法で解くことができる.
第一に、STLを使用する
第二に、タイルを使う
第三に、接続リストの使用
詳細については、👉 [アルゴリズム]StackとQueueここの位置付けを参照してください.

ソースコード

第一に、STLを使用する

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    
    stack<int> s;
    
    int n; 					// 명령의 수 
    cin >> n;
    
    string command;		    // 명령어 
    int x;					// 스택에 넣을 수 
    
    for(int i=0;i<n;i++) {
        cin >> command;
        if (command == "push") {
	        // 정수 X 를 스택에 넣음 
            cin >> x;
            s.push(x);
        } else if (command == "size") {
	        // 스택에 들어있는 정수의 개수를 출력 
            cout << s.size() << endl;
        } else if (command == "empty") {
	        // 스택이 비어있는지 확인 
            cout << s.empty() << endl;
        } else if (s.empty()) {
            // pop, top 인 경우 스택이 비어 있으면 -1 을 출력해야 함 
            cout << "-1" << endl;
        } else if (command == "pop") {
	        // top 에 있는 값을 출력해주고 pop 해줌 
            cout << s.top() << endl;
            s.pop();
        }  else if (command == "top") {
	        // top 에 있는 값 출력 
            cout << s.top() << endl;
        }
    }
    
    return 0;
}

第二に、タイルを使う

#include <iostream>
#include <string>
using namespace std;

struct stack {
    
    int top = 0;
    int a[10000];
    
    void push(int x) {
        a[top++] = x;
    }
    
    int size() {
        return top;
    }
    
    int empty() {
        return top == 0;
    }
    
    int t() {
        return a[top-1];
    }
    
    int pop() {
        return a[top--];
    }

};

int main() {
    
    stack s;
    
    int n; 					// 명령의 수 
    cin >> n;
    
    string command;		    // 명령어 
    int x;					// 스택에 넣을 수 
    
    for(int i=0;i<n;i++) {
        cin >> command;
        if (command == "push") {
	        // 정수 X 를 스택에 넣음 
            cin >> x;
            s.push(x);
        } else if (command == "size") {
	        // 스택에 들어있는 정수의 개수를 출력 
            cout << s.size() << endl;
        } else if (command == "empty") {
	        // 스택이 비어있는지 확인 
            cout << s.empty() << endl;
        } else if (s.empty()) {
            // pop, top 인 경우 스택이 비어 있으면 -1 을 출력해야 함 
            cout << "-1" << endl;
        } else if (command == "pop") {
	        // top 에 있는 값을 출력해주고 pop 해줌 
            cout << s.t() << endl;
            s.pop();
        }  else if (command == "top") {
	        // top 에 있는 값 출력 
            cout << s.t() << endl;
        }
    }
    
    return 0;
}

第三に、接続リストの使用

#include <iostream>
#include <string>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* top;
int count;

void push(int x) {
    Node* n = new Node();
    n -> data = x;
    n -> next = top;
    top = n;
    count ++;
}

int size() {
    return count;
}

int empty() {
    return top == NULL;
}

int t() {
    return top -> data;
}

void pop() {
    count--;
    top = top -> next;
}

int main() {
    
    int n; 					// 명령의 수 
    cin >> n;
    
    string command;		    // 명령어 
    int x;					// 스택에 넣을 수 
    
    for(int i=0;i<n;i++) {
        cin >> command;
        if (command == "push") {
	        // 정수 X 를 스택에 넣음 
            cin >> x;
            push(x);
        } else if (command == "size") {
	        // 스택에 들어있는 정수의 개수를 출력 
            cout << size() << endl;
        } else if (command == "empty") {
	        // 스택이 비어있는지 확인 
            cout << empty() << endl;
        } else if (empty()) {
            // pop, top 인 경우 스택이 비어 있으면 -1 을 출력해야 함 
            cout << "-1" << endl;
        } else if (command == "pop") {
	        // top 에 있는 값을 출력해주고 pop 해줌 
            cout << t() << endl;
            pop();
        }  else if (command == "top") {
	        // top 에 있는 값 출력 
            cout << t() << endl;
        }
    }
    
    return 0;
}

正解