1. What is Stack?
책상 위에 쌓인 책
책상 위에 책이 쌓여 있습니다. 가장 밑에 있는 책이 가장 먼저 쌓였음에 틀림없습니다. 그리고 가장 위에 있는 책이 가장 최근에 쌓은 책일 것입니다.
가장 밑에 있는 책을 꺼내려면 어떻게 해야 할까요?
책이 매우 무거워서 한 권씩만 꺼낼 수 있다고 가정해 봅시다. 그럼 가장 위에 있는 책부터 한 권씩 꺼내야만 가장 밑에 있는 책에 도달할 수 있습니다.
LIFO(Last-in First-out)
이것이 바로 스택(Stack)입니다. 스택은 가장 최근에 추가된 자료가 가장 먼저 제거됩니다. 이런 순서 규칙을 우리는 LIFO(Last-in first-out)이라고 부릅니다.
top/base
스택은 한 쪽 끝에서만 자료의 추가와 삭제가 일어나는 순서있는(ordered) 집합입니다. 이러한 끝을 top, 그 반대편을 base라고 합니다.
- top : 자료를 넣고 빼는 위치
- base : top의 반대편 끝
2. Stack ADT(Abstract Data Type)
Data
top: 스택의 첫 번째 요소를 가리키는 포인터size: 요소의 개수
Operations
push(item): 새로운 항목을 스택의 맨 위에 추가pop(): 스택의 맨 위 항목을 반환하고 제거topValue(): 맨 위 요소의 복사본을 반환length(): 스택의 요소 개수를 반환isEmpty(): 스택이 비어 있는지 여부를 반환clear(): 스택을 다시 초기화
stack 추상 클래스
다음과 같이 꼭 필요한 기능들만 추상 클래스로 만들어서 구현에 독립된 기능을 보장하도록 해보겠습니다.
#pragma once
template <typename T>
class Stack {
public:
virtual ~Stack() {}
// Reinitialize the stack.
virtual void clear() = 0;
// Push "it" onto the top of the stack.
virtual bool push(T it) = 0;
// Remove and return the element at the top of the stack.
virtual T pop() = 0;
// Return a copy of the top element.
virtual T topValue() = 0;
// Return the number of elements in the stack.
virtual int length() = 0;
// Tell if the stack is empty or not.
virtual bool isEmpty() = 0;
};3. Stack 구현
3-1. Array-based stack
#include <iostream>
#include "Stack.h"
using namespace std;
template <typename T>
class AStack : public Stack<T> {
public:
T* stackArray; // Array holding stack elements
static const int DEFAULT_SIZE = 10; // Default size
int maxSize; // 할당 크기를 위해
int top; // top의 위치
// 생성자
AStack(int size = DEFAULT_SIZE) {
stackArray = new T[size]; // 동적 할당
top = 0;
maxSize = size;
}
// 소멸자
~AStack() { delete[] stackArray; }
void clear() { top = 0; }
bool push(T it) {
if (top >= maxSize)
return false;
stackArray[top++] = it;
return true;
}
T pop() {
if (top == 0)
{
cout << "빈 스택입니다\n";
return T();
}
return stackArray[--top];
}
T topValue() { return stackArray[top - 1]; }
int length() { return top; }
bool isEmpty() { return top == 0; }
};3-2. Linked Stack
Linked Stack은 Single Linked List로 구현가능합니다. 데이터의 입출력이 한 쪽 끝에서만 이루어지고, 랜덤 엑세스를 하지 않기 때문입니다.
Linked Stack에서 pop()하는 과정을 살펴보겠습니다.
값의 반환을 위해 top의 값을 it 변수에 복사해놓습니다.
그리고 top이 top의 next를 가리키도록 합니다. 그리고 원래 top이 가리키던 메모리 공간은 반납해버리면 되겠죠.
it을 반환하면 끝입니다.
Single Linked List의 노드를 표현할 때 썼던 Link 클래스를 그대로 사용하여 Linked Stack을 구현해 보겠습니다.
#include <iostream>
#include "Link.cpp"
#include "Stack.h"
using namespace std;
template <typename T>
class LStack : public Stack<T> {
public:
Link<T>* top;
int stackSize;
//생성자
LStack() { top = nullptr; stackSize = 0; }
//소멸자
~LStack() {
// 명시적으로 delete
while (top != nullptr) { // top이 nullptr이 될 때까지 반복
Link<T>* tmp = top;
top = top->next(); // 다음 노드로 이동
delete tmp; // 현재 노드 메모리 해제
}
}
void clear() {
// 명시적으로 delete
while (top != nullptr) {
Link<T>* tmp = top;
top = top->next();
delete tmp;
}
stackSize = 0;
}
bool push(T it) {
top = new Link<T>(it, top);
stackSize++;
return true;
}
T pop() {
if (stackSize == 0) {
cout << "스택이 비었음\n";
return T();
}
Link<T>* tmp = top;
T it = top->element();
top = top->next();
stackSize--;
delete tmp;
return it;
}
T topValue() {
if (top == nullptr) {
cout << "빈 스택입니다.\n";
return T();
}
return top->element(); }
int length() { return stackSize; }
bool isEmpty() { return stackSize == 0; }
};