스택(Stack)

스택이란 물건을 쌓아 올리듯 자료를 쌓아올린 형태의 자료구조이다. 

스택의 push와 pop

선형 자료구조(자료 간의 관계가 1대 1인 관계)를 가지며 후입선출(LIFO: Last In First Out) 의 특성을 가진다.

즉 제일 나중에 들어온 데이터가 제일 먼저 나가게 된다. 

스택에서 입출력이 이루어지는 부분을 스택 상단(top)이라고 하고 아랫 부분을 스택 하단(bottom)이라고 한다. 자료가 하나도 들어있지 않은 스택을 공백 스택(empty stack)이라고 하며, 스택에 저장되는 데이터를 요소(element)라고 부른다.

스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어져야 할 경우 매우 요긴하다.

 

시스템 스택을 이용한 함수 호출

함수는 실행이 끝나면 자신을 호출한 함수로 돌아가야 한다. 이 때, 스택은 복귀할 주소를 기억하는데 사용된다. 함수는 호출된 역순으로 돌아가야 하기 때문이다. 함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스텍에 삽입한다. 시스템 스택에는 함수가 호출될 때마다 활성 레코드(activation record)가 만들어지며 여기에 복귀주소가 저장된다. 함수의 실행이 끝나면 시스템 스택의 top원소(스택 프레임)을 삭제(pop)하면서 프레임에 저장되어 있던 복귀 주소를 확인한다. 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.

 

스택의 연산

스택에는 두 가지 연산이 있다.

원소를 삽입하는 연산 (push)과 원소를 삭제하는 연산(pop)이 그것으로 후입선출의 성격을 갖는 스택의 특성상 제일 위에 쌓인 원소(제일 늦게 들어온 원소)를 삭제하고 삽입한다면 제일 위에 원소를 삽입한다. 접시를 한 줄로 차곡차곡 쌓는다고 생각할 때, 제일 위에 있는 접시를 사용하고, 접시를 쌓을 때는 제일 위에 쌓지 않는가? 스택도 그러하다. 

 

자바에서 스택의 사용

자바에서는 java.util.Stack을 import 해주여야 stack의 api를 사용할 수 있다.

주요 연산은 다음과 같다

• isEmpty(): 스택이 공백 스택인지 아닌지를 알려주는 메소드. bool 타입으로 리턴 값으로 true, false가 나옴
• pop(): 삭제 연산으로 제일 위에 있는 원소를 삭제한다.
• push(): 삽입 연산으로 제일 위에 원소를 삽입한다.
• peek(): 이건 제일 위에 있는 원소가 무슨 값인지 값을 리턴하는 함수다 pop은 삭제 + peek이라면 이건 그냥 보여주기만 한다.
• size():스택의 사이즈를 알려주는 메소드

 

스택의 응용 문제

괄호검사문제, 후위표기수식 등이 있다.