array형식으로도 구현가능하고 linked list로도 구현 가능하여각 장,단점을 생각해 보았다.
array로 구현시
●추가 메모리가 요구 되지 않는다.
● 먼저 array의 강력한 장점인 인덱스로 값을 찾는것이 stack에서는 그렇게 필요하지 않다고 느꼈다
어차피 맨 위의 데이터만 사용하려고 하는 것이기 때문이다.
● 크기에 대한 번거로운 과정이 있을 것이다(새로 할당받고 복사하고 원 메모리 반환)
그에 딸려오는 단편화 문제
Linked list로 구현시
● 임의의 위치에 데이터를 추가,삭제 하는 기능이 없기 때문에 이러한 장점을 살릴 수 없다.
●크기에 제약이 없다!
● 옆의 노드의 주소를 저장 할 공간이 추가 요구 됨
● 맨 위의 데이터만을 참고 한다는 스택의 특징이 랜덤 액세스가 불가능한 연결리스트의 단점을 커버 해줌
나는 무난한 배열로 구현을 해보겠다.
생성 & 소멸 & 멤버 변수
#include <iostream>
using namespace std;
#define INIT_STACK_SIZE 10
template<typename T>
class Stack
{
public:
Stack()
{
data = new T[INIT_STACK_SIZE];
capacity = INIT_STACK_SIZE;
topIndex = -1;
}
~Stack()
{
delete[] data;
data = nullptr;
}
/************생략************/
private:
//스택에 넣을 데이터를 담을 포인터 형
T * data;
//맨 위의 인덱스
int topIndex;
//스택의 총 메모리 양
int capacity;
};
데이터 삽입 (Push)
void Push(T input)
{
++topIndex;
if (capacity <= topIndex)
{
T * temp = new T[capacity * 2];
memcpy(temp, data, sizeof(int) * capacity);
delete[] data;
data = temp;
capacity *= 2;
}
data[topIndex] = input;
}
배열이기 때문에 크기에 대한 처리를 따로 해주었다.
데이터 삭제 (Pop)
void Pop()
{
if (IsEmpty() == true) return;
--topIndex;
}
맨 위의 데이터 꺼내기 (Top)
T Top()
{
if (IsEmpty() == true) return -1;
return data[topIndex];
}
여기서 예외설정을 안해서 알고리즘에서 틀렸었다 😂
결과
사용처
맨 위의 데이터를 다룬다는 것에 대하여 게임의 네비게이션에서 사용 할 수 있을거 같다.
이는 여태 시도하는 경로를 스택에 쌓아둠과 동시에 틀릴 경우 맨위부터 다시 돌아가 다른 경로를 탐색함에 있어서
LIFO인 스택과 같아 잘 맞는다.
[나중에 깊이 우선 탐색이라는 알고리즘이 이와 같다고한다?]
또한 상점에서 거래를 이전으로 돌리는 기능을 구현 할 수 있을 것 같다.(ctrl + z 처럼)
