[Data Structure] 스택(Stack)이란?

1. 스택(Stack)의 개념

스택(Stack)은 "쌓다"라는 의미로 데이터를 하나씩 쌓아 올린 형태의 자료구조로, 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조이다.

 

스택(Stack) 자료구조를 쉽게 예를 들어보자면, 박스 쌓기를 생각하면 된다.

박스를 아래에서 하나씩 쌓고, 박스를 뺄 때는 마지막에 쌓은 박스부터 다시 순서대로 박스를 빼야 한다는 점을 생각하면 쉽다.

 

2. 자바(Java) 라이브러리 스택(Stack) 관련 메서드

- pop() : 스택(Stack)의 가장 윗부분에 있는 자료를 제거한다.

- push(item) : 스택(Stack)의 가장 윗부분에 item을 추가한다.

- peek() : 스택(Stack) 가장 윗 부분에 있는 데이터를 반환한다.

- search(item) : 스택(Stack)에서 item이 있는 인덱스 위치를 반환한다.

- sEmpty(): 스택이 비어 있을 때에 true를 반환한다.

3. 스택(Stack)에서의 오버플로우(Overflow)와 언더플로우(Underflow)

- 오버플로우(Overflow) : 스택(Stack)의 크기만큼 데이터가 꽉 차서 데이터를 넣지 못할 때 발생한다.

- 언더플로우(Underflow) : 스택(Stack)이 비어 있는 상황에서 데이터를 꺼내려고 할 경우에 발생한다.

 

4. 스택(Stack) 구현

import java.util.*

public class Main{
	public static void main(String[] args){
		Stack<Intger> s = new Stack<>(); //int형 스택(Stack) 선언
		
		s.push(5); // 스택(Stack)에 5 추가
		s.push(2); // 스택(Stack)에 2 추가
		s.push(3); // 스택(Stack)에 3 추가
		s.push(7); // 스택(Stack)에 7 추가
		s.pop();   // 스택(Stack)에 가장 마지막에 추가된 7 제거
		s.push(1); // 스택(Stack)에 1 추가
		s.push(4); // 스택(Stack)에 4 추가
		s.pop();   // 스택(Stack)에 가장 마지막에 추가된 4 제거
		
		while(!s.empty()){//스택의 최상단 원소부터 출력
			System.out.print(s.peek() + " ");
			s.pop();
		}
	}
}

//실행 결과 ==> 1 3 2 5

 

5. 스택(Stack) 사용 사례

(1) 웹 브라우저 방문기록 (뒤로가기)

(2) 실핼 취소(undo)

(3) 역순 문자열 만들기

(4) 후위 표기법 계산

(5) 재귀 알고리즘