Stack 개념과 배열 기반 스택

개념

스택은 데이터가 들어갈 때마다 쌓이는 것처럼 보여 Stack이라 부른다. 가장 끝단에서 삽입과 삭제가 모두 일어난다. 후입 선출 형식으로 가장 마지박에 삽입된 원소가 가장 먼저 삭제된다. Last In First Out 이라고도 하며 LIFO구조이다.

스택의 주요 기능

 stack의 삽입 push

   요소 하나를 삽입하는 과정으로 맨 윗 부분에 추가된다.

 stack의 삭제 pop

   가장 위에 있는 요소를 제거한다.

 stack의 읽기 peek

    top에 위치한 값을 삭제하지 않고 반환한다.

 stack의 범위 검사 isEmpty

    스택이 꽉 차있는지 검사한다.

stack의 원리

스택의 활용

• 실행 취소 및 뒤로가기뒤로 가기 : 주로 undo, 뒤로 가기를 눌렀을 때 이전에 방문했던 곳이나 이전 상태로 되돌려질 것이다. 이 기능을 구현할 때 스택 기반으로 활용할  수 있다.
• 재귀 함수 : 재귀 함수는 자기 자신을 호출하는 함수를 재귀 함수라 하며 함수를 호출할 때마다 스택처럼 메모리에 쌓인다.
• 기타 : 메모리에 적재 될 때마다 주로 스택처럼 쌓인다.

 

배열 기반 스택 파이썬 구현

if __name__=="__main__":
    stack = [0 for i in range(10)]
    top=-1;
    while(True):
        print("push=pu pop=po peek=pe quit=q\n")
        
        ch=input()
        if ch=='pu':
            top+=1
            stack[top]=input()

        elif ch=='po':
            top-=1
    
        elif ch=='pe':
            print(stack[top])
        elif ch=='q':
            break
        else:
            print("wrong")