자료구조
자료구조는 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.
데이터의 정해진 규칙 없이 저장하거나, 하나의 구조로만 정리하고 활용하는 것보다 필요에 따라 데이터의 특징을 잘 파악하여 정리하고 활용해야 한다. 데이터를 체계적으로 정리하여 저정하게 되면, 데이터를 활용하는 데 있어서 더 유리하다.
자료구조의 분류
자료구조의 특징
자료구조는 특정한 상황에 놓인 문제를 해결하는데 특화되어있다.
많은 자료구조를 알게되면, 어떠한 상황에도 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다.
참고자료
https://visualgo.net/en
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
Stack
Stack은 데이터를 순서대로 쌓는 자료구조이며 입력과 출력이 하나의 방향으로 스택의 최상단에서만 이루어지는 제한적 접근에 있다. Stack 자료구조의 정책을 LIFO(Last In First Out), FILO(First In Last Out)이라고 부르기도 한다. Stack에 데이터를 넣는 것을 PUSH라고 하며, 데이터를 꺼내는 것을 POP이라고 한다.
Stack 특징
LIFO(Last In First Out), FILO(First In Last Out)
먼저 들어간 데이터가 나중에 나오는 후입선출의 구조이다. 스택 구조 내에서 특정 데이터를 조회할 수 없으며, 스택의 최상단에서만 데이터를 저장하고 꺼낼 수 있다. 이러한 특징으로 데이터를 저장하거나 검색할 때 데이터를 저장하고 검색하는 프로세스가 매우 빠르다는 것을 알 수 있다.
stack.push(데이터)
| 4 | <- top
| 3 |
| 2 |
| 1 |
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 된다.
스택이 빌 때까지 데이터를 전부 빼낸다.
stack.pop()
| |
| |
| |
| |
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 된다.하나의 입출력 방향, 데이터를 하나씩 넣고 뺄 수 있다.
Stack은 스택 내부에 데이터를 넣을 때도 최상단에 하나씩 넣고, 최상단을에서 하나씩 데이터를 뺄 수 있다.
Stack 실사용 예제
브라우저의 뒤로 가기, 앞으로 가기 기능 구현
- 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관한다.
- 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
- 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때는, Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.
- 마지막으로 현재 페이지를 Prev Stack에 보관한다.
Queue
Queue는 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out), LILO(Last In Last Out)이라고 하며, 입력과 출력의 방향이 각각 고정되어 있다. 데이터를 입력할 때는 큐의 끝에서(tail), 데이터를 출력할 때는 큐의 맨 앞에서(head) 진행되며 Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고 한다. Queue는 데이터가 입력된 순서대로 처리할 때 주로 사용한다.
Queue 특징
FIFO(First In First Out), LILO(Last In Last Out)
Queue는 먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조이다.
예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 자료구조는 데이터를 입력할 때 큐의 맨 끝으로만 입력이 가능하고 데이터를 출력할 때는 큐의 맨 앞으로만 출력이 가능하므로 2개의 입출력 방향을 가지고 있다. 각 처리 시마다 한 개의 데이터를 넣거나 뺄 수 있다.
Queue 실사용 예제
여러 문서를 순서대로 인쇄하는 프린터
- 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 (임시 기억 장치의) Queue에 들어간다.
- 프린터는 인쇄 작업 Queue에 들어온 문서를 들어온 순서대로 인쇄한다.
컴퓨터 장치들 사이에서 데이터를 주고받을 때, 장치들의 속도의 차이, 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용한다. 대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생한다. 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖는다. 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용한다.
