스택(Stack)

스택이란?

스택은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(FILO)방식이다. 데이터를 제한적으로 접근할 수 있는 구조이고, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조이다.

스택은 콜 스택(call stack)이라 하여 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조에도 널리 활용된다. 컴파일러가 출력하는 에러도 스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다. 또한 스택은 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다. 이외에도 꽉 찬 스택에 요소를 삽입하고자 할 때 스택에 요소가 넘쳐서 에러가 발생하는 것을 스택 버퍼 오버플로(stack buffer overflow)라고 부른다. 질의응답 서비스 사이트인 스택오버플로의 명칭도 여기서 유래했다.

스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조로서, 스택과 연관된 알고리즘을 제대로 이해하느냐 못하느냐에 따라 기본 알고리즘을 설계할 수 있느냐 없느냐가 결정되기도 한다.

스택 구조

  • 스택은 LIFO 또는 FILO 데이터 관리 방식을 따름
  • 대표적인 스택의 활용: 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
  • 주요기능push(): 데이터를 스택에 넣기pop(): 데이터를 스택에서 꺼내기
  • 스택의 크기: 스택에 쌓을 수 있는 데이터의 최대 개수

스택 구조와 프로세스

  • 스택 구조는 프로세스 실행 구조의 가장 기본
  • 함수 호출 시 프로세스 실행 구조를 스택과 비교해서 이해 필요

스택의 장단점

장점

  • 구조가 단순해서 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.

단점(일반적인 스택 구현 시)

  • 데이터 최대 갯수를 미리 정해야 한다. -> 파이썬의 겨우 재귀 함수는 1000번까지만 호출이 가능함
  • 저장 공간의 낭비가 발생할 수 있다. -> 미리 최대 갯수만큼 저장 공간 확보해야 함

스택의 경우 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다. 이경우, 위에서 열거한 단점이 있을 수 있다.

스택의 구현

코틀린에서는 큐와 스택을 기본 라이브러리로 제공하지 않기 때문에, 자바의 큐와 스택을 가져와 사용한다. 또한 별도의 라이브러리를 사용할 필요 없이 큐와 스택의 성질을 이용하면 (큐는 선입선출, 스택은 후입선출) ArrayList로도 구현할 수 있다.

fun main(args:Array<String>){
	var stack : Stack<Int> = Stack<Int>()

	stack.push(1) // 객체를 스택에 추가(1)
	stack.push(2) // 객체를 스택에 추가(1, 2)
	stack.push(3) // 객체를 스택에 추가(1, 2, 3)

	stack.peek()  // 맨 위 객체를 반환 (비어있는 상태라면 EmptyStackException 발생)
	println(stack) // [1, 2, 3] 
	
	stack.pop()   // 맨 위의 객체 삭제하고 반환 (비어 있는 상태이면 EmptyStackException 발생)
	println(stack) // [1, 2]
	
}

위의 코드처럼 Stack 자료형을 이용하면 쉽게 스택을 구현할 수 있다.