[묘공단] 스택 이야기

지금까지 묘공단 관련 포스팅을 velog에서 했었는데 이제 티스토리로 옮기고 싶어서 여기에 적는다.

 

자료구조하면 보통은 스택부터 이야기를 들을 것이다.

매우 쉽고 기본이 되니까.

스택은 ADT(Abstract Data Type)다.

구현된 부분이 없는 일종의 인터페이스 같은 것이다.

ADT의 구현은 자바에서 자바 콜렉션 프레임워크에 되어 있다.

 

근데 스택은 콜렉션에 없다.

스택 클래스가 따로 있다.

그리고 덱 ADT가 구현된 ArrayDeque을 스택처럼 쓸 수 있다(이건 큐처럼도 쓴다. 양방이 다 뚫려 있어서.).

 

이게 앞으로 나올 내용을 이해하기 위해 최소한으로 알고 있으면 될 내용이었다.

---

1. 자바에서 스택을 쓸 경우는 뭐가 있을까?

 

1. 후입선출(LIFO) 구조가 필요한 경우:
   1. 웹 브라우저의 뒤로 가기 기능.
   2. 실행 취소(undo) 기능을 구현할 때.
   3. 소프트웨어에서 마지막으로 입력된 데이터를 처리할 때.
2. 재귀 알고리즘:
   1. 재귀적 함수 호출을 스택을 이용해 비재귀적으로 구현할 때.
3. 문자열 및 괄호 검사:
   1. 괄호의 쌍이 올바르게 닫혔는지 확인할 때 (예: {}, [], ()).
4. 역순 문자열 생성:
   1. 문자열을 거꾸로 뒤집을 때.
5. 수식 계산:
   1. 후위 표기법(Postfix notation)이나 중위 표기법(Infix notation)을 계산할 때.
6. 메모리 관리:
   1. 프로그램의 호출 스택(call stack)에서 메소드 호출과 리턴을 관리할 때.
7. 깊이 우선 탐색(DFS):
   1. 그래프의 깊이 우선 탐색에서 사용할 때.
8. 경로 탐색:
   1. 미로를 풀거나 하나의 경로를 역추적할 때.

라고 하는데... 골든래빗의 '코딩 테스트 합격자 되기 - 자바 편'에서는 괄호 검사 관련한 내용이 좀 많이 나왔다.

실제 프로그래머스에서는 문자열 검사나 역순 문자열 생성 부분을 지금까지 많이 접했다.

레벨0을 풀고 있어서 그런 쉬운 것만 접한 걸 수도 있겠다.

어쨌든 지금까지는 굳이 스택으로 풀어야겠다는 생각을 못(안) 했는데(어떻게 쓸 줄 모르니까.) 여기서 정리해서 앞으로 자주 쓰려고 한다.

---

자바로 코테 풀 때 스택 쓴다고 하면 Stack 클래스 아니면 ArrayDeque 클래스를 이용하면 된다.

Stack 보다 ArrayDeque이 더 성능이 좋다고 하니 되도록 이걸 이용하면 좋을 거 같다.

 

2. 코테 풀 때 스택 클래스에 대해 알아야 할 정도의 내용은 어떤 게 있을까?

 

스택 클래스는 Vector 클래스를 상속받아 구현된 클래스다.

 

'코테 풀 때 알아야 할 내용'이라는 건 쉽게 말해, 이걸 '어떻게 쓰느냐'에 대한 것이다.

 

• 생성: 스택 객체를 생성하는 것은 간단하다. Stack<E> stack = new Stack<>(); 하면 끝이다.
• 주요 메서드:
  • boolean empty(): 스택이 비어있으면 true를 반환한다.
  • E peek(): 스택의 맨 위에 있는(가장 마지막에 추가된) 요소를 반환하지만 제거하지는 않는다.
  • E pop(): 스택의 맨 위에 있는 요소를 제거하고 반환한다.
  • E push(E item): 스택의 맨 위에 요소를 추가한다.
  • int search(Object o): 주어진 객체가 스택에 위치한 곳의 1부터 시작하는 위치 인덱스를 반환한다(인덱스를 0부터 적용 안 하고 1부터 적용한다는 얘기다.). 객체가 스택에 없으면 -1을 반환한다.

'스택'의 메서드는 진짜 저게 단데 저게 다는 아니다(?).

바로 상속한 벡터에서 사용 가능한 메서드들이 있기 때문.

 

