스택(Stack)

스택(Stack)이란?

---

스택이란 먼저 입력한 데이터를 가장 나중에 꺼낼 수 있는 자료구조이다.

 

먼저 입력한 데이터는 아래에 깔리고 그 위에 차곡차곡 데이터가 쌓인다. 

데이터를 꺼낼려면 가장 위에 쌓인 데이터를 꺼내야 하므로 가장 마지막에 입력된 데이터가 꺼내진다.

이러한 규칙을 선입후출, First In Last Out(FILO)라고한다.

스택에 데이터를 삽입하는 연산을 Push, 스택에서 데이터를 꺼내는 연산을 Pop이라고 한다.

스택의 ADT

메서드 및 변수	설명
boolean isFull()	스택에 데이터의 갯수가 MaxSize와 같다면 true, 그렇지 않다면 false를 반환한다.
boolean isEmpty()	스택에 데이터가 없는 경우 true를 반환, 그렇지 않으면 false를 반환한다.
void push(ItemType item)	스택에 데이터를 푸시한다.
ItemType pop()	스택에 가장 위에 위치한 데이터를 하나 꺼내고 그 데이터를 반환한다.
int top	스택에 가장 최근에 저장된 데이터의 위치
ItemType[] stack	스택의 데이터를 관리하는 배열
int maxSize	스택에 저장할 수 있는 최대 데이터 갯수

Push 세부 동작 방식

1. 스택에 데이터가 꽉찼는지 확인하기 위해 isFull()를 호출
2. 꽉차지 않았다면 top을 1 증가시킨다.
3. 배열의 top 위치에 데이터를 저장한다.

Pop 세부 동작 방식

1. 스택에 데이터가 비어있는지 확인하기 위해 isEmpty()를 호출
2. top을 1 감소시킨다.
3. 이와 동시에 기존 top 위치에 있던 데이터를 꺼낸다.

---

자바의 스택 클래스

---

스택을 직접 구현할 수 있겠지만 자바에선 Stack 클래스를 제공해준다.

Stack<ItemType> stack = new Stack<>():

 

Stack 클래스의 주요 메서드를 알아보자

메서드	설명
boolean isEmpty()	스택에 데이터가 없는 경우 true를 반환, 그렇지 않으면 false
void push(ItemType item)	스택에 데이터를 푸시한다.
ItemType pop()	스택에 가장 위에 위치한 데이터를 하나 꺼내고 그 데이터를 반환한다.
ItemType peek()	스택에 가장 위에 위치한 데이터를 반환환다.(데이터를 꺼내지는 않음)
int size()	스택에 저장된 데이터 갯수를 반환한다.

 

자바의 Stack클래스는 동적으로 크기를 할당하기 때문에 isFull() 메서드가 별도로 존재하지 않는다. 

대신 Collection 클래스에서 제공하는 size() 메서드를 통해 데이터의 크기를 알 수 있다.

 

연습문제 풀이

[프로그래머스] 올바른 괄호

[프로그래머스] 10진수를 2진수로 변환하기

해당 포스트는 『코딩 테스트 합격자 되기 - 자바편』을 참고하여 작성되었습니다.