Stack & Queue

준성·2023년 7월 31일
0
post-thumbnail

자료구조

자료구조는 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.

여기에서 데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다. 이 데이터들이 중구난방으로 있다면 한눈에 알아보기 힘들 수 있다.

이처럼 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다고 생각한다.

정해진 규칙없이 저장하는 것 보다 체계적으로 정리하여 저장해 두는 게, 데이터를 활용하는 데 있어 훨씬 유리하다

자료구조의 분류

데이터를 효율적으로 다룰 방법을 모두 모아, 자료구조라는 이름을 붙였다.

Stack

Stack의 정의

쌓다, 포개지다 라는 뜻을 가지고 있다. 이 자료구조는 말 그대로 데이터를 순서대로 쌓는 구조이다.

Stack의 구조

자료구조의 스택은 입력과 출력이 하나의 방향, 스택의 최상단에서만 이루어지는 제한적 접근에 있다. 이런 스택의 자료구조 정책을 LIFO (Last In First Out)이라고 부른다

스택에 데이터를 넣는 것은 PUSH 데이터를 꺼내는 것을 POP 이라고 한다.

Stack의 특징

1. LIFO(Last In First Out)

먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조로 되어있다. 이러한 특성으로 스택 구조 내에서 특정 데이터를 조회할 수 없으며 최상단에서만 저장하고 꺼낼 수 있다.

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

스택 자료구조는 데이터를 넣고 뺄 수 있는 곳이 스택의 가장 최상단이다. 즉 입구가 하나다.

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

스택에 여러 번 데이터를 넣어 스택 내부에 여러 개 쌓여 있어도 뺄 때는 하나씩 뺄 수 있다.

Stack의 실사용 예제

실사용에서 제일 많이 사용하는 것은 브라우저의 뒤로가기 이다 또는 APP들의 되돌리기도 스택의 실사용이다. 데이터가 메인페이지 부터 시작해 천천히 쌓여있는걸

메인페이지 → 서브페이지 → 마이페이지 이런순으로 진행되었을때 데이터들은 순서대로 쌓이며 뒤로가기를 진행 했을 때, 마이페이지를 빼면 메인페이지 → 서브페이지

이렇게 남기에 스택을 사용하는 예제가 되겠다.

Queue

큐(Queue)는 줄을 서서 기다리다라는 뜻을 가지고 있다. 일반적으로 고속도로 톨게이트에 진입한 순서대로 지나가는 것을 생각하면 쉽다.

Queue의 구조

큐는 스택과 반대로 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out)의 특징을 가지고 있다.

이 자료구조는 입력의 방향과 출력의 방향이 각각 고정되어있으며, 데이터를 입력할 시에는 큐의 끝에서, 데이터를 출력할 때는 큐의 맨 앞에서 진행된다.

Queue에 데이터를 넣는 것을 enqueue 데이터를 꺼내는 것을 dequeue 라고 한다.

Queue의 특징

1. FIFO(First In First Out)

먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조로 되어있다.

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

큐라는 자료구조는 데이터의 입력, 출력 방향이 다르다. 데이터를 입력할 때는 큐의 맨 끝으로 입력이 가능하고 데이터를 출력할 때는 큐의 맨 앞으로만 출력이 가능하다.

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

스택과 같이 데이터는 하나씩 넣고 뺄 수 가있다.

Queue의 실사용 예제

컴퓨터에서 광범위하게 활용되는데, 대표적으로 컴퓨터에서 인쇄를 진행할 때 사용된다.

문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 Queue에 들어간다. 프린터는 인쇄 작업 Queue에 들어온 문서를 들어온 순서대로 인쇄한다.

위 예시처럼 장치들 사이에서 데이터를 주고 받을 때, 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용한다.

이것을 버퍼(Buffer) 라고 하는데 우리가 아는 버퍼링(Buffering) 의 개념이 된다.

대부분의 컴퓨터 장치에 발생하는 이벤트는 파동 그래프와 같이 불규칙적이다. 이에 반해 CPU와 같이 발생한 이벤트는 일정한 처리 속도를 갖는다.

불규칙적으로 발생한 이벤트를 처리하기 위해 버퍼를 사용한다. 컴퓨터 와 프린터 사이의 데이터 통신을 정리하면 다음과 같다.

  1. 일반적으로 프린터는 속도가 느리다
  2. CPU는 프린터와 비교하여, 데이터를 처리하는 속도가 빠르다
  3. CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 다음, 인쇄 작업 큐에 저장하고 다른 작업을 수행한다
  4. 프린터는 인쇄 작업 큐에서 데이터를 받아 들어온 순서대로 일정한 속도로 인쇄한다.

유튜브와 같은 동영상 스트리밍 앱을 통해 동영상을 시청할 때, 다운로드된 데이터가 영상을 재생하기에 충분하지 않은 경우 이때 동영상을 정상적으로 재생하기 위해

큐에 모아 두었다가 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생한다.

profile
코드를 그리다.

1개의 댓글

comment-user-thumbnail
2023년 7월 31일

감사합니다. 이런 정보를 나눠주셔서 좋아요.

답글 달기