Stack

Stack의 사전적 정의는 '쌓다', '더미'입니다.

상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다.

Stack의 가장 큰 특징은 나중에 들어간 것이 먼저 나오는 (LIFO, Last In First Out)의 형태를 띈다는 것입니다. 이 방식을 가진 자료구조인 Stack을 활용하여 데이터가 입력된 순서의 역순으로 처리되어야 하는 다양한 문제를 해결할 수 있습니다. 자바에서 Stack은 java.util.Stack을 import하면 바로 사용할 수 있습니다.

---

Stack의 특징

1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조

2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 한다.

3. 인터럽트 처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임

4. 그래프의 깊이 우선 탐색(DFS)에서 사용

5. 재귀적(Recursion) 함수를 호출 할 때 사용

Stack 선언

import java.util.Stack; //import
Stack<Integer> stack = new Stack<>(); //int형 스택 선언
Stack<String> stack = new Stack<>(); //char형 스택 선언

Stack 사용법

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가 [1]
stack.push(2);     // stack에 값 2 추가 [1, 2]
stack.push(3);     // stack에 값 3 추가 [1, 2, 3]

stack.pop();       // stack에 마지막으로 들어온 값 제거 [1, 2]
stack.clear();     // stack의 전체 값 제거 (초기화) []
----------------------------------------------------------

stack.push(1);  // stack에 값 1 추가  [1]
stack.push(2);  // stack에 값 2 추가  [1, 2]
stack.push(3);  // stack에 값 3 추가  [1, 2, 3]

stack.peek();   // stack의 가장 상단의(마지막으로 들어온)값 3 출력,
								// 데이터 제거되지 않음

stack.size();      // stack의 크기 출력 : 3
stack.empty();     // stack이 비어있는제 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)

시간 복잡도

	Average	Worst
Access	O(n)	O(n)
Search	O(n)	O(n)
Insert(push)	O(1)	O(1)
Delete(pop)	O(1)	O(1)