스택(stack)

---

<스택 노트 정리>

스택이란?

스택(Stack)이란 마지막에 들어온 데이터가 먼저 나가는 후입선출(LIFO, Last In First Out)의 자료구조이다.

스택의 주요 연산과 시간복잡도

삽입(push)와 삭제(pop) - 전부 스택의 맨 위(top, peek)에서만 이루어진다. -> O(1)
전체 조회 - n개의 원소를 하나하나 순서대로 조회한다. -> O(n)

스택의 주요 사용처

• 원소 전체를 역순으로 출력
• 후위 표기 연산
• 그래프의 깊이 우선 탐색(DFS, Depth First Search)
• 함수의 재귀적인(Recursive) 호출

---

JAVA에서의 스택 사용 예시

import java.util.stack;

주요 메소드

출처

메소드	타입	설명
push(E item)	E	스택의 가장 위에 item을 삽입
pop()	E	스택의 가장 위(top)의 원소를 삭제한 후 반환
peek()	E	스택의 가장 위의 원소를 삭제하지 않고 반환
search(Object o)	int	찾고자 하는 값(Object o)이 스택의 위에서 몇 번째에 있는지를 반환, 없을 경우 -1 반환
empty()	boolean	스택이 비어있는 경우 true, 아닐 시 false 반환

예시 코드

Stack<Integer> stack = new Stack<>();	// 정수형 스택 선언

System.out.println(stack.empty());		// true
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);

System.out.println(stack.empty());		// false
System.out.println(stack.search(5));	// 1
System.out.println(stack.search(2));	// 4
System.out.println(stack.search(6));	// -1
System.out.println(stack.peek());		// 5
System.out.println(stack);				// [1, 2, 3, 4, 5]

System.out.println(stack.pop());		// 5
System.out.println(stack.pop());		// 4
System.out.println(stack.pop());		// 3
System.out.println(stack);				// [1, 2]

System.out.println(stack.pop());		// 2
System.out.println(stack.pop());		// 1
System.out.println(stack);				// []