10828) 15. 스택 : 스택

문제

https://www.acmicpc.net/problem/10828

10828번: 스택

 

풀이

   풀고 나서 다른 사람 풀이를 봤더니 대체로 그냥 통짜 배열로 처리해서 허탈했던 문제. 난 왜 Linked List까지 쓰면서 구현했는가..

사실 C코드이기 때문에 구조체를 써서 만들면 되지만 클래스 형태로 짜면 어떻게 만들어야 할까 궁금해서 이렇게 해봤다.

 

   문제에서 요구하는 push X, pop, top, size, empty 명령어에(습관적으로 getchar()를 쓰려다) 편하게 std::string을 쓰기로 했다. 근데 속도 면에서 불리하고 심지어 입력 함수인 cin도 scanf보다 느려서 string 대신 char형 배열을 쓰고, string을 안 쓰니 == 비교도 할 수 없어 strcmp를 급하게 찾아 쓰게 되었다. C++ 처음 배울 땐 printf scanf 머릿속에서 잊어야지 하고 좋아했는데, 공부할수록 어디까지가 C이고 어디서부터 C++인지 혼란스러워진다.

 

   여튼 큐(Queue) 구조에서 pop을 만들 땐 편한 게 head 순서만 만지면 되서인데, 스택(Stack) 구조에서 pop을 구현하려니 pop 부를 때마다 반복문 돌려서 이전 노드(node)를 찾느냐, 그냥 각 노드마다 이전 노드를 기억하게 하느냐가 고민이었다. 이번 경우에는 후자를 택했다.

#include "cstdio"
#include "string.h"

class NODE {
    friend class Stack;				// 이걸 해줘야 Stack 클래스에서 prev, next 접근 가능
private:
    int m_data;
    NODE* prev, *next;
public:
    NODE();
    NODE(int);
};
NODE::NODE() : m_data(0), prev(NULL), next(NULL) {}
NODE::NODE(int data) : m_data(data), prev(NULL), next(NULL) {}

class Stack {
private:
    int count;
    NODE* head, *tail;
public:
    Stack();
    void push(int);
    int pop();
    int size();
    bool empty();
    int top();
};
Stack::Stack() : count(0), head(NULL), tail(NULL) {}
void Stack::push(int data) {
    // 정수 X를 스택에 넣는 연산
    NODE* nNode = new NODE(data);
    if(!empty()) {
        // 스택에 값을 추가할 때
        nNode->prev = tail;
        tail->next = nNode;
        tail = tail->next;
    }
    else {
        // 스택에 처음 넣을 때
        tail = head = nNode;
    }
    
    ++count;
}
int Stack::pop() {
    // 스택에서 가장 위에 있는 정수를 빼고 그 수를 출력
    // 아무것도 없으면 -1 출력
    if(!empty()) {
        int data(tail->m_data);
        if(head->next != NULL) {
            NODE* temp = tail->prev;
            temp->next = NULL;
            delete tail;
            tail = temp;
        }
        else {
            delete head;
            head = NULL;
        }
        
        --count;
        return data;
    }
    
    return -1;
}
int Stack::size() { return count; }
// 스택에 들어있는 정수의 개수 출력
bool Stack::empty() {
    // 스택이 비어있으면 1, 아니면 0 출력
    if(this->head == NULL) return true;
    return false;
}
int Stack::top() {
    // 스택의 가장 위에 있는 정수를 출력, 아무것도 없으면 -1 출력
    if(!empty()) return tail->m_data;
    return -1;
}

int main() {
    int repeat(0), data(0);
    char order[6]{};
    Stack stack;
    
    scanf("%d%*c", &repeat);
    
    for(int i(0); i < repeat; i++) {
        scanf("%s", order);
        if(!strcmp(order, "push")) {
            scanf("%d%*c", &data);
            stack.push(data);
        }
        else if(!strcmp(order, "pop")) printf("%d\n", stack.pop());
        else if(!strcmp(order, "size")) printf("%d\n", stack.size());
        else if(!strcmp(order, "empty")) printf("%d\n", stack.empty());
        else if(!strcmp(order, "top")) printf("%d\n", stack.top());
        else continue;
    }
    
    return 0;
}