백준 10828, 18258번 _ Stack과 Queue C++로 구현하기.

Stack 스택 구현 문제: https://www.acmicpc.net/problem/10828

10828번: 스택

Queue 큐 구현 문제: https://www.acmicpc.net/problem/10828

10828번: 스택

이번 포스팅에는 별도로, 문제의 사진을 첨부하진 않겠다.
사실 스택과 큐를 클래스와 함수를 이용하여 C++로 구현하는 것은 처음에 대학에서 프로그래밍을 배울 때 자료구조를 직접 만들어볼 때 제일 처음 해보는 매우 기초적인 부분이다. 요즘은 파이썬에서는 리스트 자체에, C++에서도 STL로 그 기능들을 직접 만들지 않아도 이미 완성되어 있는 걸 쓰면 되는 건 사실이지만, 처음 자료구조를 접하는 입장에서는 직접 만들어보면서 그 작동원리를 이해하는 것이 매우 중요하다. 후에 그러한 STL의 메모리 관리나 시간복잡도에 대한 이해가 필요할테니...

두 문제가 공통적으로 요구하는 것은 간단하다.
Stack과 Queue의 기본 기능들을 구현하는 것이다

Stack
- push X: 정수 X를 스택에 넣는 연산이다.
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 스택에 들어있는 정수의 개수를 출력한다.
- empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
- top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

Queue
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

클래스 개념을 활용하여 구현하였으며, 바로 코드를 보면 이해갈 것이다!

STACK

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

class Stack{
private:
    const unsigned short stack_size;
    int* arr;
    int arr_size;
public:
    Stack(): arr_size(0), stack_size(10001) {arr = new int[stack_size];}
    
    void push(int n){
        arr_size += 1;
        if (stack_size == arr_size) cout << "STACK IS FULL" << endl;
        else arr[arr_size-1] = n;
    }
    
    void pop(){
        if (arr_size == 0) cout << -1 << endl;
        else {
            cout << arr[arr_size-1] << endl;
            arr_size-=1;
        }
    }
    
    void top() {
        if (arr_size == 0) cout << -1 << endl;
        else cout << arr[arr_size-1] << endl;
    }
    
    void size() {cout << arr_size << endl;}
    
    void empty() {
        if (arr_size == 0) cout << 1 << endl;
        else cout << 0 << endl;
    }
    
    ~Stack() {delete []arr;}
};

int main(){
    Stack stack;
    int num;
    cin >> num;
    string str;

    for (int i=0; i<num; i++){
        cin >> str;
        if (str == "push") {
            int input;
            cin >> input;
            stack.push(input);
        }
        else if (str == "pop") stack.pop();
        else if (str == "top") stack.top();
        else if (str == "empty") stack.empty();
        else if (str == "size") stack.size();
        else cout << "WRONG INPUT" << endl;
    }
    return 0;
}

 

QUEUE

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

class Queue{
private:
    const int Q_size;
    int* arr;
    int start;
    int arr_size;
public:
    Queue(): arr_size(0), Q_size(2000001), start(0) {arr = new int[Q_size];}
    void push(int n){
        arr_size += 1;
        arr[(start + arr_size-1)] = n;
    }
    void pop(){
        if (arr_size == 0) cout << -1 << "\n";
        else {
            cout << arr[start] << "\n";
            start += 1;
            arr_size -= 1;
        }
    }
    void front() {
        if (arr_size == 0) cout << -1 << "\n";
        else cout << arr[start] << "\n";
    }
    void back() {
        if (arr_size == 0) cout << -1 << "\n";
        else cout << arr[(start + arr_size-1)] << "\n";
    }
    void size() {cout << arr_size << "\n";}
    void empty() {
        if (arr_size == 0) cout << 1 << "\n";
        else cout << 0 << "\n";
    }
    ~Queue() {delete []arr;}
};

int main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Queue Q;
    int num;
    cin >> num;
    string str;

    for (int i=0; i<num; i++){
        cin >> str;
        if (str == "push") {
            int input;
            cin >> input;
            Q.push(input);
        }
        else if (str == "pop") Q.pop();
        else if (str == "front") Q.front();
        else if (str == "back") Q.back();
        else if (str == "empty") Q.empty();
        else Q.size();
    }
    return 0;
}

 

끝!