스택(Stack)

스택이란?

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

스택은 큐와 함께 자바에서 사용되는 가장 기본적인 자료구조 중 하나이다. (큐의 경우 먼저 추가된 데이터가 먼저 나오는 FIFO 방식)

 

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

 

• 오버플로우 : 스택의 크기만큼 데이터가 꽉 차서 데이터를 넣지 못할 때
• 언더플로우 : 스택이 비어있는데, 데이터를 꺼내려고 할 때

 

스택 구조

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

 

스택의 장단점

장점

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

스택의 장점은 후출선입인 만큼 직전의 데이터를 빠르게 갖고올 수 있다는 것이다. 또한 균형성 검사를 할 수 있기 때문에 수식, 괄호 등의 검사에서도 쓰인다.

단점

• 데이터 최대 갯수를 미리 정해야한다.
• 저장 공간의 낭비가 발생할 수 있음 (미리 최대 갯수만큼 저장공간을 확보해야함)

java.util.Stack 클래스의 경우 별도의 사이즈를 명시하지 않는다. 처음 스택이 생성되었을 떄 10개의 데이터를 저장할 수 있는 공간이 할당된다. 이후 push 메소드를 통해 데이터가 추가되어 10개가 넘어가면 현재 스택 사이즈의 2배에 해당하는 공간을 할당하고, 기존 데이터를 복사하게 된다. (스택의 크기는 Integer.MAX_VALUE-8개 까지 늘어난다.)

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

 

스택 사용법

자바는 java.util.Stack 클래스를 통해 스택 동작을 제공하고 있다.

제네릭 부분에 사용할 객체를 담고 Stack을 선언해서 사용하면 된다.

Stack<타입> 변수명 = new Stack<타입>(); 

Stack<String> stack = new Stack<>();

// Stack에 데이터 추가
stack.push("santa");
stack.push("monica");

// Stack에서 데이터 꺼내기 -> monica
System.out.println(stack.pop());

// Stack의 최상단 값 출력(제거하지 않음) -> santa
System.out.println(stack.peek());

• 스택 메서드

stack.add(A);		//stack에 A 추가 (boolean형 리턴)
stack.push(A);		//stack에 A 추가 (Exception 리턴)
stack.pop();		//stack의 마지막 push값 제거
stack.clear();		//stack의 전체 삭제
stack.peek();		//stack의 마지막 push값 확인
stack.size();		//stack의 배열 길이 수
stack.empty();		//stack이 비어있으면 true (있으면 false)
stack.contains(a);	//stack에 값(a)이 들어있으면 true (없으면 false)
stack.search(A);	//stack에 A가 있는 인덱스 위치 반환

 

 

출처

https://mollangpiu.tistory.com/261 
https://hbase.tistory.com/122
https://st-lab.tistory.com/174