자료구조
Stack, Queue 자료구조 이해하기
: Stack, Queue 자료구조를 배열로 대체해서 만들어보기
자료구조란?
자료구조란 여러 데이터들의 묶음을 어떻게 저정하고, 사용할 것인지를 정의한 것이다.
자료, data
자료, data는 자료 구조에서 가장 중요한 것으로 문자, 숫자, 소리, 그림 등 실생활에서 구성하고 있는 것들을 자료(data)라고 할 수 있다.
수많은 자료들을 분석하고, 정리한 뒤 활용할 수 있어야 의미가 있을 것이다.
형태가 다른 자료들의 특징을 잘 파악, 분석해서 정리하고 활용할 수 있도록 하는 방안들을 자료구조라고 부를 수 있다.
자료구조 종류
자료구조에는 크게 단순 구조, 선형 구조, 비선형 구조, 파일 구조가 있다.
이 안에서 또 세부적으로 나뉘게되는데 한 번 정리해보려고 한다.자료구조
1. 단순구조
1-1. 2진수
1-2. 정수 / 실수
1-3. 문자 / 문자열2. 선형구조
2-1. 리스트 (배열)
2-2. 연결 리스트
a. 단순 연결리스트
b. 이중 연결리스트
c. 원형 연결리스트
2-3. 덱
2-4. 스택
2-5. 큐3. 비선형구조
3-1. 트리
a. 일반 트리
b. 이진 트리
3-2. 그래프
a. 방향 그래프
b. 무방향 그래프4. 파일구조
4-1. 순차 파일
4-2. 색인 파일
4-3. 직접 파일
Stack & Queue & Array
Stack, Queue 단어를 들으면 뭘까 싶지만 배열(Array)도 자료 구조 중 하나이다.
자료들을 순서대로 쭉 나열해서 저장한 배열이라는 자료구조의 특징, 활용을 할 수 있기 때문에 Stack, Queue도 조금은 쉽게 다가갈 수 있을 것 같다.
- 자료 구조들이 어떠한 특징을 가졌는지?
- 자료구조를 어디에 적용하면 좋은지?
- 다른 자료구조들과 다른 점은 무엇일지?
위의 리스트들을 이해하기 위해 자료구조 내부를 직접 구현해서 어떤 방식으로 동작하는지를 배열(Array)과 같이 미리 정의된 데이터 타입을 이용해서 공부해 볼 것이다.
Stack
Stack이라는 단어의 뜻에는 '쌓다', '쌓이다', '포개지다'라는 뜻이 있다.
Stack은 단어의 뜻 그대로 자료(data)를 쌓는 자료구조이다!재귀함수를 사용했던 것을 생각해보면, Call Stack을 사용해서 Stack에 함수들이 쌓인다는 것을 알 수 있다.
쉽게 생각해보면 막다른 골목길에 차들이 7개가 들어와서 꼼짝도 못하는 상황일 때, 맨 처음 들어온 차가 나가려면 어떻게 해야 막다른 골목을 빠져나갈 수 있을까?
맨 마지막에 들어온 7번째 차가 먼저 골목을 나가고, 6번째로 들어온 차가 골목을 나가고, 5번째, 4번째, 3번째, 2번째, 1번째 순으로 골목을 후진해서 나가야지 첫 번째가 골목을 빠져나갈 수 있다.
즉, 가장 먼저 들어간 자동차가 가장 나중에 나올 수 있다.
이는 가장 나중에 들어간 자동차가 가장 먼저 나올 수 있다는 말도 된다.
Stack 자료구조의 특성은 입력/출력 입구가 1개인 제한적 접근이 있다.
Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 한다.
Stack이 사용되는 예
브라우저의 뒤로 가지, 앞으로 가기 기능을 구현할 때 Stack 자료 구조가 활용되는 것을 살펴볼 수 있다.
- 새로운 페이지를 접속하게 되면 현재 페이지를 이전 페이지, Prev Stack에 보관한다.
- 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때는 현재 페이지를 앞으로 가기 Next Stack에 보관한다.
그리고 이전 페이지 Prev Stack에 있던 가장 나중에 보관된 페이지를 현재 페이지로 다시 가져온다.- 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 할 때는 Next Stack에 가장 마지막으로 보관되어 있던 페이지를 가져온다.
- 마지막으로 현제 페이지를 Prev Stack에 다시 보관한다.
- 아예 새로운 탭을 여는 경우에는 앞으로 가기나 이전 페이지로 가기를 눌러도 페이지가 존재하지 않는 것도 잘 생각해둬야 된다.
Queue
Queue는 줄을 서서 기다리다, 대기 행렬 이라는 뜻을 가지고 있다.
Queue는 Stack과는 반대되는 개념으로 먼저 들어간 자료(data)가 가장 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)의 특성을 가지고 있는 자료구조이다.
예를 들어서 마트에서 장을 보고, 계산대에 5명이 계산을 하기 위해 줄을 섰을 때, 맨 처음 서있던 사람의 계산이 끝나야만 두번째 사람이 계산을 할 수 잇다. 마찬가지로 세번째, 네번째, 다섯번째 사람들이 앞 사람의 작업이 다 끝나야만 계산이 가능하다.
마트 계산대를 Queue 자료구조, 자동차는 자료(data)로 비유 할 수 있다.
가장 먼저 줄을 서 있던 사람이 가장 먼저 마트를 빠져나올 수 있다.
이는 가장 나중에 줄을 선 고객이 앞 사람들의 계산이 모두 다 끝나기 전에는 마트를 빠져나갈 수 없다는 말과 같다.Queue는 자료(data)가 입력된 순서대로 처리해야 할 필요가 있는 상황에서 사용된다.
Queue가 사용되는 예
Queue 자료 구조는 컴퓨터에서도 광범위하게 활용되는데 그중 컴퓨터와 연결된 프린터에서 문서를 인쇄할 때를 생각해보려고 한다.
- 사용자가 문서를 작성한 뒤 출력버튼을 누르면 해당 문서를 인쇄 작업, 임시 기억장치 Queue에 들어간다.
- 프린터는 인쇄 작업 Queue로 들어온 순서대로 문서를 인쇄한다.
컴퓨터(출력 버튼) --> Queue(임시 기억장치)에 출력 버튼을 눌렀을 때 해당하는 영역의 문서들이 하나씩 들어옴 --> 들어온 순서부터 인쇄 작업
들어온 순서대로 문서가 출력된다.
컴퓨터 장치들 사이에서 자료(data)를 주고 받을 때 각 장치들 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위한 임시 기억 장치로 Queue가 사용되는데 이를 버퍼(buffer)라고 한다.
아래에서 버퍼링(buffering)의 개념을 알아보도록 할 것이다.
대부분의 컴퓨터 장치에서 발생하는 이벤트는 아래 오른쪽 파동 그래프와 같이 시간에 따라 불규칙적으로 발생하게 된다. 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖는데, 이 둘 사이의 속도 차이를 버퍼(buffer)를 사용해서 해결 할 수 있다.
위의 그림을 보고 컴퓨터, 프린터 사이의 자료(data)의 통신을 살펴보면,
프린터는 보통 속도가 느리고, 상대적으로 CPU는 속도가 빠르기 때문에
CPU는 빠른 속도로 인쇄 자료(data)를 만들고, 그 다음 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.프린터는 인쇄 작업 Queue에서 자료(data)를 가져가서 일정한 속도로 인쇄한다.
