Stack & Queue

현채은·2023년 5월 10일

알고리즘 자료구조

📑 Stack이란?

쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있음
데이터(data)를 순서대로 쌓는 자료구조
일상생활 예시
- 동그란 원통에 차례대로 구슬을 넣는 경우, 가장 위에있는 구슬을 먼저 뺼 수 있음

📑 Stack의 구조

원통을 자료구조 Stack, 구슬을 데이터(data)로 비유할 수 있음
자료구조 Stack의 특징은 입출력이 하나의 방향 (최상단)에서만 이루어지는 제한적 접근에 있음
이런 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out) 이라고 부름
Stack에 데이터를 넣는 것을 'PUSH' , 데이터를 꺼내는 것을 'POP'이라고 함

📑 Stack의 특징

1. LIFO(Last In First Out)

가장 나중에 들어간 데이터가 첫번째로 나온다 - 먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조로 되어있음

이러한 특성으로 인해 스택 구조 내에서 특정데이터를 조회할 수 X
스택 최상단에서만 데이터를 저장하고 꺼낼 수 있음
데이터를 저장, 검색할 때 항상 최상단에서만 행위가 이루어지며 이에 따라 데이터를 저장하고 검색하는 프로세스가 매우 빠름

2. 하나의 입출력 방향을 가지고 있다.

stack 자료구조는 데이터를 빼고 넣는 곳이 스택의 가장 최 상단, 한군데 - 데이터를 넣을 때에도 스택의 가장 최상단으로 넣고(입력), 뺄때도 최상단에서 뺌(출력)

3. 데이터는 하나씩 넣고 뺄 수 있음

스택에 한개씩 여러번 데이터를 넣어 스택 내부에 데이터가 여러개 쌓여 있다고 하더라도, 데이터를 뺄 때에는 스택의 가장 최상단에서 한번에 한 개의 데이터만을 뺄 수 있음

📑 Stack의 실사용 예제

컴퓨터 자료구조 : 브라우저의 뒤로가기, 앞으로가기 기능 구현
브라우저 자료구조 Stack이 사용될 때는 다음과 같은 순서를 거침
①. 새로운 페이지 접속시, 현재 페이지를 Prev Stack에 보관
②. 뒤로가기 버튼을 눌러 이전페이지로 돌아갈 때는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옴
③. 앞으로가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는 Next Stack의 가장 마지막으로 보관된 페이지를 가져옴
④. 마지막으로 현재 페이지를 Prev Stack에 보관

📚 Queue 란?

큐(Queue)는 줄을 서서 기다리다, 대기행렬이라는 뜻을 가지고 있음
휴지심처럼 생긴 모양
ex. 명절 톨게이트에는 진입한 순서대로 통행료를 내고 톨게이트 통과
- 톨게이트 : Queue , 자동차 : 데이터(data)
- 가장 먼저 진입한 자동차가 가장 먼저 톨게이트를 통화
  ➡️ 가장 나중에 진입한 자동차는 먼저 도착한 자동차가 모두 빠져나가기 전까지 나갈 수 없음

📚 Queue의 구조

Stack과는 반대되는 개념으로 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)을 특징으로 가지고 있음
티켓을 사려고 줄을 서는 모습과 흡사
입출력 방향이 각각 고정되어 있음
- 입력 : 큐의 끝(tail) ➡️ enqueue
- 출력 : 큐의 맨 앞(head) ➡️ dequeue
데이터가 입력된 순서대로 처리할 때 주로 사용

📚 Queue의 특징

1. FIFO (First In First Out)

먼저 들어간 데이터가 제일 처음에 나오는 선입선출 구조

2. 두 개의 입출력 방향을 가지고 있음

- 데이터의 입력은 큐의 맨 끝 (tail)으로만 입력 - 데이터의 출력은 큐의 맨 앞 (head)으로만 출력 - 큐는 데이터를 입출력 하는 곳이 각각 정해져 있음 - 입출력이 같다면 Queue의 자료구조라고 볼 수 없음

3. 데이터는 하나씩 넣고 뺄 수 있음

큐에 한 개씩 여러번 데이터를 넣어 큐 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때에는 큐의 맨 앞에서 한 번에 한 개씩 데이터를 뺄 수 있다.

📚 Queue의 실사용예제

컴퓨터에서도 광범위하게 이용되는 Queue

컴퓨터와 연결된 프린터에서 여러문서를 순서대로 입력하려면 ?
1. 우리가 문서를 작성하고 출력버튼을 누르면 해당 문서는 인쇄작업 Queue에 들어감
2. 프린터는 인쇄 작업 Queue에 들어온 순서대로 인쇄
- 컴퓨터(출력버튼) ➡️ (임시기억장치의) Queue에 하나씩 들어옴 ➡️ Queue에 들어온 문서를 들어온 순서대로 인쇄
위 예시처럼 컴퓨터 장치들 사이에서 데이터를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시기억장치의 자료구조로 Queue를 사용
이것을 통틀어 버퍼(Buffer)라고 함
아래의 이미지는 버터링(Buffering)의 개념을 보여줌
- 대부분의 컴퓨터 잘치에서 발생하는 이벤트 ➡️ 파동 그래프와같이 불규칙적
- 이에비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리속도를 가짐
  ➡️ 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용
  
  컴퓨터와 프린터 사이의 데이터(data)통신을 정리하면 다음과 같음
일반적으로 프린터는 속도가 느립니다.
CPU는 프린터와 비교했을 때 데이터를 처리하는 속도가 빠름
CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 후, 인쇄작업 Queue에 저장하고 다른 작업 수행
프린터는 인쇄작업 Queue에서 데이터를 받아온 순서대로 일정한 속도로 인쇄