자료구조 2강. 스택(Stack)
[자료구조 강좌]
선입후출! 후입선출!
스택(Stack)
오늘 알아보게될 스택(Stack)이란 자료구조는 선입후출(First In, Last Out: FILO), 후입선출(Last In, First Out: LIFO)의 구조를 가지고 있습니다. 예를 들자면, 어느 개발자의 책상에 빼곡히 쌓여있는 책을 정리하기 위해 가장 위에있는 책부터 꺼내들어 차례대로 정리합니다. 여기서, 먼저 쌓인 책들보다 나중에 쌓인 책들이 먼저 밖으로 나간다고 해서 후입선출의 구조라 말하고, 반대로 나중에 쌓인 책들보다 먼저 쌓인 책들이 늦게 밖으로 나간다고 해서 선입후출의 구조라고 말하는 것입니다. 스택(Stack)도 마치 개발자의 책상에 빼곡히 쌓여있는 책들과 비슷합니다.
1. 스택(Stack) 데이터의 삽입과 제거가 한쪽 끝에서만!
<스택(Stack)의 모습>
위의 이미지는 용량이 꽉 찬 스택의 모습입니다. 마치 책이 들어간 박스를 연상하게 하지 않나요? 위와 같은 구조는 데이터를 빼내려고 한다면 가장 위에있는 데이터부터 빼내어야 안에있는 데이터를 빼낼 수 있겠죠? 스택(Stack)에서는 데이터를 쌓는 것을 삽입(push)라 하고, 빼내는 것을 제거(pop)라 합니다. 여기서 스택의 특징으로는, 한 방향 끝에서만 데이터의 삽입과 제거가 이루어진다는 것입니다. 이제는 스택 내에 데이터를 삽입하거나, 제거하는 기능을 직접 구현해보도록 합시다. 우선, 스택(Stack) 클래스 부터 살펴보도록 합시다.
// 템플릿을 통해 명시된 타입의 스택을 만들도록 함
template <class T>
class Stack {
private:
T* stack; // = 스택의 첫번째 요소를 가리키는 포인터
int top; // = 스택 내에 들어있는 데이터의 수
int maxSize; // = 스택의 용량
public:
Stack(int maxSize) : maxSize(maxSize) { // 멤버 이니셜라이저를 통한 maxSize의 초기화
top = 0; // top을 0으로 초기화 한다.
stack = new T[maxSize]; // 메모리 공간에 T의 크기 * maxSize 만큼의 공간을 할당한다.
}
void push(T data) { stack[top++] = data; } // 현재의 top번째에 데이터를 집어넣고 top 1 증가
T pop() { return stack[--top]; } // top의 값을 1 감소시키고, 해당하는 값의 요소를 반환
bool isEmpty() { return (top == 0); } // 스택이 비어있는지 확인하는 함수
T getTop() { return stack[top-1]; } // 스택의 최상위 데이터를 가져오는 함수
// bool isFull() { return (top == maxSize); }
~Stack() { delete []stack; } // 클래스 내에서 new 연산을 통해 할당한 메모리 공간을 소멸시킴
};
위 코드의 2행을 보시게 되면, 우리가 명시한 타입의 스택을 만들기 위해서 템플릿을 이용했습니다. 스택 클래스를 대충 살펴보면, 의외로 간단하죠? 17행의 내용은 아직까진 사용할 일이 없을것 같아 우선 주석처리를 해두었습니다. 함수명 그대로 스택이 꽉 찼나 차지 않았나를 구별하는 함수입니다. 메인 함수를 보도록 합시다.
int main()
{
// char형 타입의 스택 클래스
Stack<char> stack(5);
// 스택에 a, b, c, d, e 순서대로 올려놓는다
stack.push('a');
stack.push('b');
stack.push('c');
stack.push('d');
stack.push('e');
// 스택의 용량만큼 루프를 돌음
for (int i=0; i<5; i++)
{
// 스택이 비어있으면 루프를 빠져나옴
if (stack.isEmpty()) break;
// 제거되는 데이터를 출력함
cout << "제거되는 데이터: " << stack.pop() << ", ";
// 스택이 비어있지 않을 경우 최상위 데이터를 가져옴
if (!stack.isEmpty()) cout << "현재 최상위 데이터: " << stack.getTop() << endl;
// 최상위 데이터가 존재하지 않을경우 = 스택이 비어있을 경우
else cout << "최상위 데이터가 존재하지 않습니다." << endl;
}
return 0;
}
4행을 먼저 살펴보시면, char형 타입임을 명시하고 Stack 생성자로 5라는 값을 넘겨주었습니다. 즉, 용량 5 만큼의 char형 배열이 만들어졌다고 생각하시면 됩니다. 그런 뒤에, 7~11행에선 a, b, c, d, e를 차례대로 스택에 올려놓습니다. 그 후에 스택의 용량만큼 루프를 돌게 되는데, 루프를 도는중 스택이 비어있으면 루프를 빠져나오도록 코드를 작성했습니다. 만약, 스택이 비어있지 않을 경우에는 최상위 데이터를 제거(pop)하고, 제거된 데이터를 출력하도록 했으며 제거한 후에도 스택이 비어있지 않으면 제거되고 난 뒤의 최상위 데이터는 무엇인지 출력하고, 스택이 비어있으면 최상위 데이터가 존재하지 않는다는 문구를 출력하도록 했습니다.
이번에는 링크드 리스트로 스택을 구현하여 위의 스택 구현과 비교를 해보도록 할까요?
2. 링크드 리스트 스택(Linked List Stack) 링크드 리스트를 기반한 스택!
아까 우리가 방금 구현한 스택은 문제점이 존재합니다. 배열처럼 스택의 용량을 정해두고 데이터를 쌓아야만 합니다. 스택의 용량을 초과할 경우 위에 있는 데이터를 빼내야만 다른 데이터를 삽입할 수가 있습니다. 그런데, 이번에 링크드 리스트로 구현할 스택은 용량에 제한이 없습니다. 어떻게 구현이 될지 대충 짐작이 가시나요?
<링크드 리스트 스택(Linked List Stack)>
이제, 링크드 리스트 스택을 직접 구현해보도록 합시다. 위에서 예로 들었던 스택의 구현과는 달리 이번에는 노드(Node)라는 구조체를 만들어, 클래스 내에 데이터와 위에 위치하는 노드를 가리키는 포인터를 집어넣도록 하겠습니다.
typedef struct node
{
string data; // 데이터 필드
struct node* nextNode; // 위의 노드를 가리키는 포인터 (스택이기 때문에)
} Node;
Node 구조체의 멤버를 잠시 살펴보자면 string형이 보이는데, 단순히 string형 타입의 변수를 선언할 수는 있어도 이 변수를 출력하고자 할때는 에러가 납니다. (string 타입에 따른 연산자 오버로딩이 존재하지 않기 때문) 그렇기 때문에, string을 include하여야만 합니다. 이번에는 Stack 클래스의 멤버 변수를 살펴보도록 합시다.
class Stack {
private:
int count; // = 스택에 존재하는 노드 수
Node* top; // = 가장 위에 있는 노드
Node* list; // = 가장 아래에 있는 노드
..
먼저, count는 스택에 존재하는 노드 수를 알기 위함입니다. push가 이루어 질땐 1이 증가하고, pop이 이루어 질땐 1이 감소합니다. 그 다음, top은 가장 위에 있는 노드를 알기 위함입니다. 링크드 리스트로 치자면 테일(tail)인 셈이죠. 그리고 list는 가장 아래에 있는 노드, 가장 먼저 추가된 노드를 알기 위함입니다. 링크드 리스트로 치자면 헤드(head)가 되겠죠?
..
void push(string data)
{
Node* newNode = new Node; // 새로운 노드를 만든다
newNode->data = data; // 새로 추가된 노드의 데이터에 인자로 받은 data를 대입한다
newNode->nextNode = NULL; // nextNode는 NULL로 초기화 한다
// 만약 리스트가 NULL이라면 = 스택에 데이터가 아무것도 존재하지 않는다면
if (list == NULL) list = newNode; // 새로 추가된 노드를 가장 아래에 있는 노드로 지정한다
else { // 스택에 데이터가 하나 이상 존재할 경우
Node* tmpNode = list; // 임시 노드를 만들고, 가장 아래에 있는 노드를 대입한다
while (tmpNode->nextNode != NULL) // 임시 노드의 다음을 가리키는 노드가 NULL일때까지 반복 = top을 구함
tmpNode = tmpNode->nextNode; // tmpNode는 다음 노드를 가리키게 한다
tmpNode->nextNode = newNode; // 가장 위에있는 노드의 다음 노드를 새로 추가된 노드로 지정한다
}
top = newNode; count++; // 새로 추가된 노드를 가장 위에있는 노드로 지정하고 count를 1 증가시킨다
}
..
이 push 함수는 노드를 새로 추가하고, 가장 위에있는 노드와 새로 추가되는 노드를 연결합니다. 그리고 새로 추가되는 노드를 가장 위에있는 노드라 칭합니다. 만약에, 스택 내에 노드가 하나도 존재하지 않는다면 새로 추가된 노드를 가장 아래에 있는 노드라 칭합니다.
..
Node* pop()
{
Node* topNode = top; // 가장 위에있는 노드의 주소를 다른 포인터에 복사한다
// 만약 list가 비어있다면 = 노드가 하나도 존재하지 않는다 = 스택이 비어있다
if (list == NULL) cout << "스택이 비어있습니다." << endl;
// 최하위 노드와 최상위 노드가 같다면 = 노드가 하나만 존재한다면
// list와 top를 아무것도 가리키게 하지 않고 count를 1 감소시킨다
else if (list == top) { list = NULL; top = NULL; count--; }
// 노드가 두개 이상 존재한다면
else {
Node* currentNode = list; // 최하위 노드의 주소를 다른 포인터에 복사한다
// currentNode 포인터가 NULL를 가리키고 있지 않으며 다음 노드가 최상위 노드일때까지 루프를 돈다
// 즉, currentNode는 최상위 노드에서 하나 아래에 있는 노드를 최종적으로 가리키게 된다
while (currentNode != NULL && currentNode->nextNode != top)
// currentNode의 다음 노드 주소값을 currentNode에 대입한다
currentNode = currentNode->nextNode;
// currentNode를 최상위 노드로 지정한다
top = currentNode;
currentNode->nextNode = NULL; // currentNode가 가리키는 다음 노드를 NULL로 변경한다
count--; // count를 1 감소시킨다
}
return topNode; // 제거된 이전의 top 노드의 주소값을 반환한다
}
..
이 pop 함수는 노드가 두개 이상 존재할 경우, top 노드의 이전 노드를 구하고, 그 이전 노드를 top 노드로 지정합니다. 그런 뒤에 그 이전 노드가 가리키는 다음 노드를 NULL로 대입함으로써 이전 top 노드와 currentNode의 연결을 끊습니다. 만약에 최하위 노드와 최상위 노드가 같은 곳을 가리킨다면 그것은 분명, 노드가 하나만 존재한다는 뜻입니다. 그렇다면, 바로 list와 top에 NULL를 대입하고 count를 감소시킴으로써 pop 연산을 수행할 수 있습니다. 그 다음, 나머지 함수들을 살펴보도록 합시다.
..
int getSize() { return count; } // 현재 스택 내에 있는 노드의 수를 반환한다
bool isEmpty() { return (list == NULL); } // 스택이 비어있으면 true, 비어있지 않다면 false
Node* getTop() { return top; } // 가장 위에있는 노드의 주소값을 반환한다
..
getSize 함수는 스택 내에 존재하는 노드의 수를, isEmpty는 스택이 비어있는지의 여부를, getTop는 최상위 노드를 가져오기 위함입니다. 간단하죠? 이제는, 전체 코드를 보도록 합시다.
예>
#include <iostream>
#include <string>
using namespace std;
typedef struct node
{
string data; // 데이터 필드
struct node* nextNode; // 위의 노드를 가리키는 포인터 (스택이기 때문에)
} Node;
class Stack {
private:
int count; // = 스택에 존재하는 노드 수
Node* top; // = 가장 위에 있는 노드
Node* list; // = 가장 아래에 있는 노드
public:
Stack()
{
count = 0; // count를 0으로 초기화
top = NULL; // top을 NULL로 초기화
list = NULL; // list를 NULL로 초기화
}
void push(string data)
{
Node* newNode = new Node; // 새로운 노드를 만든다
newNode->data = data; // 새로 추가된 노드의 데이터에 인자로 받은 data를 대입한다
newNode->nextNode = NULL; // nextNode는 NULL로 초기화 한다
// 만약 리스트가 NULL이라면 = 스택에 데이터가 아무것도 존재하지 않는다면
if (list == NULL) list = newNode; // 새로 추가된 노드를 가장 아래에 있는 노드로 지정한다
else { // 스택에 데이터가 하나 이상 존재할 경우
Node* tmpNode = list; // 임시 노드를 만들고, 가장 아래에 있는 노드를 대입한다
while (tmpNode->nextNode != NULL) // 임시 노드의 다음을 가리키는 노드가 NULL일때까지 반복 = top을 구함
tmpNode = tmpNode->nextNode; // tmpNode는 다음 노드를 가리키게 한다
tmpNode->nextNode = newNode; // 가장 위에있는 노드의 다음 노드를 새로 추가된 노드로 지정한다
}
top = newNode; count++; // 새로 추가된 노드를 가장 위에있는 노드로 지정하고 count를 1 증가시킨다
}
Node* pop()
{
Node* topNode = top; // 가장 위에있는 노드의 주소를 다른 포인터에 복사한다
// 만약 list가 비어있다면 = 노드가 하나도 존재하지 않는다 = 스택이 비어있다
if (list == NULL) cout << "스택이 비어있습니다." << endl;
// 최하위 노드와 최상위 노드가 같다면 = 노드가 하나만 존재한다면
// list와 top를 아무것도 가리키게 하지 않고 count를 1 감소시킨다
else if (list == top) { list = NULL; top = NULL; count--; }
// 노드가 두개 이상 존재한다면
else {
Node* currentNode = list; // 최하위 노드의 주소를 다른 포인터에 복사한다
// currentNode 포인터가 NULL를 가리키고 있지 않으며 다음 노드가 최상위 노드일때까지 루프를 돈다
// 즉, currentNode는 최상위 노드에서 하나 아래에 있는 노드를 최종적으로 가리키게 된다
while (currentNode != NULL && currentNode->nextNode != top)
// currentNode의 다음 노드 주소값을 currentNode에 대입한다
currentNode = currentNode->nextNode;
// currentNode를 최상위 노드로 지정한다
top = currentNode;
currentNode->nextNode = NULL; // currentNode가 가리키는 다음 노드를 NULL로 변경한다
count--; // count를 1 감소시킨다
}
return topNode; // 제거된 이전의 top 노드의 주소값을 반환한다
}
int getSize() { return count; } // 현재 스택 내에 있는 노드의 수를 반환한다
bool isEmpty() { return (list == NULL); } // 스택이 비어있으면 true, 비어있지 않다면 false
Node* getTop() { return top; } // 가장 위에있는 노드의 주소값을 반환한다
};
int main()
{
Stack stack; // 스택 클래스를 기반으로 한 객체
int getSize; // stack의 노드 수를 담을 변수
// 스택에 순서대로 삽입(push)한다
stack.push("Internet Explorer");
stack.push("Google Chrome");
stack.push("Opera");
stack.push("Netscape");
stack.push("Mozilla Firefox");
stack.push("Safari");
// stack의 노드 수를 getSize 변수에 담는다
getSize = stack.getSize();
// stack의 노드 수만큼 루프를 돈다
for(int i=0; i<getSize; i++)
{
if (stack.isEmpty()) break; // 만약 스택이 비어있을 경우 빠져나온다
// pop 연산을 수행하며 스택의 제거되는 데이터를 출력한다.
cout << "제거되는 데이터: " << stack.pop()->data << ", ";
// 스택이 비어있지 않을 경우에
if (!stack.isEmpty()) cout << "현재 최상위 데이터: " << stack.getTop()->data << endl;
// 스택이 비어있을 경우에
else cout << "최상위 데이터가 존재하지 않습니다." << endl;
}
return 0;
}
결과:
제거되는 데이터: Safari, 현재 최상위 데이터: Mozilla Firefox
제거되는 데이터: Mozilla Firefox, 현재 최상위 데이터: Netscape
제거되는 데이터: Netscape, 현재 최상위 데이터: Opera
제거되는 데이터: Opera, 현재 최상위 데이터: Google Chrome
제거되는 데이터: Google Chrome, 현재 최상위 데이터: Internet Explorer
제거되는 데이터: Internet Explorer, 최상위 데이터가 존재하지 않습니다.
계속하려면 아무 키나 누르십시오 . . .
메인 함수를 보시면 크게 달라진게 없습니다. 한가지 중요한 특징은, 처음 구현한 스택과는 달리 용량에 제한이 없어졌다는 것을 명심하셔야 합니다. 장점이 있으면 반대로 단점도 존재합니다. 첫 구현과는 달리 삽입과 제거가 좀더 복잡해져 시간이 오래걸린다는 단점이 있습니다. 스택(Stack)은 메모리 구조에서도 등장하고 후위 표현식 계산도 좀더 간단하게 할 수 있다는 이점을 지니고 있습니다.
여기까지 스택(Stack)이란 자료구조에 대해 알아보았고, 다음 강좌에는 큐(Queue)에 대해 알아보도록 하겠습니다. 읽어주셔서 감사합니다. 모두 수고하셨습니다.
'알고리즘, 자료구조' 카테고리의 다른 글
| 자료구조 4강. 트리(Tree) (4) | 2013.01.23 |
|---|---|
| 자료구조 3강. 큐(Queue) (4) | 2013.01.15 |
| 자료구조 1강. 리스트(List) (20) | 2013.01.01 |
| 비주얼베이직6 움직임에 관한 수학공식 정리 (4) | 2012.10.03 |
| 알고리즘 1-1강. 정렬 (16) | 2012.05.27 |