1. Stack
Stack 이란?
- 데이터를 순서대로 쌓는 자료구조.
- 예시 : 원통 안에 위에서부터 구슬을 넣고, 다시 위에서부터 구슬을 빼는 것.
Stack 자료구조의 특징
- 데이터의 입출력이 스택의 최상단에서만 이루어지는 제한적 접근 구조임
- LIFO(Last In First Out), FILO(First In Last Out) 방식임.(선입후출, 후입선출)
- Stack 에 데이터를 넣는 것은 ‘push’, 꺼내는 것은 ‘pop’
🌐️ (참고) 위키피디아 정의
스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 **LIFO 구조**라고 한다.
Stack 의 특징
1. LIFO(Last In First Out)
- 후입선출 구조.
- 이 특성때문에 리스트와 달리 스택 내에서 특정 데이터를 조회할 수 없으며, 스택의 최상단에서만 데이터를 저장하고 꺼낼 수 있음 ⇒ 데이터 저장, 검색 시 항상 스택의 최상단에서만 행위가 이루어지기 때문에 프로세스가 매우 빠름!
2. 단일 입출력 방향
- 스택의 최상단으로만 데이터의 입출력이 가능함.
3. 데이터는 하나씩 입출력 가능
- 데이터 입출력 경로가 최상단 한군데 뿐이어서, 한번에 하나씩만 데이터를 넣고 뺄 수 있음.
Stack 의 실사용 예제
- 대표적으로 브라우저의 뒤로가기, 앞으로 가기 기능이 있음
- 브라우저에서 Stack 자료구조가 사용될 때의 순서 (Prev Stack - 현재 페이지 - Next Stack 이 있음)
-
새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack 에 보관함
-
뒤로가기 → 현재 페이지를 Next Stack에 보관, Prev Stack 에 가장 나중에 보관된 페이지를 현재 페이지로 불러옴
-
앞으로가기 → Next Stack의 가장 마지막으로 보관된 페이지를 현재 페이지로 가져오고 현재페이지를 Prev Stack에 보관함
-
2. Queue
Queue 란?
- 일렬로 늘어선 줄과 같이, 데이터가 선입선출 방식으로 입출력되는 구조
- 예시 : 티켓을 사러 줄을 선 사람들이 먼저 온 순서대로 빠지는 것, 톨게이트에 먼저 진입한 자동차가 먼저 통과하는 것 등
Queue 자료구조의 특징
- 입력과 출력의 방향이 고정되어 있으며, 데이터를 입력(enqueue)할 경우에는 큐의 끝(tail)에서, 데이터를 출력(dequeue)할때는 큐의 맨 앞(head)에서 에서 진행됨.
- FIFO(First In First Out) 혹은 LILO(Last In Last Out) 방식임 (선입선출, 후입후출)
- Queue 에 데이터를 넣는 것은 ‘enqueue’, 꺼내는 것은 ‘dequeue’
🌐️ (참고) 위키피디아 정의
스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.
Queue 의 특징
1. FIFO (First In First Out)
- 먼저 들어간 데이터가 제일 처음에 나오는 선입선출 구조.
- tail → head 방향으로 enqueue 되고, head 에 있는 데이터부터 dequeue 됨
2. 두개의 입출력 방향이 잇음
- 데이터를 입력할 때는 큐의 맨 끝(tail)으로만 입력이 가능하며 데이터를 출력할 때는 큐의 맨 앞(head)으로만 출력이 가능
- 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없음
3. 데이터는 하나씩 입출력 가능
- 큐 내부에 데이터가 쌓여있어도 입력시에는 뒤에서, 출력시에는 맨 앞에서 한번에 하나의 데이터만을 입출력 가능함
Queue의 실사용 예제
- 프린터에서 문서를 인쇄하는 경우
- 문서 출력 버튼을 누르면 해당 문서는 인쇄작업 (임시 기억장치의) Queue 에 들어감.
- 프린터는 인쇄 작업 Queue 에 들어온 문서를 먼저 들어온 순서대로 인쇄함.
🌐️ (참고) 위키피디아 정의
기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.
나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.
프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.
Stack 과 Queue 의 차이점 한눈 정리 이미지
Buffer
- 컴퓨터 장치들 사이에서 데이터(data)를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이
나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용하며, 이것을 buffer 라고 함. - 다른 말로는 속도차가 큰 두 대상이 입출력을 수행할 때 효율성을 위해 사용하는 임시 저장공간
Buffer 의 예시
-
유튜브를 예로 들자면, 영상 재생 시 아직 보지 않은 부분의 회색 재생바가 늘어나는 것이 Queue 에 영상 데이터를 모아두는 것임.
-
데이터를 다운받는 것이 CPU의 처리 속도보다 느리기 때문에, CPU 가 다른 작업을 처리할 동안 미리 Queue 에 영상 데이터를 다운받아놓고, 데이터가 어느정도 쌓이면 CPU 가 재생을 시작함.
-
이때 재생 중 재생 속도보다 데이터의 다운로드 속도가 느리면 영상이 끊기는 buffering이 발생함.
-
프린터를 예로 들자면, 프린터가 인쇄하는 속도보다 CPU 가 빠르기 때문에, CPU 는 빠른 속도로 인쇄에 필요한 데이터를 만든 다음 인쇄작업 Queue 에 저장하고 다른 작업을 수행함.
-
프린터는 인쇄작업 Queue 에서 데이터를 받아, 들어온 순서대로 일정한 속도로 인쇄함.
🌐️ (참고) 위키피디아 정의
컴퓨팅에서 버퍼(buffer, 문화어: 완충기억기)는 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역이다. 버퍼링(buffering)이란 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 말한다. 다른 말로 '큐(Queue)'라고도 표현한다.
버퍼는 컴퓨터 안의 프로세스 사이에서 데이터를 이동시킬 때 사용된다. 보통 데이터는 키보드와 같은 입력 장치로부터 받거나 프린터와 같은 출력 장치로 내보낼 때 버퍼 안에 저장된다. 이는 전자 통신의 버퍼와 비유할 수 있다. 버퍼는 하드웨어나 소프트웨어에 추가될 수 있지만 버퍼는 상당수가 소프트웨어에 추가된다. 버퍼는 보통 속도가 계속 바뀔 수 있으므로 데이터 수신, 처리 속도에 차이가 있다. (예: 프린터 스풀러)
버퍼는 네트워크 상에서 자료를 주고 받을 때나 스피커에 소리를 재생할 때, 또는 디스크 드라이브와 같은 하드웨어의 입출력을 결합하는 데에 자주 이용된다. 버퍼는 또한 순서대로 데이터를 출력하는 FIFO 방식에서 보통 사용된다.
🔗️ (참고) [개념정리] 버퍼(BUFFER)란? 버퍼 개념
