알고리즘 시리즈 중 첫번째로 'Stack' 에 대해 알아보도록 하겠습니다!
Stack을 제가 이해한 바로 간단하게 설명하자면, 놀이공원 가서 줄을 섰는데 제일 마지막에 온 사람이 첫번째로 온 사람보다 먼저 입장하는 알고리즘입니다. 상식적이지는 않죠? 더 쉽게 설명하면 여러분들이 평소에 자주 사용하고 있는 ctrl + z 실행 취소 단축키를 생각해보세요. 작업을 하다가 지금 적었던 내용을 지웠을 때, 해당 단축키를 누르면 지금 적었던 내용이 바로 나올 겁니다. 가장 처음에 썼던 제목이 나오는 게 아니라요!
1. Stack의 성격
- 나중에 저장한 데이터가 먼저 나오는 구조 👉 L I F O
- ⭐ LIFO : Last In First Out (마지막 데이터의 관점)
- 또는 FILO : First in Last Out (처음 들어온 데이터의 관점)
2. Stack의 쓰임
- 바로 넣었다가 거꾸로 정렬된 데이터를 꺼내쓰고 싶을 때
3. Stack이 지원하는 메소드
(1) pop( ) : 마지막에 들어온 데이터를 가져오고 지움
(2) push ( ) : 새로운 데이터를 원래 있던 Stack에 맨 위에 추가해서 쌓음
(3) peek( ) : 마지막에 있는 데이터를 알려줌
(4) isEmpty( ) : stack에 데이터가 있는지 없는지 확인함
자, 여기서 하나의 궁금증이 생깁니다. 그럼 마지막 에 있는 데이터 말고 그 나머지 데이터 요소들은 못 보는 걸까?
정답은 네, 맞습니다. 입니다. Stack은 데이터의 추가, 제거, 마지막에 들어온 데이터만 확인이 가능합니다. 나머지 요소들을 확인하거나 수정하는 기능을 제공하지 않습니다. 이해가 안될 수도 있는데 이것 말고도 다른 알고리즘들도 차차 살펴볼테니 이런 자료구조 형식도 있구나 하고 넘어가시면 됩니다!
4. Stack 구현 방법
(1) 1차원 배열
- 장점 : 구현이 쉽다
- 단점 : 추가 될 요소의 갯수를 미리 알아서 해당 크기만큼의 배열을 생성해야함
(2) 리스트
- 장점 : 1차원 배열보다 동적으로 작동하기 때문에 저장될 갯수의 제한이 없음
- 단점 : 구현이 어려움
5. Stack 실습
그러면 Stack을 JAVA에서 구현해보겠습니다
(보편적으로는 코드가 간단한 파이썬에서 알고리즘 테스트를 많이 하지만 저는 JAVA를 배워서 JAVA로 구현해보겠습니다)
먼저, Stack을 구현하는 Class를 만들어볼까요?
import java.util.EmptyStackException;
//(1) stack class 만들기
class Stack<T> {
//(2) 같은 type을 받는 노드를 생성
class Node<T>{
//(3) 데이터 생성
private T data;
//(4) 다음 노드 생성
private Node<T> next;
//(5) 생성자 생성 : 해당 타입의 데이터를 하나 받아서
public Node(T data) {
//(6) 내부 변수에 저장
this.data = data;
}
}
//(7) 멤버 변수 만들기
private Node<T> top;
//(8) 함수 구현
//(8-1) pop() : 맨 위에 있는 노드를 가져오는 함수
public T pop() {
//만약에 맨 위에 있는 노드가 null이면 exception 처리
if(top == null) {
throw new EmptyStackException();
}
//맨 위에 있는 데이터를 반환하기 전,
//맨 위 바로 아래에 있는 데이터를 top으로 만들어야 하기 때문에
//그 데이터의 주소를 가져오자!
//데이터 백업
T item = top.data;
//top의 다음 요소를 top으로 만듦
top = top.next;
//데이터 반환
return item;
}
//(8-2) push() : 데이터를 추가하는 함수
public void push(T item) {
//push할 T type의 item을 받아서 그 item으로 새 노드 생성
Node<T> t = new Node<T>(item);
//top앞에 해당 노드를 위치시킴
t.next = top;
//이제 그 노드가 top이 됨
top = t;
}
//(8-3) peek() : T type의 데이터를 반환하는 함수
public T peek() {
//만약에 맨 위에 있는 노드가 null이면 exception 처리
if(top == null) {
throw new EmptyStackException();
}
//null이 아니면 현재 top이 가지고 있는 데이터를 반환
return top.data;
}
//(8-4) isEmpty() : 요소가 비어있는지 확인
public boolean isEmpty() {
return top == null ;
}
}
내용이 도움이 되셨으면 좋겠습니다!
나중에 Stack으로 알고리즘 문제를 풀어보는 글도 올리겠습니다.
봐주셔서 감사합니다 😊
