[자료구조] stack, queue

자료구조 크게 봤을때 4가지

1. 스택과 큐
실생활에서도 흔히 볼 수 있는 자료구조, 가장 간단한 자료구조이다.
스택과 큐는 서로 비슷하면서도 다른 쌍둥이 같은 느낌이다.
스택과 큐는 활용도가 가장 높다.

2. 연결 리스트와 해시 테이블
배열과 같이 여러 데이터를 선형적으로 담을 수 있는 연결 리스트
배열과 어떤 부분이 다른지 생각하면서 공부!!
해시 테이블은 자료구조 중에서 가장 어렵다.
해시 테이블의 장점을 알게되면 해시 테이블을 남용할 것이다.

3. 그래프, 트리, 이진 탐색 트리
그래프, 트리, 이진 탐색 트리는 모두 그래프의 형태를 가지는 자료 구조이다.
그래프의 형태이기 때문에, 수학적인 부분에서만 사용된다. 
실생활의 무수히 많은 문제를 해결하는데 적용할 수 있다.

4. 시간 복잡
프리코스에서 마지막에 배웠던 시간 복잡도!! 알고리즘을 표현하는 도구이다.
자료구조와 자료구조에서 발생하는 특정 작업들을 작성하고 난뒤,
이것이 어떤 시간적 효율을 가지는지 알 수 있다.

---

1. 스택(Stack)

: '쌓다'라는 뜻으로, 쌓여있는 접시 더미와 같이 동작한다고 한다.

새로운 접시가 쌓일 때 맨 위에서 쌓이고, 접시를 가져갈 때도 맨 위에서 가지고 간다.

후입선출 (LIFO : Last in, First out) : 나중에 집어넣은 데이터가 먼저 나온다.

 

스택은 브라우저 히스토리(이전 페이지, 다음 페이지)

또는 ctrl+z로 이전 작업을 취소하는 등의 동작에 쓰이는 자료구조이다.

stack overflow 나 stack underflow를 많이 들어봤을 것이다.

stack overflow는 유명한 해외 프로그래밍 커뮤니티 사이트이기도 하다.

하지만 그것에 원래 뜻은 각각 주어진 스택 메모리보다 데이터를 더 넣었거나,

스택이 메모리가 비어있는데 거기서 데이터를 꺼내려고 했을 때 발생하는 대표적인 에러라고 한다.

 

 

속성) 

• top : Stack 맨 위의 item (또는 Stack의 마지막 요소)

메소드)

• push(item) : Stack 맨 위에 item을 삽입한다.

• pop() : Stack 맨 위의 item을 제거하고 및 그 item을 반환한다.

• peek() : Stack 맨 나중에 집어넣은 데이터를 확인한다.

• contains() : 해당 item Stack에 존재하는지 확인한다.

• size(): 현재 Stack에 있는 item의 총 개수를 반환한다.

• isEmpty() : Stack이 비어있는지 확인

---

2. 큐(Queue)

: "대기 행렬" or "줄을 서서 기다리다" 라는 뜻으로, 맛집에서 줄서서 기다리는것과 같이 작동한다.

새로 온 사람은 줄 맨 뒤에 서고, 제일 앞 사람은 음식점으로 들어가므로 줄에서 빠져나갑니다.

이렇게 큐(queue)는 뒤에서 들어가고 (enqueue) 앞에서 빠지는 (dequeue) 구조이다.

선입선출 (FIFO : First in, First out) : 먼저 들어온 데이터가 먼저 나가게 된다. (편의점식 진열)

큐(Queue)는 레스토랑 앱, 예매 앱, 우버 앱 등에서 큐를 주요한 자료구조로 사용할 것이다.

 

속성)

• first : Queue맨 앞의 item

메소드)

• enqueue(item) : Queue에 item을 추가한다.

• dequeue() : Queue 맨 앞의 item을 제거하고 및 그 item을 반환한다.

• peek() : 제일 앞의 데이터를 알 수 있는 즉, front 값

• contains() : 해당 item이 Queue에 존재하는지 확인한다.

• size() : 현재 Queue에 있는 item의 총 개수를 반환한다.

• empty() : Queue가 비어있는지 확인

 

추가 개념 요약

2-1. 우선 순위 Queue

dequeue를 실행하면 우선 순위가 높은 값이 먼저 dequeue된다.

// 조건 priority 가 높을 수록 우선 순위가 높다.
const queue = new PriorityQueue();

queue.enqueue({ value: 'A', priority: 5 })
queue.enqueue({ value: 'B', priority: 2 })
queue.enqueue({ value: 'C', priority: 1 })
queue.enqueue({ value: 'D', priority: 4 })
queue.enqueue({ value: 'E', priority: 3 })
// dequeue 5 times...

 

원래대로라면 enqueue된 순서인 A-B-C-D-E 순으로 출력될텐데
우선 순위 queue에서는 우선순위가 높은 것이 먼저나온다. 따라서 A-D-E-B-C 순으로 출력된다.

 

Q. 우선 순위 QUEUE를 구현한다고 하면 우선순위를 어떻게 계산할 수 있을까?
A. 우선순위는 정렬sort할 수 있는 값으로 두어야한다.
ex) 우선순위를 숫자로 설정하고 조건문을, max를 이용해서 최대값인 것을 dequeue한다.

 

관련개념 "힙트리" : 최대값 최소값을 효율적으로 찾을 수 있도록 고안된 자료구조

 

2-2. 원형 Queue

원형 QUEUE는 동그랗게 생겨서 front와 rear가 붙어있는 구조.

원형queue를 쓰는 이유: 재사용

QUEUE를 배열로 구현했을 때, 삽입 삭제 연산이 이루어지면서 front와 rear의 위치가 뒤로 점점 밀려나고

앞 쪽에는 데이터가 들어올 수 있는 공간이 있지만 rear가 배열 인덱스의 가장 마지막을 가리키고 있다면,

enqueue했을 때 실제로 큐에 공간이 있음에도 불구하고 삽입할 수 없는 문제가 생기게 된다.
즉, 삭제가 이루어졌을 때 나머지 데이터가 앞쪽으로 이동하지 않으면 공간의 낭비가 생기게 된다.
이것이 큐를 배열로 구현했을 때 생기는 문제점이며 환형배열을 통해 해결한다.