[스택]

스택

스택은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 제한적으로 접근할 수 있는 후입선출(Last-In-First-Out) 형태의 선형 자료구조이다.

• 스택 상단 : 스택에서 입출력이 이루어지는 부분
• 스택 하단 : 스택의 바닥 부분
• 요소 : 스택에 저장되는 것
• 공백 스택 : 스택에 요소가 없는 상태

 

스택의 is_empty 연산

is_empty(S):
	if top == -1
    	then return TRUE
        else return FALSE

 

 

 

스택의 is_full 연산

is_full(S):
	if top >= (MAX_STACK_SIZE-1)
    	then return TRUE
		else return FALSE

 

 

 

스택의 push 연산

push(S, x):
	if is_full(S)
    	then error "overflow"
        else top<-top+1
        	stack[top]<-x

 

 

 

스택의 pop 연산

pop(S, x):

if is_empty(S)
	then error "underflow"
    else e <- stack[top]
    	 top <- top - 1
         return e

 

 

 

스택의 응용 - 후위 표기 수식의 계산

중위 표기법	전위 표기법	후위 표기법
2+3*4	+2*34	234*+
a*b+5	+*ab5	ab*5+
(1+2)*7	*+127	12+7*

 

 

 

후위 표기 수식 계산 알고리즘

calc_posfix:
	스택 s를 생성하고 초기화한다.
    for item in 후위표기식 do
    	if (item이 피연산자이면)
        	push(s, item)
        else if (item이 연산자 op이면)
        	second <- pop(s)
            first <- pop(s)
            result <- first op second // op
            push(s, result)
    final_result <- pop(s);

 

 

 

중위 표기 수식을 후위 표기 수식으로 변환하는 알고리즘

infix_to_postfix(exp):

스택 s를 생성하고 초기화
while (exp에 처리할 문자가 남아 있으면)
	ch <- 다음에 처리할 문자
    switch (ch)
    case 연산자:
    	while (peek(s)의 우선순위 >= ch의 우선순위) do
        	e <- pop(s)
            e를 출력
        push(s, ch);
        break;
	case 왼쪽 괄호:
    	push(s, ch);

 

 

 

미로 탐색 알고리즘

maze_search():

스택 s과 출구의 위치 x, 현재 생쥐의 위치를 초기화
while(현재의 위치가 출구가 아니면) do
	현재위치를 방문한 것으로 표기
	if(현재 위치의 위, 아래, 왼쪽, 오른쪽 위치가 아직 방문되지 않았고 갈 수 있으면)
    	then 그 위치들을 스택에 push
    if(is_empty(s))
    	then 실패
	else 스택에서 하나의 위치를 꺼내어 현재 위치로 만든다;
성공;