안녕하세요~ 준형입니다.
오랜만에 블로그에 왔는데 이번에는 자료구조를 배우면 거의 초반에 배우는
비교적 쉬운 자료구조인 스택을 쉽고 정확하고 확실하게! 알려드리기 위하여 글을 쓰러 왔습니다.
순서는
1. 스택이란 무엇인지 간단하게 알아보고
2. 코드와 함께 구현과 동작 원리를 알려드리고
3. 마지막으로 2번 과정으로 작성된 코드의 동작까지 한번 확인해보죠
스택이란 무엇인가?
스택의 기본 동작 과정은 후입선출 (Last in First Out)
즉, 가장 마지막에 들어간 데이터(가장 최근에 들어온 데이터)가 가장 먼저 빠져나가는 방식입니다.
실생활에 간단히 비교해 보자면
물건이 쌓여 있을 때 가장 위에 있는 물건부터 집어가듯 스택도 똑같다고 생각하시면 될 거 같습니다.
그림으로도 간단하게 보여드리자면
자 여기까지가 스택이 무엇인지 대충 감을 잡는 시간이었고 이제 본격적으로 스택 구현 방법 알려드리겠습니다.
스택의 구성, 그리고 구현까지
먼저 스택의 구성부터 알려드리겠습니다.
| STACK 구조체 | 스택의 본체 |
| init_stack | 스택의 초기화 (스택의 초기 상태) |
| empty_check 함수 | 스택이 비어있는지 체크하기 위한 용도 |
| full_check 함수 | 스택이 꽉 차있는지 확인하기 위한 용도 |
| add 함수 | 스택에 데이터를 추가하는 함수 |
| get 함수 | 스택에 데이터를 추출하는 함수 |
| peek 함수 | 스택 최상단의 데이터를 확인 하는 함수 |
자 그러면 스택의 본체인 스택 구조체부터 알아보시죠
스택의 본체인 구조체 부분은 원하는 데이터 타입의 배열과 현재 데이터의 위치를 저장해 줄 변수 이렇게 두 개로 구성되어 있습니다. 먼저 저는 간단하게 int 타입 100칸짜리 배열 스택으로 가보겠습니다. 다음 단계로는
스택 구조체를 초기값으로 세팅해 주는 함수 init_stack을 한번 알아보죠
스택 초기값 세팅 함수 init_Stack
별거 없습니다. 여기서 탑을 -1로 초기화해 주는 이유는 데이터가 한 개 들어오면 탑이 +1 되어 0이 되는데
0이 배열 인덱스의 첫 번째 요소이기 때문에 탑을 -1로 주어 비어있는 스택을 의미하게 합니다.
다음으로는 스택에 데이터를 추가하고 꺼내기 전에 꽉 찼는지 비어있는지 확인을 해주어야 되기 때문에
empty, full check 함수를 만들어보겠습니다,
스택의 상태 판단 함수 empty_check, full_check
먼저 스택이 비어있는지 확인하는 함수는 방금 말했듯이 탑이 -1이 비어있는 스택을 의미하므로 탑이 -1인지만 체크해 주면 됩니다. 리턴값으로는 1(true), 0(false)를 해주는 것이죠.
스택이 꽉 차있는지 확인하는 함수는 처음 스택 구조체에서 저는 SIZE(100) 짜리 데이터 배열을 선언해 두었는데 100짜리 배열의 마지막 인덱스는 99번째 이기 때문에 SIZE-1로 현재 탑의 위치가 배열의 끝자락까지 왔는지 확인합니다.
자 그러면 이제 본격적으로 스택에 데이터를 집어넣으러 가봅니다.
스택에 데이터 추가 함수 add
스택에 데이터를 추가하기 전에 먼저 체크해야 될 것이 있죠. 바로 스택이 꽉 찼는지 먼저 확인을 해야 합니다!
그래서 방금 저희가 만들어둔 함수가 있죠 바로 full_check. 이것을 이용하여 full_check에서 참(1)을 리턴하였다면 저장할 공간이 없다 안내해 주고 리턴하여 함수를 종료해 버립니다. 그렇지 않다면? 이제 값을 넣어야죠.
top의 위치를 한 칸 더해주고 난 뒤에 해당 위치에 매개변수로 입력받은 데이터를 넣어줍니다.
스택의 데이터 추출함수 get
데이터를 추출할 때는 꺼낼 때와는 반대로 스택이 비어있는지 먼저 확인을 해주어야 합니다.
만들어둔 empty_check 함수를 이용하여 확인하는데 이번에는 스택이 공백 상태라면 함수를 종료시키는 것이 아니라 프로그램을 종료시킵니다. 리턴 값이 있는 함수 이기 때문에 없는데도 무언가를 뱉어낼 수는 없기 때문이죠.
그러면 이제 비어있지 않은 경우 추출하는 부분도 보죠, 리턴 값으로 바로 탑에 위치한 데이터를 바로 주는데
추출을 하였으면 탑의 위치도 한 칸 빼줘야 하기 때문에 s->data [s->top--]로 추출과 동시에 탑은 1칸 마이너스되게 합니다.
현재 top에 위치한 값 확인 함수 peek
음.. 이거는 사실 바로 위에 추출 함수와 거의 동일합니다.
딱 한 가지의 차이가 있는데 추출 함수는 말 그대로 추출이기에 추출 후 top도 한 칸 줄여줬지만 peek는 그럴 필요가 없죠
바로 그냥 탑에 위치한 값만 리턴해줍니다.
자 이제 이렇게 저희가 짠 코드를 종합해 보면..!
짠! 요런 느낌이죠 이제 메인함수에서 구현된 스택이 올바르게 작동하는지도 확인해 볼까요?
1,2,3,4 숫자를 차례대로 집어넣고 스택이 제기능을 하는지 즉,
가장 마지막에 들어간 4부터 시작하여 4,3,2,1 이렇게 출력이 되는지 보죠.
Good! 잘 작동합니다.
자.. 여기까지가 기본적인 스택의 구조였습니다. 도움이 되셨나요? 궁금한 점이 있다면 뭐든 질문해주세요!
감사합니다.