Stack
stack은 단어가 쌓다 뭐 이런 뜻이죠.
말 그래도 쌓는다 이렇게 이해하면 됩니다.
위 그림 처럼 동전을 쌓는다고 생각하고 원소를 하나씩 push (넣는다) 하면 밑에 부터 쌓이게 됩니다.
pop을 하는 것은 원소를 빼는 것이고 stack은 위에서부터 하나씩 빼는 방식을 가지고 있습니다.
스택 클래스는 위 처럼 구성할 것이고 STL 스택을 써보신 분들은 아시겠지만 data type을 stack을 선언할 때 사용자가 정할 수 있습니다. 그것과 똑같이 만들기 위해 template class를 사용하여 data type을 사용자가 설정할 수 있도록 만들었습니다.
그래서 코드를 보시면 template<class ItemType> 으로 선언된 것을 볼 수 있습니다.
Stack을 구현하는 세 가지 방법이 있습니다.
하나는 배열을 이용한 방법(static 방식).
두번째는 pointer를 이용하는 방법 이렇게 말이죠(dynamic 방식).
세번째는 Linked structure를 이용한 방법이 있습니다.
세 가지 모두 구현해 보도록 하겠습니다.
Static Allocation
메모리 공간이 compile time에 결정이 됩니다.
Dynamic Allocation
메모리 공간이 run time에 operator new를 사용할 때 결정이 됩니다.
전체 코드는 https://github.com/goragoraki/Data-Structure 에 주석과 함께 올려두었으니
코드를 참고 하실분은 여기서 보시면 됩니다.
배열
top이라는 변수를 설정해주고 현재 높이를 나타냅니다. -1을 초기값으로 해서 push가 될때마다 +1을 해주고
pop이 될때마다 -1을 해주면 됩니다.
그리고 item을 저장하는 배열을 선언해줍니다. 그리고 push라면 item[top]에 원소 추가 후 top++, pop이라면 top--.
top 함수는 stack 맨 위에 있는 원소를 리턴하는 함수로 그냥 return item[top]을 해주면 됩니다.
Pointer
포인터로 구성할 때도 많이 달라지는 것은 없습니다.
여기에는 생성자에 파라미터를 이용해서 max공간을 잡을 수 있도록 만들어 놓았습니다.
생성자에서
이런식으로 items에 동적 할당을 하기 위해서 new라는 operator를 써주시면 됩니다.
그 다음은 배열과 동일 합니다.
Linked structure
이 구현 방식이 3가지 중에서는 제일 어렵다고 생각이 됩니다.
이것을 이해하기 위해서는 pointer에 대한 부분을 잘 이해를 해야지 구현이 가능합니다.
일단 구현하기 앞서 NodeType이라는 것을 이해해 주어야합니다.
또노드 타입을 가르키는 포인터를 잘못 바꾸게 되면 노드 타입이 메모리에 남아 메모리 누수를 일으킬 수 있기 때문에 주의 해야합니다.
우리는 이 노드타입이라는 구조체를 연결 시켜 stack을 구성합니다.
이런식으로 말입니다. 하나의 NodeType은 info와 next 변수를 가집니다.
info는 말 그대로 우리가 보관하고 싶은 원소를 저장합니다.
next는 다음 NodeType을 가르키는 포인터 변수입니다. 그렇기 때문에 우리는 이 next를 이용하여 다음 NodeType을 연결시켜 스택을 유지합니다.
Push 함수 구현
항상 pointer를 다룰때는 순서에 주의해야합니다.
먼저 새로운 노드타입의 노드를 생성해주고 그 안에 값들을 채워 넣습니다.
그 후 새로운 노드타입의 next에 topPtr이 가르키고 있던 노드타입을 가르키도록 넣어주고
topPtr을 새로운 노드타입을 가르키게 하면 됩니다.
이렇게 하면 새로운 노드타입을 추가할 수 있습니다.
Pop 함수 구현
tempPtr로 만들어서 top의 노드타입을 가르칩니다.
그 다음 topPtr을 topPtr = topPtr->next로 해서 다음 노드를 가르킨 후 delete를 이용해 맨 앞쪽 노드였던 것을 삭제해주면 됩니다.
시간 복잡도
main.cpp는
이런식으로 기둥이 있다고 하고 왼쪽에서 볼 때 보이는 기둥의 개수를 출력하는 것으로 만들어 놓았습니다.
Stack을 활용하면 쉽게 풀 수 있겠죠.
전체 코드는 https://github.com/goragoraki/Data-Structure 에 방문해서 봐주시면 됩니다.
다음글은 queue에 대한 설명으로 stack을 잘 이해하셨다면 queue는 쉽게 이해가 가능합니다.
'CS > 자료구조(Data Structure)' 카테고리의 다른 글
| [자료구조] Binary Search Tree c++ 구현 [컴공과고씨] (0) | 2023.01.26 |
|---|---|
| [자료구조] Quick sort(퀵 정렬) 구현 c++ [컴공과고씨] (0) | 2023.01.20 |
| [자료구조] Linked List(링크드 리스트) c++ 구현 [컴공과고씨] (0) | 2023.01.19 |
| [자료구조] Queue(큐) 구현 c++ [컴공과고씨] (0) | 2023.01.15 |
| [자료구조] 리스트(unsorted & sorted list) c++ [컴공과고씨] (0) | 2023.01.12 |