스택 ADT에 대한 이해와, 배열과 링크드리스트를 이용하여 구현해봅시다.
스택(Stack)
스택은 무거운 상자들을 쌓아 둔 것이라 생각하면 됩니다. 예시에서도 알 수 있듯이 스택은 들어온 순서의 역순으로 데이터를 꺼낼 수 있는(후입선출, LIFO; last in first out) 자료구조입니다. 스택ADT에는 비어있는지 확인하는 기능과 꽉 차있는지 확인하는 기능, 그리고 스택에 맨 위에 데이터를 쌓는 기능과 맨 위에서 빼는 기능, 마지막으로 데이터를 빼지는 않고 뭐가 맨 위에 있는지 확인하는 기능이 있습니다.
스택 ADT의 구현
위에서 말했듯이 다섯 가지의 기능을 C++로 나타내보도록 합시다.
// C++, 문자열 형을 담는 스택
#include<iostream>
#include<string>
using namespace std;
class Stack {
public:
bool isEmpty() {
// 비어있는지 확인하는 함수
}
bool isFull() {
// 꽉 찼는지 확인하는 함수
}
void push() {
// 새 값을 넣는 함수
}
string pop() {
// 값 하나를 빼는 함수
}
string top() {
// 값 하나를 빼지는 않고 무엇인지 확인하는 함수
}
};이 양식을 활용하여 ADT 내부를 배열과 링크드리스트를 이용하여 구현해봅시다.
배열을 이용한 구현
배열을 이용하면 stack을 간단히 구현할 수 있다는 장점이 있습니다.
class Stack {
private:
string array[100];
int size;
public:
Stack() {
size = 0;
}
bool isEmpty() {
if (size == 0) return true;
else return false;
}
bool isFull() {
if (size == 100) return true;
else return false;
}
void push(string data) {
if (isFull()) { cout << "err! cannot push anymore."; return; }
array[size] = data;
size++;
}
string pop() {
if (isEmpty()) cout << "err! cannot pop anymore.";
else {
string temp = array[size - 1];
array[size - 1].clear();
size--;
return temp;
}
}
string top() {
if (isEmpty()) return "nothing";
return array[size-1];
}
};다만 리스트ADT 때와 마찬가지로 스택의 사이즈를 동적으로 할당할 수 없다는 단점이 있습니다.
링크드리스트를 이용한 구현
링크드리스트를 이용하면 스택의 사이즈를 메모리가 허락하는 한 무한정으로 늘릴 수 있다는 장점이 있습니다.
class Node {
public:
string data;
Node* next = nullptr;
};
class LinkedList {
public:
Node* head;
Node* tail;
LinkedList() {
head = nullptr;
tail = nullptr;
}
};
class Stack {
private:
LinkedList list;
int size;
public:
Stack() {
size = 0;
}
bool isEmpty() {
if (list.head == nullptr) return true;
else return false;
}
//bool isFull() {
// 이 함수는 구현할 필요가 없습니다.
//}
void push(string data) {
Node *newNode = new Node();
newNode->data = data;
if (isEmpty()) {
list.head = newNode;
list.tail = newNode;
}
else {
list.tail->next = newNode;
list.tail = newNode;
}
size++;
}
string pop() {
if (isEmpty()) cout << "err! cannot pop anymore.";
else {
Node* pre = list.head;
while (pre->next != list.tail) pre = pre->next;
pre->next = nullptr;
string temp = list.tail->data;
delete list.tail;
list.tail = pre;
size--;
return temp;
}
}
string top() {
if (isEmpty()) return "nothing";
return list.tail->data;
}
};스택 ADT의 동작
위 두 가지 방법으로 구현된 스택 ADT가 사용자입장에서 구현부를 몰라도 정상적으로 돌아가는지 확인하기 위해 main함수에서 사용해봅시다.
// 이 부분에 각각의 방식으로 구현된 Stack 구현부가 들어가면 됩니다.
int main() {
Stack stack;
cout << "3일 간의 택배보관함 시뮬레이션입니다.\n";
cout << "------------------------------------\n";
cout << "****택배기사 전용****\n";
cout << "택배보관함에 집어넣을 물건을 입력하시오(다음 단계로 넘어가려면 q 입력)\n";
do {
string t;
cin >> t;
if (t == "q") break;
stack.push(t);
} while (true);
cout << "------------------------------------\n";
cout << "****아파트 주민 전용****\n";
cout << "오늘은 몇 개의 택배를 가져가시겠습니까?\n";
int n;
cin >> n;
for (int i = 0; i < n; i++) {
if (stack.isEmpty()) { cout << "택배보관함이 비었습니다!\n"; break; }
cout << stack.pop() << "을(를) 가져갑니다.\n";
}
cout << "Top of the stack is " << stack.top();
}두 방법으로 구현된 Stack에 위 main 함수를 사용하여 차례대로 a, b, c, d를 넣고 4를 입력하면 넣은 순서의 역순으로 d, c, b, a가 콘솔 화면에 출력되는 것을 볼 수 있습니다.
스택의 사용
스택을 사용하는 예로 가장 대표적인 것은 프로그램에서 함수 호출 시 이를 스택에 넣는다는 것입니다. 이로 인해 스택의 한계치 이상의 함수가 호출되면 stack overflow가 발생하며, 이는 재귀함수 호출 시 많이 관찰됩니다.
스택은 미로찾기 알고리즘에도 사용될 수 있습니다. 슈도코드를 통해 어떻게 사용될 수 있는지 살펴봅시다.
// pseudocode of maze solution with STACK
Now-position = START
while ('Now-position' is not an END)
mark now-position visited.
if(there is unvisited position near)
push those positions in STACK
if(STACK is empty)
실패!!
else Pop one element and mark it as 'now-position'
이 뿐만 아니라 스택은 수식을 계산하는 데에 쓰이는 등 많은 활용성을 가지고 있습니다.
