[자료구조] - Stack , Queue

자료구조

여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것

➰ 데이터란?

문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값

데이터 자체만으로는 어떤 정보를 의미하는지를 알기 어렵다.

ex) 나이라는 데이터가 사람의 나이인지 동물의 나이인지 알 수 없음

➡︎ 데이터는 분석하고 정리하여 활용 해야만 의미를 가질 수 있다.

🗂️ 자료구조의 분류

필요에 따라 데이터의 특징을 파악해 체계적으로 저장해 두는 것이 데이터를 활용하는데 있어 유리하다.

상황에 따른 데이터 분류

자료구조

• 무수한 상황에서 데이터를 효율적으로 다룰 방법을 모두 모아둔 것
• 자주 등장하는 자료구조 : Stack, Queue, Tree, Graph

 

 

 

 

 

 

🗂️ 자료구조의 특징

대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는데 특화되어있다.

많은 자료구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다.

---

Stack 과 Queue

리스트 자료구조(선형 자료구조)의 특별한 경우

📍 Stack

Stack
쌓다, 쌓이다, 포개지다

데이터를 순서대로 쌓는 자료구조

➰ 원통을 자료구조 Stack, 구슬을 데이터에 비유하자면,

원통 맨 위에 뚫려있는 구멍으로 들어온 구슬은 들어온 순서대로 쌓이게 되어 가장 상단에는 가장 나중에 넣은 구슬이 위치한다.

때문에 구슬을 빼는 경우 나중에 넣은 구슬이 먼저 빠진다.

 

🁢 Stack의 구조

Stack은 원통에 구슬을 넣어둔 형태와 비슷하다.

이를 통해 Stack의 특징을 알아보면

• 입출력이 하나의 방향, 즉 스택의 최상단에서만 이루어진다.  → 제한적 접근

이런 스택 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부른다.

• PUSH
  • 스택에 데이터를 넣는 것
• POP
  • 데이터를 꺼내는 것

 

🁢 Stack의 특징

1. LIFO (Last In First Out)

후입선출

스택의 최상단에서만 데이터를 저장하고 꺼낼 수 있으므로 스택 구조 내에서 특정 데이터를 조회할 수 없다.

예1) 1, 2, 3, 4를 스택에 차례대로 넣습니다.

stack.push(데이터)
|  4  | <- top
|  3  |
|  2  |
|  1  |
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 스택이 빌 때까지 데이터를 전부 빼냅니다.

stack.pop()
|    |
|    |
|    |
|    |
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 됩니다.

때문에 데이터를 저장하거나 검색할 때 항상 스택의 최상단에서만 행위가 이뤄지며 이에 따라 데이터를 저장하고 검색하는 프로세스가 매우 빠르다.

 

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

스택 자료구조는 가장 최상단에서만 행위가 이루어지므로 데이터를 입력, 출력할 때도 가장 최상단에서 이루어진다.

 

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

스택 내부에 여러 개의 데이터가 쌓여있더라도 입출력은 최상단, 한 곳에서 이루어지기 때문에 한 번에 한 개의 데이터만을 뺄 수 있다.

 

 

🁢 Stack의 실사용 예제

브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 Stack이 활용된다.

스택이 사용되는 순서는 다음과 같다.

1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관
2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옴
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때는, Next Stack의 가장 마지막으로 보관된 페이지를 가져옴
4. 마지막으로 현재 페이지를 Prev Stack에 보관

 

---

📍 Queue

Queue
줄을 서서 기다리다, 대기행렬

데이터를 입력된 순서대로 처리할 때 사용하는 자료구조

➰ 톨게이트를 Queue 자료구조, 자동차를 데이터로 비유한다면,

고속도로에 있는 톨게이트는 자동차가 진입한 순서대로 통과한다.

→ 나중에 진입한 자동차는 먼저 도착한 자동차가 빠져나가기 전까지는 톨게이트를 빠져나갈 수 없다.

 

🚥 Queue의 구조

스택과 반대되는 개념으로, FIFO(First In First Out) 혹은 LILO(Last In Last Out)의 특징이 있다.

• 데이터를 입력할 시에는 큐의 끝에서(tail) 진행
  • enqueue : 데이터를 넣는 것
• 데이터를 출력할 시에는 큐의 맨 앞에서(head) 진행
  • dequeue : 데이터를 꺼내는 것

 

🚥 Queue의 특징

1. FIFO (First In First Out)

선입선출 구조

예1) 1, 2, 3, 4를 큐에 차례대로 넣습니다.

						queue.enqueue(데이터)
출력 방향(head) 	<---------------------------< 입력 방향(tail)
					1 <- 2 <- 3 <- 4
				<---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 큐가 빌 때까지 데이터를 전부 빼냅니다.

						queue.dequeue(데이터)
출력 방향(head)	 <---------------------------< 입력 방향(tail)

				 <---------------------------<
1, 2, 3, 4
제일 첫 번째 있는 데이터부터 차례대로 나오게 됩니다.

 

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

Queue 자료구조는 데이터의 입력, 출력 방향이 다르다.

큐는 데이터를 입력할 때 큐의 맨 끝에서만 가능하고, 데이터를 출력할 때는 큐의 맨 앞으로만 가능하다. (입 출력 방향이 고정되어 있음)

→ 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없다.

 

 

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

Queue 자료구조는 두 개의 입출력 방향을 가진다.

큐 내부에 여러 데이터가 쌓여 있더라도, 데이터가 입/출력 되는 방향이 다르므로 맨 앞에서 한 번에 한 개의 데이터를 뺄 수 있다.

 

 

🚥 Queue의 실사용 예제

Queue는 컴퓨터에서 광범위하게 활용된다.

• 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄하는 경우
  1. 출력 버튼을 누르면 해당 문서는 인쇄 작업(임시 기억 장치의) Queue에 들어간다.
  2. 프린터는 인쇄 작업 Queue에 들어온 문서를 들어온 순서대로 인쇄한다.

컴퓨터 장치들 사이에서 데이터를 주고 받을때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용한다. →이것을 통틀어 버퍼(buffer)라고 한다.

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

➡︎ 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용

 

📍 컴퓨터와 프린터 사이의 데이터 통신

• 일반적으로 프린터는 속도가 느리다.
• CPU는 프린터와 비교했을때, 데이터를 처리하는 속도가 빠르다.

→ CPU는 빠른 속도로 인쇄에 필요한 데이터를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.

• 프린터는 인쇄 작업 Queue에서 데이터를 받아 들어온 순서대로 일정한 속도로 인쇄한다.

동영상 스트리밍 앱을 통해 동영상을 시청하는 경우에도, 동영상을 정상적으로 재생하기 위해 Queue에 모아두었다가 동영상을 재생하기에 충분한 양의 데이터가 모이면 동영상을 재생 하기도 한다.