자료구조 Data structure
문제 해결에 있어 가장 효율적인 구조로 표현한 것.
알게모르게 관람차도 자료구조를 연상시킨다.
스택 Stack
입력과 출력이 하나의 포인터에서 일어나는 구조.
나중에 입력된 데이터가 먼저 출력되므로
후입선출(後入先出), LIFO(Last In First Out)라고 할 수 있다.
포스팅 사상 최초 3개 언어 등장.
이게 스택이다.
가장 밑의 까만돌을 먼저 두었으나, 꺼낼 수 있는건 가장 위의 작은 돌이다.
행여 엎어버리려는 생각을 가졌다면 그것은 구조를 무너뜨린다.
푸시 PUSH
데이터의 삽입.
자세한 알고리즘은 알고리즘 카테고리에서 다룰 예정이다.
일단 개념만 살펴보자.
TOP 포인터를 삽입 위치에 위치시킨 후 데이터를 강력하게 푸시한다.
단, TOP 포인터가 스택의 크기를 벗어나지 않도록 한다.
벗어날 경우 오버플로우(Overflow)를 발생시킨다.
팝 POP
데이터의 삭제.
현 TOP 포인터 위치에서 삭제 후 TOP 포인터 이동한다..
단, TOP 포인터가 스택의 크기를 벗어나지 않도록 한다.
벗어날 경우 언더플로우(Underflow)를 발생시킨다.
오버/언더 플로우
직역하면 위로 넘치거나 아래로 넘친다는 의미다.
컴퓨터에선 표현 가능한 범위를 벗어났을 경우를 말한다.
가령, 필자에게 아랍어를 요구할 때 어버버 발생,
필자의 표현 범위를 벗어났으므로 이것도 일종의 플로우가 아닐까 싶다.
컴퓨터에선 이렇게 아름다운 플로우를 기대할 수 없다.
자세한건 운영체제 카테고리에서 다룰 예정이므로 넘어간다.
예
편집기에서 Ctrl + Z와 같은 되돌리기(Undo) 기능.
대표적인 스택의 예다.
Ctrl + Y에 해당하는 되살리기(Redo)도 마찬가지라고 할 수 있다.
큐 Queue
입력과 출력이 나눠져 두 포인터로 운용되는 구조.
먼저 입력된 것이 먼저 출력되므로
선입선출(先入先出), FIFO(First In First Out)의 특징이 있다.
입력은 뒤에서만 출력은 앞에서만 이루어지는 줄의 형태 또한 큐의 대기모습과 같다.
삽입
Rear 포인터에서 삽입이 이루어진 후 한 칸 이동한다.
마찬가지로 Rear 포인터가 크기를 벗어난다면
오버플로우가 발생한다.
삭제
Front 포인터에서 삭제가 이루어진 후 한 칸 이동한다.
Front 포인터와 Rear 포인터의 위치가 같을 경우
언더플로우가 발생한다.
문제점
Front와 Rear 포인터 모두 한 방향으로 전진만 한다.
즉, 길이 막히면 돌아올 생각을 안해서 저장공간의 낭비가 발생한다.
돌아가면 해결될 것을 전진만 하려 한다.
그래서 이러한 문제점이 보완된 큐가 등장했다.
환형큐 Circular Queue
마지막 위치까지 삽입 한 후 삽입 포인터를 처음 위치로 이동시킨다.
(이미지 출처 : 나무위키)
즉, 우로보로스처럼 꼬리를 물고 있는 형태의 큐.
예
(동영상 출처 : 유튜브)
햄스터의 쳇바퀴도 처음위치로 돌아오니 환형큐랄까.
이동큐 Moving Queue
삽입과 삭제포인터의 위치가 같아질 경우 처음 위치로 이동시킨다.
데크 DEQUE
Double Ended QUEue의 줄임말로 양쪽에서 입출력이 발생하는 구조.
뒤로 갈수록 다소 성의가 없어지는 것 같지만
이해를 돕기엔 충분하다고 판단되므로 마치겠다.
끝!
'IT > 자료구조' 카테고리의 다른 글
| 자료형(Data Type)의 종류와 표현범위 (0) | 2016.04.19 |
|---|---|
| [특집] 해시(Hash) :: 개념, 해시 테이블, 해시 함수, 해시 태그, 해시 브라운 (0) | 2016.04.06 |