METHOD	DESCRIPTION
add(Object obj)	Appends the specified element to the end of this Vector.
add(int index, Object obj)	Inserts the specified element at the specified position in this Vector.
addAll(Collection c)	Appends all of the elements in the specified Collection to the end of this Vector,  in the order that they are returned by the specified Collection’s Iterator.
addAll(int index, Collection c)	Inserts all the elements in the specified Collection into this Vector at the specified position.
addElement(Object o)	Adds the specified component to the end of this vector, increasing its size by one.
capacity()	Returns the current capacity of this vector.
clear()	Removes all the elements from this Vector.
clone()	Returns a clone of this vector.
contains(Object o)	Returns true if this vector contains the specified element.
containsAll(Collection c)	Returns true if this Vector contains all the elements in the specified Collection.
copyInto(Object []array)	Copies the components of this vector into the specified array.
elementAt(int index)	Returns the component at the specified index.
elements()	Returns an enumeration of the components of this vector.
ensureCapacity(int minCapacity)	Increases the capacity of this vector, if necessary, to ensure that it can hold  at least the number of components specified by the minimum capacity argument.
equals()	Compares the specified Object with this Vector for equality.
firstElement()	Returns the first component (the item at index 0) of this vector.
get(int index)	Returns the element at the specified position in this Vector.
hashCode()	Returns the hash code value for this Vector.
indexOf(Object o)	Returns the index of the first occurrence of the specified element in this vector, or -1  if this vector does not contain the element.
indexOf(Object o, int index)	Returns the index of the first occurrence of the specified element in this vector, searching forwards from the index, or returns -1 if the element is not found.
insertElementAt(Object o, int index)	Inserts the specified object as a component in this vector at the specified index.
isEmpty()	Tests if this vector has no components.
iterator()	Returns an iterator over the elements in this list in proper sequence.
lastElement()	Returns the last component of the vector.
lastIndexOf(Object o)	Returns the index of the last occurrence of the specified element in this vector, or -1  If this vector does not contain the element.
lastIndexOf(Object o, int index)	Returns the index of the last occurrence of the specified element in this vector,  searching backward from the index, or returns -1 if the element is not found.
listIterator()	Returns a list iterator over the elements in this list (in proper sequence).
listIterator(int index)	Returns a list iterator over the elements in this list (in proper sequence),  starting at the specified position in the list.
remove(int index)	Removes the element at the specified position in this Vector.
remove(Object o)	Removes the first occurrence of the specified element in this Vector If the Vector does not contain the element, it is unchanged.
removeAll(Collection c)	Removes from this Vector all of its elements that are contained in the specified Collection.
removeAllElements()	Removes all components from this vector and sets its size to zero.
removeElement(Object o)	Removes the first (lowest-indexed) occurrence of the argument from this vector.
removeElementAt(int index)	Deletes the component at the specified index.
removeRange(int fromIndex, int toIndex)	Removes from this list all the elements whose index is between fromIndex, inclusive, and toIndex, exclusive.
retainAll(Collection c)	Retains only the elements in this Vector that are contained in the specified Collection.
set(int index, Object o)	Replaces the element at the specified position in this Vector with the specified element.
setElementAt(Object o, int index)	Sets the component at the specified index of this vector to be the specified object.
setSize(int newSize)	Sets the size of this vector.
size()	Returns the number of components in this vector.
subList(int fromIndex, int toIndex)	Returns a view of the portion of this List between fromIndex, inclusive, and toIndex, exclusive.
toArray()	Returns an array containing all of the elements in this Vector in the correct order.
toArray(Object []array)	Returns an array containing all of the elements in this Vector in the correct order; the runtime  type of the returned array is that of the specified array.
toString()	Returns a string representation of this Vector, containing the String representation of each element.
trimToSize()	Trims the capacity of this vector to be the vector’s current size.

 

뭐 이런 게 있는데 말입니다... 이것을 제가 다 한글화하기가 매우 힘들군요...

보니까 구조가 이러한데, ArrayList도 List를 구현한 거라서 저 메서드 다 같이 쓸 수 있을 것 같다.

그러니 언제 한 번 주요 메서드들 정리를 좀 해야겠다.

코테 칠 때 보통은 그냥 만들어진 API 잘 갖다 쓰면 장땡이더라고...

• 동기화: Stack 클래스의 메서드들은 동기화되어 있어서 멀티 스레드 환경에서 안전하다. 그러나 이로 인해 단일 스레드 환경에서는 ArrayDeque에 비해 성능이 낮을 수 있다.
• 상속 구조: Stack은 Vector를 확장하므로 Vector의 모든 메서드와 필드를 상속받는다. 이는 Stack이 동기화된 메서드를 가지고 있고 내부적으로 배열을 사용하여 요소를 관리한다는 것을 의미한다.
• 성능: Stack은 동기화 때문에 단일 스레드 애플리케이션에서는 ArrayDeque보다 성능이 떨어질 수 있으나, 멀티 스레드 환경에서 안전하게 사용할 수 있다.
• 대안: java.util.Deque 인터페이스를 구현하는 ArrayDeque는 스택의 행동을 모방할 수 있으며, Stack에 비해 더 빠른 성능을 제공한다. 또한 스택 기능 뿐만 아니라 큐 기능도 제공한다.

코딩 테스트 또는 일반적인 사용을 위해 Stack 대신 ArrayDeque를 사용하는 것이 좋다. 하지만 레거시 코드를 다루거나, 동기화된 스택이 필요한 특정 멀티 스레드 환경에서는 Stack 클래스를 사용할 수 있다.

 

정도면 기본적인 건 다 정리가 된 것 같다.

이 정도만 알아도 코테에서 스택 바로 쓸 수 있다.

---

이제 Deque이랑 ArrayDeque을 좀 봐야 되는데 내용이 길어질 것 같으니 새 페이지에서 정리하겠다.

 

골든래빗 출판사의 묘공단 스터디를 진행하며

코딩 테스트 합격자 되기 - 자바 편 프로그래머스 제공 97 문제로 완벽 대비를 읽고 정리한 내용입니다.