스택
- 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
- 스택에 저장된 자료는 선형 구조를 갖는다
선형구조 : 자료 간의 관계가 1대1의 관계를 갖는다
비선형구조: 자료 간의 관계가 1대N의 관계를 갖는다(예: 트리) - 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다
- 마지막에 삽입한 자료를 가장 먼저 꺼낸다. 후입선출
스택에 1, 2, 3 순으ㅗ 자료를 상빙ㅂ한 후 꺼내면 역순으로 3, 2, 1 로 꺼낸다
스택을 프로그램에서 구현하기 위해 필요한 자료구조와 연산
- 자료구조: 자료를 선형으로 저장할 저장소
배열 사용 가능
저장소 자체를 스택이라 부르기도 한다
스택에서 마지막 삽입된 원소의 위치를 top 이라 부른다
연산
- 삽입 : 저장소에 자료 저장, push
- 삭제 : 저장소에서 자료 꺼낸다. 꺼낸 자료는 삽입 자료의 역순, pop
- 스택이 공백인지 아닌지 확인하는 연산은 isEmpty
- 스택의 top 에 있는 item(원소)를 반환하는 연산 peek
스택의 삽입/삭제 과정
빈 스택에 원소 A, B, C를 차례로 삽입 후 한번 삭제하는 연산과정
스택의 push 알고리즘
(가능하면 스택의 크기를 정해놓고 움직이려고 한다)
- append 메소드를 통해 리스트의 마지막에 데이터를 삽입
def push(item):
s.append(item)
스택의 pop 알고리즘
def pop():
if len(s) == 0:
# underflow
return
else:
return s.pop()
스택 구현 고려 사항
- 1차원 배열 사용해 구현할 경우, 구현이 용이하다는 장점이 있지만 스택의 크기를 변경하기가 어렵다는 단점
- 저장소를 동적 할당하여 스택 구현하는 방법이 있다 (동적 연결리스트 이용) 구현은 복잡하지만 메모리를 효율적으로 사용한다는 장점이 있다
스택 응용1 : 괄호검사
- 괄호의 종류 : 대괄호 [ ] , 중괄호 { }, 소괄호 ( )
- 조건
왼쪽괄호의 개수와 오른쪽 괄호 개수가 같아야 한다
같은 괄호에서 왼쪽은 오른쪽보다 먼저 나와야 한다
괄호 사이에는 포함 관계만 존재한다
여는 괄호 -> push
여는 괄호 -> push
닫는 괄호 -> pop
- 괄호 없고 stack 비었으면 정상
- 괄호 없고 stack에 남은 괄호가 있으면 오류
- 닫는 괄호가 있는데 stack이 비어있으면 오류
알고리즘 개요
괄호를 차례대로 조사하면서 왼쪽 만나면 스택에 삽입!
오른쪽 만나면 스택에서 top 괄호를 삭제한 후 오른쪽과 짝이 맞는지 검사
스택 응용2: Function call
프로그램에서 함수 호출과 복귀에 따른 수행 순서를 관리
- 가장 마지막에 호출된 함수가 가장 먼저 실행 완료하고 복귀하는 후입선출 구조 (스택 이용해 순서 관리)
- 함수 호출 발생하면 지역변수, 매개변수, 복귀할 주소 등의 정보를 스택 프레임에저장해 시스템 스택에 삽입
- 실행 끝나면 시스템 스택의 top 원소(스택 프레임)를 삭제(pop)하면서 프레임이 저장되어 있던 복귀주소를 확인하고 복귀
- 함수 호출과 복귀에 따라 과정 반복하여 전체 프로그램이 종료되면 시스템 스택은 공백 스택이 된다
