ABOUT ME

개발과 사진을 인생의 낙으로

  • 스택, 큐
    개발 지식/알고리즘 2020. 6. 30. 14:55

    스택 (Last In First Out) (배열로 구현)

    peapable stack : 중간에 넣고 뺄 수 있는 스택 (LL로 구현)

     

    하나의 공간에 두개의 스택

    S1 □□ S2

    -> bottom point가 두개

     

    다중 스택: 하나의 스택 안에 여러개의 스택이 들어가는 형태

    초기 공간 분배 방법

    영분배: n개의 스택을 모두 합친 뒤 모든 스택의 크기 0

    균등분배: 스택을 합쳐서 저장공간 균등하게 재분배

    차등분배: 스택의 이용도 추정하여 그 비융ㄹ에 따라 공간 분할

    knuth's 0분배: 처음에는 모두 0, overflow가 발생할 때 마다 할당 공간 1 증가

     

    ---------------------------------------------------------------------------------------------

     

    큐 (First In First Out)

    <- front □ rear <-

    : front에서 하나가 삭제될 때 안의 내용들을 당겨주는데 비효율적 : 원형큐를 사용한다

     

    원형큐 :

    공백 상태 원형 큐 : front = rear

    포화 상태 원형 큐 : front % M = (rear + 1) % M

     + 포화상태를 구별하기 위해 하나의 공간은 항상 남겨둔다

     

    - insert 연산 :

    r = (r + 1) % M

    - delete 연산 :

    f = (f + 1) % M

     

     

    Deque (Double-ended queue)

    <-> front □ rear <->

    댓글

Designed by Tistory.