자료구조란?
자료구조는 여러 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것이다. 데이터를 체계적으로 정리하여 저장하는 것이 데이터를 사용할 때 유리하므로 자료구조를 잘 활용하는 것이 좋다.자료 구조를 눈으로 볼 수 있는 사이트
VisuAlgo
Data Structure Visualizations
Stack
Stack이란?
Stack은 데이터를 순서대로 쌓는 자료구조이다. 일상 생활에서 예를 들면 끝이 막혀있는 골목에 차들이 들어오는 걸 생각하면 된다. 끝이 막혀있으니 차는 계속 쌓일 것이고 여기서 탈출하려면 맨 마지막에 들어온 차부터 빠져나와야 한다. 여기서 골목은 Stack, 자동차는 데이터로 비유할 수 있다.
Stack의 특징
- LIFO(Last In First Out, 후입선출)
👉 이러한 특성으로 인해 스택은 조회가 필요하지않으므로 데이터를 저장하고 검색하는 프로세스가 빠르며 최상위 블록에서 데이터를 저장하고 검색하면 된다는 장점이 있다. - 데이터는 하나씩 넣고 뺄 수 있다.
- 하나의 입출력 방향을 가지고 있다.
- 저장되는 데이터는 유한하고 정적이어야 한다.
- 스택의 크기는 제한되어 있다.
Stack 예시
컴퓨터에서 Stack이 대표적으로 사용되는 곳은 브라우저의 앞으로 가기, 뒤로 가기 기능이다.
- 새로운 페이지로 접속할 때 현재 페이지를 Prev Stack에 보관한다.
- 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
- 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는 Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.
- 마지막으로 현재 페이지를 Prev Stack에 보관한다.
Queue
Queue란?
큐는 줄을 서서 기다리다, 대기 행렬이라는 뜻을 가지고 있다. 일상 생활에서 예를 들면 고속도로를 지나는 차의 모습을 생각하면 된다. 가장 먼저 톨게이트에 진입한 차가 가장 먼저 톨게이트를 통과한다. 여기서 고속도로의 톨게이트를 Queue, 자동차는 데이터에 비유할 수 있다.
Queue의 특징
- FIFO(First In First Out, 선입선출)
- 데이터는 하나씩 넣고 뺄 수 있다.
- 두 개의 입출력 방향을 가지고 있다.
데이터를 넣는 것을enqueue, 꺼내는 것을dequeue라고 한다.
Enqueue 기능
Enqueue는 큐 자료구조에 데이터를 넣는 기능을 수행한다. 앞서 비유한 톨게이트에 자동차들이 줄을 서있다면 톨게이트 맨앞에 있는 자동차를 front라 하고 마지막에 있는 자동차를 rear라고 부른다.
1번 자동차가 Enqueue되면 front와 rear 모두 1번 자동차를 가리킨다.
다음으로 2번 자동차가 Enqueue되면 front는 고정이고 rear만 나중에 들어온 2번 자동차를 가리킨다.
이런 식으로 rear 인덱스가 점점 증가된다.
Dequeue 기능
Dequeue는 반대로 Queue에서 데이터를 내보내는 기능을 수행한다. 보통은 Dequeue 기능을 수행하고 front의 인덱스를 증가시키는데 이렇게 되면 rear이 배열의 마지막 인덱스를 가리키게 되면서 앞에 남아있는 (삽입 중간에 Dequeue되어 비어있는 공간) 공간을 활용할 수 없게 된다. 이 방식을 해결하기 위해서 아래 그림처럼 Dequeue를 할때 front를 고정시킨 채 뒤에 남아있는 데이터를 앞으로 한칸씩 당기거나 원형 큐를 사용한다.
Queue 예시
컴퓨터 장치들 사이에서 데이터를 주고받을 때 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용한다. 이것을 통틀어 버퍼라고 한다.
대부분의 컴퓨터 장치에서 발생하는 이벤트는 불규칙적으로 발생한다. 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도는 갖는다. 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼를 사용한다.
컴퓨터와 프린터 사이의 데이터 통신 정리
- CPU와 프린터의 속도를 비교하면 상대적으로 CPU가 데이터를 처리하는 속도가 빠르다.
- 따라서 CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.
- 프린터는 인쇄 작업 Queue에서 데이터를 받아 일정한 속도로 인쇄한다.
동영상 스트리밍을 통해 동영상을 시청할 때 다운로드된 데이터가 영상을 재생하기에 충분하지 않은 경우가 있다. 이때 동영상을 정상적으로 재생하기위해 Queue에 모아두었다가 충분한 양의 데이터가 모이면 동영상을 재생한다.
참고
