Stack

Stack❓

• Stack은 후입선출(Last-In-First-Out; LIFO)의 대표적인 선형 자료구조 중의 하나
• 후입선출이란 Last-In-First-Out 이라는 뜻 그대로 나중에 들어온 데이터가 가장 먼저 나간다 의 의미
• 프로그래밍에서 데이터가 입력된 순서대로 처리되는 것이 아닌, 가장 나중에 들어온 데이터를 먼저 처리할 때 사용

Stack의 특징

1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조
2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함
3. 인터럽트 처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
4. 재귀(Recursion) 함수를 호출 할 때 사용
5. 그래프의 깊이 우선 탐색(DFS)에서 사용

시간복잡도

연산	평균 소모 시간	최악 소모 시간
Acess	O(n)	O(n)
Search	O(n)	O(n)
Push	O(1)	O(1)
Pop	O(1)	O(1)

• Stack에서의 삽입 삭제는 O(1)의 시간 복잡도를 가짐
  -> 삽입, 삭제는 항상 Stack의 top에서 일어나기 때문

 

Stack 사용법

Stack 선언

import java.util.Stack

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

 

Stack 값 추가

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

stack.push(1);        // stack에 1 추가
stack.push(2);        // stack에 2 추가
stack.push(3);        // stack에 3 추가

 

Stack 값 삭제

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

stack.pop();         // stack의 맨 위 값 삭제

 

Stack 가장 상단 값 출력

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

stack.peek();        // stack의 가장 상단 값 출력

 

Stack 기타 메서드

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

stack.size();        // stack의 크기 출력
stack.empty();        // stack이 비어있는지 확인 (비어있다면 true를 반환)
stack.contains(1);    // stack에 1이 있는지 확인 (있다면 true를 반환)
stack.clear();         // stack에 들어있는 모든 값 초기화
stack.search(2);     // 2(value)의 인덱스 값 반환