개발자가 되고 싶었던 주니어 hobby 개발자 입니다.

1 분 소요

스택(Stack)과 큐(Queue)

서론

Absttract Data Type VS Data Structure

ADT(abstract data type)

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

DS(data structure)

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

이번 시간에는 스택과 큐를 ADT 관점에서 설명할 예정임.

본론

스택(Stack)이란?

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

스택 주요 동작

  • push(넣는 것)
  • pop(빼는 것)
  • peek (가장 최상단에 있는 것을 알려줌)

스택 동작 방식 설명

스택과 큐

큐(queue)란?

큐 주요 동작

  • enqueue(아이템을 넣는 것)
  • dequeue(아이템을 빼는 것)
  • peek(꺼내겔 될 아이템이 값을 알 수 있음)

큐 동작 방식 설명

스택과 큐

스택 사용 사례: stack memeory & stack frame

def a(): 
    b()
def b():
    c()
def c():
    print("wow")
// 최종적으로 wow가 출력되면 스택이 끝이 난다.

큐 사용 사례 : producer/consumer architecture

스택과 큐

결론(마무리)

기술문서에서 큐를 만났을 때 팁

항상 FIFO를 의미하지는 않음. 큐가 대기공간처럼 사용되는게 많다. 이게 first in first out인지 확인해보고 읽어야 함.

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

  • StackOverflowError 스택 메모리 공간을 다 썼을 때 발생하는 에러
    => 재귀함수(recursive function)에서 탈출 못해서 발생 
    def recur_fibo(n):
  if n < 1:
      return n 
  else: 
    return(recur_fibo(n-1) + recur_fibo(n-2))
    // 탈출조건이 있어야 빠져나올 수 있음.
  • OutOfMemoryError java의 힙(heap)메모리를 다 썼을 때 발생
    => 큐에 데이터가 계속 쌓이기만 한다면 발생
    => 큐에 사이즈를 고정
    => 만약 큐가 다 찼을 때 어떻게 할 것인가?
  • 예외(exception)던지기
  • 특별한 값(null or false)을 반환
  • 성공할 때까지 영원히 스레드 블락(block)
  • 제한된 시간만 블락되고 그래도 안되면 포기
    Java에서 이 4가지 방식을 포함한 것은 LinkedBlockingQueue

참고자료 및 블로그

참고