Stack

Stack 이란 ?

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 사전적 정의는 '쌓다' 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 구조로 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 

자료를 넣는것을 '밀어넣는다' 하여 push라고 하고 반대로 넣어둔 자료를 꺼내는 것을 pop이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 즉, 나중에 들어간 것이 먼저 나오는 LIFO(Last In First Out)의 형태를 띄고있다.

 

스택 용어

(1) 삽입 (Push) : Push는 스택의 구조상 최상 위에 데이터가 저장 됩니다.

(2) 삭제 (Pop) : Push와 반대로 데이터를 삭제하는 것을 Pop이라 합니다. Pop도 Push와 마찬가지로 최상위 데이터 위치에서 삭제가 됩니다.

(3) 읽기 (Peek) : 마지막 위치(top)에 해당하는 데이터를 읽습니다. 이 때, top의 변화는 없습니다.

 

Stack 선언 

import java.util.Stack;

Stack<Integer>stack = new Stack<Integer>(); // Integer타입 선언
Stack<Integer>stack = new Stack<>(); // 뒤의 타입 생략 가능
Stack<Character>stack = new Stack<>(); // Char 타입 선언
Stack<String>stack = new Stack<>(); // String 타입 선언

스텍 메소드 종류

메서드	설명
stack.push(1);	스택에 값 1 추가
stack.size();	스택의 크기 출력
stack.empty();	스택이 비어 있으면 true, 비어 있지 않으면 false를 반환
stack.peek();	스택의 제일 상단에 있는(마지막으로 저장된) 요소를 반환
stack.pop();	스택의 제일 상단에 있는(마지막으로 저장된) 요소를 반환후, 해당 요소를 스택에서 제거함. (값을 remove 할때 pop 을 사용하면된다.)
stack.search(1);	스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환 이때 인덱스는 제일 상단에 있는(마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작함.
stack.contains(1);	스택에 1이 있으면 true, 없으면 false 를 반환

스택 시간복잡도 Big O

• Insertion O(1)
• Deletion O(1)
• Search O(n)

삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가집니다. 하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가집니다.

 

---

참고 링크 
https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90

스택, 큐 (Stack, Queue)

https://yunamom.tistory.com/232

[Java] Stack 클래스 설명 및 예제