[자료구조] 스택

스택과 큐

스택과 큐는 데이터를 저장하는 동적인 자료구조이다. 스택은 LIFO(last in first out) 구조이고 큐는 FIFO(first in first out) 구조이다.

스택

스택은 접시가 쌓인 걸 상상하면 된다.

접시를 꺼내는 순서는 맨 위에 놓인 접시가 가장 먼저 나온다.

접시를 꺼내는 순서는 맨 위에 놓인 접시가 가장 먼저 나온다.

접시를 꺼내는 순서는 맨 위에 놓인 접시가 가장 먼저 나온다.

항상 맨위의 접시를 꺼낸다는 순서를 생각하면 Last In First Out, LIFO의 구조이다.

• 스택에 무언갈 넣는 것을 PUSH연산이라고 한다.
• 반대로 꺼내는 것, 삭제(Delete)는 POP연산이다.
• 빈 스택에서 POP하려는 것을 Undeflow, 가득 찬 스택에서 PUSH하는 것을 Overflow라고 한다.

가장 최근에 Insert한 요소의 인덱스를 Stack.TOP라고 할 때 Stack의 모습은 아래와 같다.

순서대로 초기상태, Stack.PUSH(17)후, Stack.POP()후 의 모습이다. 

 

스택은 [1,2,...,TOP]까지이다. 만약 Stack.TOP == 0 이면 Stack은 Empty라고 한다.

주요 연산

PUSH(S, x): 
	S.top = S.top + 1 
    S[S.top] = x 
    
   
POP(S): 
    if stack-empty(S): 
    	error "underflow" 
    else: 
    	S.top = S.top - 1 
        return S[S.top+1]

보조연산

Stack-empty(): 스택이 비어있는지 확인 
Stack-size(): 스택의 사이즈 확인 
Stack-full: 스택이 가득 찼는지 확인 
Stack-top: 스택의 마지막 항목을 삭제하지 않고 리턴