[C++] 자료구조 – 스택(Stack) 코드 : Array / LinkedList 를 사용하여 구현

Stack을 구현하는건 쉬웟다. 의외엿던건, 코드를 짜기 전에는 LinkedList 를 사용하여 구현하는게 더 복잡할 줄 알았는데 LinkedList 를 사용하는건 정말 간단했고, 오히려 배열을 사용하여 구현하는게 조금 헷갈렸다.

배열로 구현 할 때 헷갈렸던 부분은 생성자에서 배열을 initialize 할 때, 처음엔 Node* nodes 를 사용하고 생성자에서 new Node[capacity] 로 설정했었는데, 불필요하게 capacity 만큼의 Node를 생성하게 되는 문제가 있었다. C언어에서는 malloc 을 사용하면 됐는데, C++에서는 malloc을 사용 할 수 있는데 사용하는게 비권장되어서 조금 더 생각해보니 포인터 배열을 사용하면 되겠다 싶어서 사용해보니 원하는대로 작동했다. Node** nodes 이렇게 별하나 더 붙여주고 생성자에는 Node*[capacity] 이렇게 사이에 별하나 추가.

그나저나 포인터 개념은 분명히 옛날에 알고리즘 공부하면서 분명히 충분히 이해했는데 오랫동안 안하면 또 헷갈리는것 같다.. 내 머리가 겨우 이 정도인가..
이럴 때 보면 프로그래밍이랑 수학은 은근히 비슷한것 같..ㄷ

링크드 리스트를 사용해서 스택을 구현 할 때는 의외로 쉬워서 간단했다.

책이나 인터넷상 몇몇 코드를 보니 Node 부분에서 ‘next‘ 를 사용했는데 음.. stack 인데 ‘next’ 라는 표현을 쓰는것보다 이전 노드인 ‘prev‘ 를 사용하는게 더 말이 되겠다 싶어서 연결될 노드의 이름을 ‘prevNode‘ 로 했다. 이 변수의 이름을 next 로 하면 코드를 짤 때 머릿속에서 틀이 잘 안그려진다 – 글을 작성하면서 알았는데, 처음엔 그냥 단순히 변수명의 문제인줄 알았으나. 책에 있는 코드랑 인터넷상 코드를 보니까 next 노드를 사용하게 하면서 pop 할 때 while 문 돌려서 끝에 있는 노드를 조회한다.. 도대체 왜 이렇게 짜는거야? 매우 비효율적이다..

아, 그리고 코드작성할때 초보스러운 실수를 저질렀었는데, 클래스를 만들고, 생성자에서 length 의 값을 안정해줬다. 그래서 나중에 테스팅할때보니 length 여러자릿수..
이런 실수를 코딩면접할떄 저지르면 얼마나 쪽팔릴까 허허허. 왜 까먹은거지. 주의하자.

생각해보니 난 학부시절 자료구조를 처음 배울때 어리석게도 stack 과 queue 의 개념이 헷갈렸다. 근데 옆에 있던 미국애가 stack 은 ‘think about a stack of papers’ 이러면서 쌓여있는 종이에 비유했다. 종이를 쌓아놓으면 맨 위 부터 본다고 생각하면 되고, queue 는 줄서는걸 생각하라고 했다. 걔는 그냥 지나가면서 설명해줬겟지만 난 요즘도 stack 과 queue 를 볼 떄 걔가 해준말을 기억한다

배열 기반 Stack

/**
 * @file ArrayStack.cpp
 * @brief Stack implemented using array
 * @author velopert
 * @version 1.0
 * @date 2016-04-13
 */

#include <iostream>

using namespace std;

/*
 * Node Class
 */

class Node {
    public:
        int data;
        Node(int data);
        Node();
        ~Node();
};

Node::Node(int data) {
    this->data = data;
}


Node::~Node() {
    cout << "deleting node (" << this->data << ")" << endl;
}

/*
 * Stack Class
 */

class Stack {
    public:
       int capacity;
       int top;
       Node** nodes;

       Stack(int capacity);
       ~Stack();

       void push(int data);
       int pop();
       bool isEmpty();
       int getSize();
};

Stack::Stack(int capacity){
    this->nodes = new Node*[capacity];
    this->capacity = capacity;
    this->top = 0;
}

Stack::~Stack() {
    for(int i = 0; i < this->capacity; i++) {
        if(this->nodes[i]) {
            delete this->nodes[i];
        }
    }

    delete[] this->nodes;
}

void Stack::push(int data) {
    this->nodes[this->top++] = new Node(data);
    cout << "push: " << data << endl;
}

int Stack::pop() {
    int data = this->nodes[--(this->top)]->data;
    cout << "pop: " << data << endl;
    return data;
}

bool Stack::isEmpty() {
    return (this->top == 0);
}

int Stack::getSize() {
    return this->top - 1;
}
/*
 * testing
 */
int main() {
    Stack stack(30);
    stack.push(1);
    stack.push(2);
    stack.push(3);

    cout << "size: " << stack.getSize() << endl;

    stack.pop();
    stack.pop();

    cout << "empty: " << (stack.isEmpty() ? "true" : "false") << endl;

    stack.pop();

    cout << "empty: " << (stack.isEmpty() ? "true" : "false") << endl;
}

LinkedList 기반 Stack

/**
 * @file LinkedListStack.cpp
 * @brief Stack implemented using LinkedList
 * @author velopert
 * @version 1.0
 * @date 2016-04-13
 */

#include <iostream>

using namespace std;

/*
 * Node
 */
class Node {
    public:
        int data;
        Node* prevNode;

        Node(int data);
        ~Node();
};

Node::Node(int data) {
   this->data = data;
}

Node::~Node() {
    cout << "deleting node (" << this->data << ")" << endl;
}

/*
 * Stack
 */
class Stack {
    public:
        Node* topNode;
        int length;

        Stack();
        ~Stack();

        void push(int data);
        int pop();

        int getLength();
};

Stack::Stack() {
    this->topNode = NULL;
    this->length = 0;
}

Stack::~Stack() {
    Node* top = this->topNode;
    while(top) {
        Node* old = top;
        top = top->prevNode;
        delete old;
    }
}

void Stack::push(int data){
    if(this->topNode == NULL) {
        this->topNode = new Node(data);
    } else {
        Node* old = this->topNode;
        this->topNode = new Node(data);
        this->topNode->prevNode = old;
    }
    length++;

    cout << "push: " << data << endl;
}

int Stack::pop() {
    int data = this->topNode->data;
    delete this->topNode;
    this->topNode = this->topNode->prevNode;

    length--;

    cout << "pop: " << data << endl;
    return data;
}

int Stack::getLength() {
    return length;
}
/*
 * testing
 */
int main() {
    Stack stack;

    stack.push(1);
    stack.push(2);
    stack.push(3);

    cout << "length: " << stack.getLength() << endl;

    stack.pop();
    stack.pop();
    stack.push(4);
    stack.pop();

    cout << "length: " << stack.getLength() << endl;

    stack.pop();

    cout << "length: " << stack.getLength() << endl;

    stack.push(10);
    stack.push(11);
    stack.push(12);

}