스택 Stack & 큐 Queue

---

ADT (Abstract Data Type)

• 추상자료형
• 개념적으로 어떤 동작이 있는지만 정의한다.
• 구현에 대해서는 다루지 않는다. 

DS (Data Structure)

• 자료구조
• ADT에서 정의된 동작을 실제로 구현한 것을 의미한다.

---

스택 Stack

스택은 가장 최근에 넣은 것을 가장 먼저 뺄 수 있는 데이터 구조로 내부 프로세스 구조 함수의 동작 방식으로 사용된다. 

LIFO (Last In First Out) 형태로 데이터를 저장하는 구조

 

1. 스택 주요 동작

• push : 아이템을 집어넣음/쌓음 (Python list의 append 메소드와 같다)
• pop : 아이템을 빼냄 (Python list의 pop 기능과 같다)
• peek : 최상단의 아이템을 알려줌

2. 스택 동작 방식

동작	결과
push(1)	1
push(2)	2 1
push(3)	3 2 1
pop()	2 1
peek() = 2	2 1
pop()	1
push(4)	4 1

 

3. 장단점

• 장점
  • 구조가 단순하고, 구현이 쉽다.
  • 데이터 저장 및 불러오는 속도가 빠르다.
• 단점
  • 데이터 최대 갯수를 사전에 지정해줘야한다. (Python 재귀함수는 1,000번 까지 가능)
  • 저장 공간 낭비가 발생할 수 있다.

단점이 상당히 크기 때문에 보통 배열로 대체하여 사용한다고 한다.

 

4. 스택 사용 사례 

stack memory

- 스택이라는 자료구조를 이용해서 만들어진 스택 메모리 영역

 

stack frame

- 함수가 호출될 때마다 스택 프레임이 스택 메모리에 쌓이고

- 함수가 사라지면 그에 해당하는 함수의 스택 프레임이 메모리 영역에서 사라진다.

---

큐 Queue

• FIFO (First In First Out) 형태로 데이터를 저장하는 구조

1. 큐 주요 동작

• enqueue : 아이템을 집어넣음
• dequeue : 아이템을 빼냄
• peek : 최상단의 아이템을 알려줌
  
  

2. 큐 동작 방식

enqueue(1)	enqueue(2)	enqueue(3)	dequeue()	dequeue()	peek() = 3	enqueue(4)	dequeue()
1	2 1	3 2 1	3 2	3	3	4 3	4

 

3. 큐 사용 사례 

producer architecture

- 프로듀서는 계속해서 아이템을 생성해서 큐에 넣으면

consumer architecture

- 컨슈머는 그때마다 차례대로 아이템을 가져가서 처리한다.

 

4. 기술 문서에서 큐를 만났을 때

- 항상 FIFO를 의미하지는 않는다.

- 큐 중에서 순서가 아닌 우선순위에 의한 큐도 존재한다. 그래서 큐라고 해서 FIFO인 것은 아니다.

---

 

스택 / 큐 관련 에러와 해결 방법

StackOverflow Error

스택 메모리 공간을 다 사용했을 때 발생하는 에러

재귀함수 (recursive function)에서 탈출하지 못해서 발생하는 현상이 다반수이다.

def recur_fibo(n):
  if n <= 1: # 탈출 조건
    return n 
  else:
    return recur_fibo(n-1) + recur_fibo(n-2)

 

재귀함수는 함수 내에서 자기 자신을 사용하는 함수를 의미한다. 

위 코드에서는 recur_fibo 함수가 else return에서도 자기 본인 함수를 사용하므로 재귀함수인 것을 확인할 수 있다. 

 

근데 여기서 만약 if에 해당하는 탈출 조건이 없다면 스택 메모리 공간을 다 차지하기 때문에 에러가 발생할 수 있다는 점이다.

그래서 꼭 탈출 조건의 여부와 정확성을 확인해야 한다.

OutofMemory Error

Java에서 힙(heap) 메모리를 다 썼을 때 발생

 

ex)

큐에 데이터를 consume 해야 하는데 안 하거나, consume 속도가 느려서 계속 쌓이기만 했을 때 발생

 

해결 방법 : 큐의 사이즈를 고정한다.

 

그러면 큐가 다 찼는데 아이템을 넣으려고 한다면 어떻게 할 것인가?

• 예외 (exception) 던지기
  •  문제가 있다는 것을 알림
• 특별한 값 (null or false) 반환
  • 실패하였다는 것을 알림
• (밀어 넣으려고 했던 스레드를 큐에 공간이 생길 때까지 / 성공할 때까지) 영원히 스레드 블락 (block)
  • 블락 : 공간이 생길 때까지 대기한다.
  • 하지만 이 경우, 스레드가 블락이 되었기 때문에 그 이후에 작업을 진행할 수 없기에 스레드 낭비 발생 가능
• 제한된 시간만 블락되고 그래도 안되면 포기

위 4가지를 해결하기 위해 존재하는 클래스 중 하나가 LinkedBlockingQueue이다.

---

LinkedBlockingQueue

- Java의 java.util.concurrent 패키지에서 제공하는 큐(Queue) 구현 클래스 중 하나로, 멀티스레드 환경에서 안전하게 사용할 수 있는 블로킹 큐이다.

- 어떻게 동작했으면 하는지에 따라 다른 함수 사용하니까 잘 확인해서 사용하면 좋을 듯 싶다.

출처 : https://devopedia.org/queue-data-structure