🤔 스택이란?
스택(stack)이란 한국말로 번역하면 쌓이다, 포개지다, 채우다 등으로 번역된다.
롤 하시는 분이라면 많이 들어봤던 나서스 스택...이 있다. 몇 스택 쌓았니?
그럼 자료구조로서의 스택은 무엇일까? 말 그대로 입력 데이터를 순서대로 쌓는 자료구조이다. 모양을 예로 들면 프링글스 통이 될 수 있을 것 같다.
🙄 스택 특징은?
스택의 특징을 간략히 설명하면,
-
LIFO(Last In First Out) 후입선출로, 마지막에 들어온 것이 가장 먼저 나가는 방식
- 흔히, 아는 FIFO(Firtst In first Out)의 반댓말이다. <- Queue(큐)가 여기 해당
- 흔히, 아는 FIFO(Firtst In first Out)의 반댓말이다. <- Queue(큐)가 여기 해당
-
들어오는 방향과 나가는 방향이 같은 단방향 입출력 구조를 가진다.
- 중간의 데이터를 삭제하거나 추가하는 것이 불가능하다.
-
자바의 stack 클래스는 List 인터페이스의 Vector 클래스를 상속 받기 때문에 Thread-safe한 특징을 가지고 있다.
- Vector 클래스는 각각의 메서드에 대한 동기화(synchronization)로 이루어지기 때문에 여러 Thread에서 동시에 접근해도 안전하게 동작한다.
그럼 스택은 언제 쓰는건가??
스택 자료구조는 메모리 영역이나 실생활에서 많이 사용하는 자료구조이다.
수식계산, 수식괄호 검사, 웹브라우저 뒤로가기/ 앞으로, undo / redo
메모리 영역에서는 JVM의 Runtime data area에서 지역변수, 매개변수 값을 저장하며 메서드가 호출 될 때 스택에 쌓이고 호출이 종료되면 제거되는 부분에서 사용 된다고 한다.
또한 알고리즘에서는 그래프의 깊이 우선 탐색(DFS)에 이용되며, 재귀 형태의 함수를 호출 할 때 이용된다.
😚 스택 사용법 정리
🍕 스택 선언하기
import java.util.statck;
Stack<Integer> stack_int = new Stack<>();스택 역시 클래스로 되어 있기 때문에 new 연산자를 통해 객체로 선언하여 사용할 수 있다.
🍔 스택에 요소(element) 넣기
Stack<String> stack_str = new Stack<>();
stack_str.push("box1");
stack_str.push("box2");
stack_str.push("box3");
System.out.println(stack_str); // ["box1", "box2", "box3"]스택에 요소를 넣을 때에는 다음과 같은 메서드를 사용한다.
Object push(Object item)
-> item을 스택의 맨 위에 넣습니다.push의 시간복잡도는 O(1)을 가집니다. ※최상단에 값을 넣기만 하기 때문
🍟 스택에 요소(elment) 꺼내기
Stack<String> stack_str = new Stack<>();
stack_str.push("box1");
stack_str.push("box2");
stack_str.push("box3");
System.out.println(stack_str.pop()); // "box3"
System.out.println(stack_str); // ["box1", "box2", "box3"]스택에 요소를 꺼낼 때에는 다음과 같은 메서드를 사용한다.
Object pop()
-> 스택의 맨 위의 요소를 제거하며, 해당 함수(pop)의 반환값으로 해당 요소를 반환합니다.
즉, 스택의 맨 위의 요소를 꺼내며(제거) 이를 반환하는 메서드이다.
만약, 꺼낼 요소가 없다면 EmptyStackException을 발생시킨다.
pop()메서드의 시간복잡도는 O(1)입니다. ※최상단의 값만 제거하고 반환하기 때문
🌭 스택에 맨 위의 요소 가져오기
Stack<String> stack_str = new Stack<>();
stack_str.push("box1");
stack_str.push("box2");
stack_str.push("box3");
System.out.println(stack_str.peek()); // "box3"
System.out.println(stack_str); // ["box1", "box2", "box3"]스택에 최상단 요소를 가져오고자 하면, 다음과 같은 메서드를 사용한다.
Object peak()
-> pop()메서드와 달리 스택의 맨 위의 요소를 제거하지 않고 맨 위의 요소에 해당하는 값만 보여줍니다.
peak()메서드의 시간 복잡도는 O(1)입니다. ※최상단의 값만 보여주기 때문
🍿 스택공간이 비었는지 아닌지 판단하기
Stack<String> stack_str = new Stack<>();
if(stack_str.empty() {
System.out.println("공백")
}
// "공백" 출력스택 공간이 비었는지의 유무를 판단하는 메서드는 다음과 같다
boolean empty();
-> stack공간이 비었다면 true, 아니면 false를 반환이를 통해 peek() 메서드나 pop()메서드를 보다 안전하게 사용할 수 있다.
만약 빈 공간인 상태에서 peek, pop 메서드를 사용하면 EmptyStackException 예외를 던진다.
🥓 스택 요소 위치 파악하기
Stack<String> stack_str = new Stack<>();
stack_str.push("box1");
stack_str.push("box2");
stack_str.push("box3");
stack_str.push("box4");
stack_str.push("box5");
// 배열이나 리스트와 같이 인덱스 번호를 반환하는 것이 아닌,
// pop()을 만약 하게 된다면, 몇번째로 밖으로 나가지는지를 나타냄
System.out.println(stack_str.search("box3")); // 3
System.out.println(stack_str.search("box5")); // 1스택 요소의 위치를 파악하는 메서드는 다음과 같다
int search(Object o)
-> 스택에서 1-based position 형태로 몇 번째로 꺼내지는 지를 반환여기서 1-based position은 우리가 배열이나 list를 사용하면 인덱스가 0부터 시작하는 것을 알 수 있다.
하지만 1-based position은 인덱스가 1부터 시작하는 것을 의미한다.
search()메서드의 시간복잡도는 O(n)입니다.
※최상단의 요소부터 말단 요소까지 모두 확인해야 하기 때문
🧇 스택의 크기
Stack<String> stack_str = new Stack<>();
stack_str.push("box1");
stack_str.push("box2");
stack_str.push("box3");
stack_str.push("box4");
stack_str.push("box5");
System.out.println(stack_str.size()); // 5스택은 vector 클래스를 상속받기 때문에 vector 클래스의 메서드 중 하나인 크기를 반환하는 size()메서드를 사용할 수 있다.
👀 stack 클래스의 장단점
장점
먼저 위에서 설명했듯, stack은 vector 클래스를 상속받아 사용하기 때문에
아래와 같이 stack 주요 메서드들이 synchronized(동기화) 인것을 볼 수 있다.
※push(), empty() 메서드는 synchronized가 아니다.그렇기 때문에 Vector 클래스처럼 Thread-safe하다는 장점이 존재한다. 이 말은 여러 Thread가 동시에 접근하여도 안정성을 보장하는 의미이다.
단점
실제 스택 클래스를 살펴보면 위와 같은 문구를 볼 수 있다. 이를 간략히 해석해보면Deque 클래스를 사용하면 stack보다 완벽하고 일관된 LIFO 스택 연산을 제공한다고 한다.
그렇다면, 왜 이런 말을 하는 것인가?
먼저 stack은 vector 클래스는 상속해서 사용하기 때문에 이는 stack 클래스가 vector 클래스에 존재하는 메서드를 사용할 수 있다는 것이다.예를 들어 좀 설명을 하자면, vector 클래스의 메서드 중 add()메서드가 존재한다. add() 메서드에는 특정 인덱스에 값을 삽입할 수 있는 오버로딩된 메서드가 존재하는데,
만약 이를 사용하게 되면 stack에서도 원하는 위치에 값을 삽입할 수 있다는 소리이다. 그러면 단방향 입출력 구조로, 중간에 삽입 삭제가 안되는 LIFO 구조가 아니라는 소리인데
그렇게 되면 의도치 않은 동작이 발생할 수 있는 단점이 발생하는 것이다.이러한 객체 지향 프로그래밍에서 상속의 문제점으로 stack보다는 deque 클래스를 우선적으로 사용하라는 것이다.
또한, stack 클래스의 메서드에는 sychronized 키워드가 존재하는 데, 이를 통해 Thread-safe한 특징이 있다고 했다.
이 말은 멀티스레드 환경에서 여러 스레드가 동시에 접근하게 되면 locking 매커니즘을 통해 해당 영역이 해제될 때 까지 다른 스레드들이 대기를 해야 한다. 여기서 오버헤드가 발생할 수 있게 되는 것이다.
종합적으로 단점을 정리하자면
- vector 클래스를 상속하고 있기에, vector의 불필요한 메서드까지 사용이 가능하다. 이로인해 LIFO 구조가 깨지는 단점이 발생
- stack 메서드는 sychronized 키워드가 붙는데, 이는 Thread-safe한 특징으로 안정성을 줄 순있지만, 많은 스레드가 영역이 해제될 때까지 대기해야 하는 문제가 발생하여 오버헤드가 발생할 수 있다.
💜 참고자료
