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);
}