스택, 큐

스택 (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 <->