[자료구조] 스택 (Stack)

스택

• 가장 먼저 입력된 데이터가 가장 나중에 출력됨.
• 한쪽에서만 자료의 입•출력이 일어나는 구조 

• top : 스택의 최상단을 의미 
• push는 데이터삽입을 의미한다. push하게되면 top포인터가 하나 증가하여 방금 추가된 데이터의 상단을 가리키게 된다.
  pop은 데이터의 삭제이며 이후에 top포인터가 하나 감소한다.           
• 데이터의 삽입과 삭제가 상단인 top에서만 일어난다.                

• 스택영역에 데이터가 꽉 차있으면 full 상태, 데이터가 존재하지 않으면 empty상태로 판단한다.  
• 스택오버플로우 StackOverflow : 포화상태인 스택에 새로운 요소 삽입하려 할 때 발생하는 오류이며 stackfull 메세지 도출됨
  스택언더플로우 StackUnderflow : 공백상태인 스택에서 pop을 실행할 때 발생하는 오류 stackempty 메세지 도출

이러한 특징으로 인해 스택은 늦게 들어온 데이터가 먼저 사용되는 후입선출(LIFO)방식의 자료구조다.

 

추상자료구조 (ADT)

객체(데이터)에 대해 적용가능한 연산을 정의하고 데이터와 연산을 통해 프로그래머의 의도를 반영하는 자료구조를 표현하는 방법. 

push, pop, create와 같이 객체에 접근할 수 있도록 의도를 가지고 만든 것이기 때문에 효율적인 동작을 위해 개발자들이 함부로 접근할 수 없도록 제한되어 있다. 

스택의 ADT 연산

ADT연산	기능설명
push()	데이터삽입
pop()	데이터삭제
isEmpty()	스택이 비어있으면 true, 그렇지않으면 false 반환
isFull()	스택이 가득차있으면 true, 그렇지않으면 false 반환
size()	스택에있는 요소 개수 반환
display()	전체항목 화면출력

 

스택의 응용

• 변수에 대한 메모리의 할당과 수집을 위한 시스템 스택
  - 변수의 생명주기 관리를 하는경우 운영체제가 시스템 스택을 이용할 수 있다.
• 서브루틴 호출 관리를 위한 스택
  - 서브루틴 수행이 끝난 후에 되돌아갈 함수 주소를 저장하는 경우
• 연산자들간의 우선순위에 의해 계산순서가 결정되는 경우
• 인터럽트 처리와 이후 리턴할 명령 수행지점을 저장하기 위한 스택
• 컴파일러와 순환호출 관리
  - 재귀와 같은 순환호출의 경우 호출이 끝나고 되돌아갈 주소를 저장할 수 있다. 

 

배열로 스택을 구현하는 경우의 간단한예