CSDataStructure

[자료구조] 스택(Stack)

CS, DataStructure

스택(Stack)

1. 스택의 개념

자료의 삽입과 삭제가 한쪽 끝에서만!

  • 스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다.
  • 스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO; Last In First Out) 방식으로 자료를 처리한다.
  • TOP : Stack으로 할당된 기억 공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소. 스택 포인터(SP, Stack Pointer)라고도 한다.
  • Bottom : 스택의 가장 밑바닥이다.


2. 스택 - 자료의 삽입(Push)과 삭제(Pop)

출처 : Wikipedia


3. 자료의 삽입(Push)

1
2
3
4
5
Top = Top + 1
If Top > M Then
    Overflow
Else
    X(Top) <- Item
  • 코드 설명 : 스택 포인터(Top)를 1 증가시킨다. 스택 포인터가 스택의 크기보다 크면 Overflow이고 그렇지 않으면 Item이 가지고 있는 값을 스택의 Top위치에 삽입한다.
  • M : 스택의 크기
  • Top : 스택 포인터
  • X : 스택의 이름
  • Overflow : 스택으로 할당받은 메모리 부분의 마지막 주소가 M번지라고 할 때, Top Pointer의 값이 M보다 커지면 스택의 모든 기억장소가 꽉 채워져 있는 상태이므로 더 이상 자료를 삽입할 수 없어 Overflow를 발생시킨다.


4. 자료의 삭제(Pop)

1
2
3
4
5
If Top = 0 Then
    Underflow
Else
    Item <- X(Top)
    Top = Top - 1
  • 코드 설명 : 스택 포인터가 0이면 스택의 바닥이므로 더 이상 삭제할 자료가 없으므로 Underflow를 처리한다. 그렇지 않으면 Top 위치에 있는 값을 Item으로 옮기고 스택 포인터를 1 감소시킨다.
  • Stack에 기억되어 있는 자료를 삭제시킬 때는 제일 먼저 삭제할 자료가 있는지 없는지부터 확인해야 한다.
  • Underflow : Top Pointer가 주소 0을 가지고 있다면 스택에는 삭제할 자료가 없으므로 Underflow를 발생시킨다.


5. Stack의 응용 분야

  • 부 프로그램 호출 시 복귀주소를 저장할 때
  • 함수 호출의 순서 제어
  • 인터럽트가 발생하여 복귀주소를 저장할 때
  • 후위 표기법(Postfix Notation)으로 표현된 수식을 연산할 때
  • 0 주소지정방식 명령어의 자료 저장소
  • 재귀(Recursive) 프로그램의 순서 제어
  • 컴파일러를 이용한 언어 번역 시
Share