1. 개요
항상 무언가를 공부하거나 새로운 지식을 학습할 때, 알아야하는 것은 내가 학습하려는 것이 어디에 사용되고, 본질이 무엇인지에 대해서이다. 그러나 이것이 내가 공부하는 모든 지식에 적용되지는 않는 것 같다. 그 중 하나가 바로 자료구조이다. (적어도 나에게는) 자료구조라는 과목이 얼마나 중요한지는 유튜브에 '개발'이나 '프로그래밍' 이라는 키워드로 3분동안만 검색해봐도 알 수 있는 사실이다. 그렇게 악명 높은 코딩 테스트도 가장 기초가 되는 부분이 바로 자료구조라는 사실은 조금만 찾아봐도 알 수 있다.
그러나 나는 아직도 내가 배우는 이 자료구조들이 실무에서 어떤 모습으로 사용되는지는 알지 못한다. 그저 원리와 구현 방법 그리고 이론으로 설명되는 활용 방법과 응용 문제들을 푸는 수준이다. "이런건 그냥 학부 수준의 과목 아닌가?" 라고 생각할 수도 있겠지만, 실제로 현직 개발자들에게 직접 여쭤보면 다들 중요하다고 하나같이 답해주신다. 스택, 트리, 리스트같은 자료구조들을 자세히 알면 알수록 할 수 있는 것이 많아진다는 말씀과 함께 말이다.
결국 "자료구조는 중요하다" 라는 하나의 신념으로 공부를 진행해야할 수 밖에 없다. 앞으로 이 페이지에 자료구조와 관련된 다양한 글들을 올렸으면 좋겠다.
2. 스택 이론
오늘 배울 자료구조는 "스택" (Stack) 이다. 지금까지 해결한 백준 알고리즘 문제들도 다 스택에 관련된 문제들있었다. 그렇다고 내가 스택을 잘 한다는 것은 아니다. 매소드를 듣고 구현만 하는 수준이기 때문이다. Stack을 위키백과에 검색해보면 다음과 같은 정의를 볼 수 있다.
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.
출처: 위키 백과
설명만 보면 알 것 같기도 하고...... 모를 것 같기도 하다. 확실한 것은 Stack이 동작되는 대표적인 기능을 파악하고, 그것을 구현할 수 있어야 한다. 자 다음은 내가 그린 Stack의 그림이다.
약간 굴둑과 비슷한 형태(실제로 Stack은 굴둑이라는 뜻도 가지고 있다.)의 통 같이 생긴 모습이다. 그리고 Stack은 "무엇"을 담을 수 있는 통이 맞다. 그리고 그 "무엇"을 우리는 요소 라고 한다. 이 요소는 정수가 될 수 있고, 실수가 될 수 있고, 어떤 것이든 될 수 있다. 나는 예시로 '문자열'을 요소로 가지는 Stack을 표현해보았다. 나는 스택이라는 "통" 안에 'dog' 라는 문자열 형태의 "요소"를 집어 넣을 것이다. 그럼 다음과 같은 모습이 된다.
그럼 다음과 같이 스택이라는 "통" 맨 밑에 부분에 요소가 위치하게 된다. 그럼 이제 'cat'이라는 요소를 다시 Stack이라는 "통"에 넣어보겠다. 그럼 다음과 같은 모습이 된다.
가장 먼저 들어간 요소인 'dog' 위에 다음으로 들어간 'cat'이 위치하였다. 자 그럼 마지막으로 내가 제일 좋아하는 동물인 'chicken'이라는 요소를 넣어보겠다. 이미 알겠지만, 그래도 그림으로 표현하자면 다음과 같다.
자 이제 우리는 Stack이라는 통에 요소를 집어넣을 수 있다는 사실과 가장 늦게 들어간 요소일수록 위쪽에 위치한다는 사실을 알 수 있게 되었다. 우리가 물통을 들고다닐 때 물을 보관하기위해서만이 목적은 아닐 것이다. 결국 통 안에 있는 내용물을 꺼내야 그 통은 제 역할을 한다고 할 수 있다. Stack도 마찬가지이다. 이제 Stack안에 있는 요소를 하나씩 꺼내볼 것이다. 그리고 여기서 Stack의 가장 중요한 특징을 알 수 있다. 결론부터 말하자면 Stack의 입구는 위쪽 하나이기 때문에 꺼낼때도 들어가는 곳과 같은 입구를 써야한다. 그렇다면 결국 맨 위에 위치하는 요소부터 꺼낼 수 밖에 없다. 자 다음은 Stack에서 하나의 요소를 꺼내는 모습이다.
그림을 보면 더 확실해진다. Stack에서는 요소를 꺼낼 때, 가장 나중에 들어온 요소가 나온다는 것을 알 수 있다. 이 문장에 더욱 신뢰를 줄 수 있도록, 다음 요소도 꺼내보겠다.
자 다음은 마지막 요소까지 꺼내는 모습이다.
결국 들어간 순서의 반대로 요소들이 나온다는 것을 알 수 있다. 그리고 이것이 바로 Stack의 큰 특징인 'LIFO' 구조라고 한다. 그리고 Stack의 가장 윗 부분을 가르키는 것(변수, 포인터 등등)을 'Top'이라고한다. 'dog'를 넣었을 때는 Top이 'dog' 이고, 'cat'을 넣었을 때는 'Top'이 'cat'이다. Stack에 무엇을 넣는 행위는 'Push', 빼는 행위는 'Pop'이다. 이렇게 보면 위키트리의 설명도 어느저도 이해할 수 있을 것 같기도 하다. 자, 그럼 위의 내용을 전부 정리해보겠다.
Stack 자료구조 : 어떠한 요소(정수, 실수 등등) 을 담을 수 있는 '통' 이다.
Stack의 구조: 가장 먼저 집어놓은 요소가 가장 나중에 나오는 LIFO 구조 이다.
Stack의 매소드(기능)
- 1. Push: Stack에 요소를 집어넣는 것을 의미한다.
- 2. Pop: Stack에서 요소를 꺼내는 것을 의미한다.
- 3. Top: 스택안에 있는 요소들 중 가장 위에 위치한( 가장 나중에 들어간) 요소를 가리키는 포인터(변수) 이다.
3. 스택 구현
자료구조를 잘 하는 편은 아니지만 나름 나의 공부법을 적어보자면 이론을 어느정도 이해하고 다른 사람들의 코드를 보면서 구현해본 다음, 그것을 바탕으로 자신만의 방법으로 스택을 구현해보는 것이 좋다고 생각한다. 이론을 전부 이해하고 코드를 본다면 더욱 좋겠지만 어떨때는 코드를 보면서 이해를 하는 경우도 있기 때문이다. 이 블로그에서는 C, C++로 구현한 Stack의 코드를 올릴것이다. main() 함수는 구성한 자료구조 코드를 테스트하기 위해 작성된 것이므로 별로 상관은 없다.
-C언어로 구현한 Stack
#include <stdio.h>
#define SIZE 100
void Push(int stack[], int *top);
int Pop(int stack[], int *top);
int isFull(int top);
int isEmpty(int top);
void PrintError(char *msg);
int main(void) {
int stack[SIZE];
int top = -1;
while (1) {
int input;
printf("[push: 1 pop: 2 exit: 3]");
scanf("%d", &input);
if (input == 1) {
Push(stack, &top);
printf("\n");
}
else if (input == 2) {
int buff = Pop(stack, &top);
if(buff)
printf("Pop: %d\n\n", buff);
}
else
break;
}
return 0;
}
void Push(int stack[], int *top) {
if (isFull(++(*top))) {
(*top)--;
PrintError("스택이 포화상태입니다.");
}
else {
int item;
printf("정수: ");
scanf("%d", &item);
stack[*top] = item;
}
}
int Pop(int stack[], int *top) {
if (isEmpty(*top)) {
PrintError("스택이 비어있습니다.");
return NULL;
}
return stack[(*top)--];
}
int isFull(int top) {
return top >= SIZE ? 1 : 0;
}
int isEmpty(int top) {
return top == -1 ? 1 : 0;
}
void PrintError(char *msg) {
printf("-----%s-----\n\n", msg);
}
설명하자면, 보통 Stack을 처음 배울 때 배열로 구현하기도 한다. (더 배우면 연결 리스트로 구현하는데, 이는 나중에 설명할 것이다.) C언어의 경우 절차지향이기에, 매소드들을 함수로 구현하고, 배열을 Stack으로 정의하는 경우가 있고, 나 또한 그렇다. 확실히 객체지항이 자료구조에 있어서는 조금더 편할것 같다는 생각을 했지만, C로도 구현해보는 연습을 하는것이 무의미 하지는 않을 것이다.
내가 구현한 매소드들은 매우 기본적인 메소드들이다. Push와 Pop만을 구현하였고, 중간에 보이는 isEmpty와 isFull은 index를 이용하여 스팩의 포화 여부를 알려주는 함수이다. 가끔 자료를 찾아보면 top를 반환하는 메소드, Pop을 하지 않고, 값만을 확인하는 메소드들이 구현된 스택을 볼 수 있다.(실제로 내가 백준알고리즘 문제를 풀 때, 구현한 Stack도 이같은 기능을 포함하고 있다.) 확실한 것은, 이 이론만을 정확하게 이해하면 이런 메소드들을 구현하는 것은 쉬워진다는 것이다.
-C++로 구현한 Stack
다음은 C++로 구현한 Stack이다. C++이기에, Stack이라는 Class를 선언하였다. 다음은 소스 코드이다.
#include <cstdio>
#define SIZE 100
class Stack {
private:
int arr[SIZE];
int top;
public:
Stack() { top = -1; }
void Push();
int Pop();
int isFull();
int isEmpty();
void PrintError(const char *msg);
};
void Stack:: Push() {
top += 1;
if (isFull()) {
top -= 1;
PrintError("함수가 포화상태입니다.");
}
else {
int item;
printf("정수: ");
scanf("%d", &item);
arr[top] = item;
}
}
int Stack::Pop() {
if (isEmpty()) {
PrintError("스택이 비어있습니다.");
return false;
}
else
return arr[top--];
}
int Stack::isFull() {
return top >= SIZE ? true : false;
}
int Stack::isEmpty() {
return top == -1 ? true : false;
}
void Stack::PrintError(const char *msg) {
printf("-----%s-----\n\n", msg);
}
int main(void) {
Stack stack;
while (1) {
int input;
printf("[push: 1 pop: 2 exit: 3]");
scanf("%d", &input);
if (input == 1) {
stack.Push();
printf("\n");
}
else if (input == 2) {
int buff = stack.Pop();
if (buff)
printf("Pop: %d\n\n", buff);
}
else
break;
}
return 0;
}
기본적인 문법은 C와 같다. 다만 클래스 안에 있는 매소드들이기 때문에, C언어 처럼 포인터를 사용할 필요가 없다는 것이다.
3.결어
자료구조 시험공부를 대비하기 위해 작성한 글이지만, 나름 효과가 있다는 것을 느꼈다. 실제라 이 페이지에 글을 쓰면서 내가 몰랐던 C언어에 대한지식도 알게 되었다. 다음은 Queue에 대한 설명을 올릴것이다. 다시한번 말하지만, 나의 코드가 최선은 절대 아니다. 다양한 방법이 있을 것이다. 중요한 것은 Stack이라는 구조의 이해이다.
'programming > 자료구조' 카테고리의 다른 글
| [자료구조] - C언어를 활용한 그래프의 구현 (0) | 2021.03.04 |
|---|---|
| [자료구조] - LCRS_TREE 구현 (C++) (0) | 2021.01.11 |
| [자료구조] - LinkedQueue 구현 (C++) (0) | 2020.07.18 |
| [자료구조] - CircularDoubledLinkedList의 구현 (C++) (0) | 2020.07.13 |
| [자료구조] - LinkedList의 구현 (C언어) (0) | 2020.06.27 |
