자료구조
- 여러 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것이다.
- 나이에 관한 데이터가 있으면, 사람의 나이인지, 동물의 나이인지에 대한 정보가 있어야 하며, 이처럼 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다.
- 필요에 따라 데이터의 특징을 잘 파악하여 정리하고 활용할 수 있어야 하며, 데이터를 체계적으로 정리하여 저장하는 게 데이터를 활용하는 데 있어 훨씬 유리하다.
자료구조의 분류
- 자료구조
- 단순구조
- 2진수
- 정수/실수
- 문자/문자열
- 선형구조
- 리스트(배열)
- 연결리스트
- 단순 연결리스트
- 이중 연결리스트
- 원형 연결리스트
- 덱
- 스택
- 큐
- 비선형구조
- 트리
- 일반 트리
- 이진 트리
- 그래프
- 방향 그래프
- 무방향 그래프
- 트리
- 파일구조
- 순차 파일
- 색인 파일
- 직접 파일
- 단순구조
자주 등장하는 네 가지 자료구조
- Stack 바보
- Queue
- Tree
- Graph
자료구조의 특징
- 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다.
- 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다.
Stack
- Stack은 쌓다,쌓이다,포개지다 라는 뜻을 가지고 있으며, 의미 그대로 데이터를 순서대로 쌓는 자료구조를 말한다.
- 입력과 출력이 하나의 방향으로, 최상단에서만 이루어지는 제한적 접근이라는 특징이 있다.
이러한 자료구조의 정책을 LIFO(Last In First Out), FILO(First In Last Out)이라 부르기도 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
예1) 1, 2, 3, 4를 스택에 차례대로 넣습니다. stack.push(데이터) | 4 | <- top | 3 | | 2 | | 1 | 들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다. 예2) 스택이 빌 때까지 데이터를 전부 빼냅니다. stack.pop() | | | | | | | | 4, 3, 2, 1 제일 마지막에 있는 데이터부터 차례대로 나오게 됩니다.
- 데이터를 넣는 것을 PUSH, 꺼내는 것을 POP이라고 한다.
- 하나의 입출력 방향을 가진 후입선출의 구조로 되어 하나의 입출력 방향을 가지고 있으며, 데이터를 넣을 때도 최상단으로 넣고 뺄 때도 최상단으로 데이터를 뺀다.
- 데이터를 넣고 뺄 수 있는 경로가 한 군데이기 때문에 항상 데이터를 하나씩만 뺄 수 있다.
브라우저의 뒤로 가기, 앞으로 가기 기능 예제
- 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관한다.
- 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
- 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때는 Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.
- 마지막으로 현재 페이지를 Prev Stack에 보관한다.
Queue
- 줄을 서서 기다리다, 대기행렬 이라는 뜻을 가지고 있다.
고속도로를 예로 들어, 톨게이트는 Queue, 자동차는 data로 비유할 수 있다.
![183900533-71d772d3-14e3-49e2-97fa-4473d7756f39]()
- 가장 먼저 진입한 자동차가 가장 먼저 톨게이트를 통과한다.
- 가장 나중에 진입한 자동차는 먼저 도착한 자동차가 모두 빠져나가기 전까지 톨게이트를 빠져나갈 수 없다.
Queue의 구조
- Stack 개념과 반대로, 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)의 특징을 갖고 있다.
- 입력의 방향과 출력의 방향이 각각 고정되어 있으며, 데이터를 입력할 시에는 큐의 끝에서, 데이터를 출력할 때는 큐의 맨 앞에서 진행된다.
- Queue에 데이터를 넣는 것을 ‘enqueue’, 데이터를 꺼내는 것을 ‘dequeue’라고 한다.
Queue의 특징
FIFO(First In First Out)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
예1) 1, 2, 3, 4를 큐에 차례대로 넣습니다. queue.enqueue(데이터) 출력 방향(head) <---------------------------< 입력 방향(tail) 1 <- 2 <- 3 <- 4 <---------------------------< 들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다. 예2) 큐가 빌 때까지 데이터를 전부 빼냅니다. queue.dequeue(데이터) 출력 방향(head) <---------------------------< 입력 방향(tail) <---------------------------< 1, 2, 3, 4 제일 첫 번째 있는 데이터부터 차례대로 나오게 됩니다.
- 두 개의 입출력 방향을 가지고 있어 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없다.
- 데이터는 하나씩 넣고 뺄 수 있다.
- 큐의 맨 앞부분에서 처리하기 때문에 각 처리 시마다 한 개의 데이터를 넣거나 뺄 수 있다.
- 큐에 한 개 씩 여러 번 데이터를 넣어 큐 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 큐의 맨 앞에서 한 번에 한 개의 데이터만을 뺄 수 있다.
Queue의 실사용 예제
- 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄하는 방법
- 우리가 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 Queue에 들어간다.
- 프린터는 인쇄 작업 Queue에 들어온 문서를 들어온 순서대로 인쇄한다.
- 위 예시처럼 각 장치 사이에 존재하는 속도의 차이나 시간의 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용한다.
- 이것을 통틀어 버퍼(buffer)라고 한다.
- 대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생하지만, CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖고, 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼를 사용한다.
- 일반적으로 프린터는 속도가 느리다.
- CPU는 프린터와 비교하여 데이터를 처리하는 속도가 빠르다.
- 따라서 CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.
- 프린터는 인쇄 작업 Queue에서 데이터를 받아 들어온 순서대로 일정한 속도로 인쇄한다.
- 유튜브와 같은 동영상 스트리밍 앱을 통해 동영상을 시청할 때, 다운로드 된 데이터가 영상을 재생하기에 충분하지 않은 경우, 동영상을 정상적으로 재생하기 위해 Queue에 모아 두었다가 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생한다.