[스택] 배열 기반 스택과 연결 리스트 기반 스택

Stack

• 스택은 후입선출이라는 규칙에 따라 데이터를 저장하고 접근하는 선형 자료구조
• 사용 예시 : 웹 브라우저의 뒤로 가기 기능, 문자열 역순, 괄호 검사, 실행 취소 기능, 재귀 함수 호출

 

 

스택의 개념

• 스택은 LIFO(Last In, First Out) 또는 FILO(First In, Last Out) 원칙에 따라 작동하는 자료구조
• 이 원칙은 가장 마지막에 삽입된 요소가 가장 먼저 제거된다는 것을 의미함

 

스택 자료구조의 ADT(추상 데이터 타입)

Push : 스택의 맨 위에 요소를 추가합니다.
Pop : 스택의 맨 위에서 요소를 제거하고, 그 요소를 반환합니다.
Peek : 스택의 맨 위 요소를 반환하지만, 제거하지 않습니다.
IsEmpty : 스택이 비어 있는지 확인합니다.

 

 

배열 기반 스택 (Stack 클래스)

구성요소

• 내부 배열 : 동적으로 크기가 조정될 수 있는 배열
• Top 포인터 : 스택의 최상위 요소(마지막으로 추가된 요소)를 가리키는 포인터 또는 인덱스
• Capacity : 내부 배열의 최대 크기
• Size : 현재 스택에 저장된 요소의 수

 

작동 원리

• 내부 배열 : Stack은 내부적으로 동적 배열을 사용하여 요소들을 저장. 이 배열은 Vector 클래스를 통해 구현되어 있으며, 필요에 따라 동적으로 크기가 조절됨
• Top 요소 : 스택의 최상단에 있는 요소(가장 최근에 추가된 요소)는 내부 배열의 마지막 요소로 관리
• Push 연산 : 새로운 요소를 스택의 맨 위에 추가할 때, 이 요소는 배열의 마지막에 추가. 필요한 경우 배열 크기 확장
• Pop 연산 : 스택의 맨 위에서 요소를 제거할 때, 배열의 마지막 요소가 제거되고 반환됨
• Peek 연산 : 스택의 최상단 요소를 확인하려면, 배열의 마지막 요소를 조회

 

주요 메서드

• push(E item) : 스택의 최상단에 요소를 추가
• pop() : 스택의 최상단에서 요소를 제거하고, 그 요소를 반환. 스택이 비어있는 경우 EmptyStackException을 던질 수 있음
• peek() : 스택의 최상단 요소를 반환하지만, 제거하지 않음. 스택이 비어있는 경우 EmptyStackException을 던질 수 있음
• isEmpty() : 스택이 비어있는지 여부를 반환. 비어있으면 true, 그렇지 않으면 false를 반환
• size() : 스택에 저장된 요소의 수를 반환

• search(Object o) : 지정된 객체가 스택에서 얼마나 멀리 있는지를 반환. 스택의 최상단부터 객체까지의 거리를 1로 시작하여 계산. 객체가 스택에 없으면 -1을 반환
• elementAt(int index) : 스택에서 지정된 인덱스에 있는 요소를 반환
• capacity() : 스택의 현재 용량을 반환. 이는 스택 내부의 배열이 담을 수 있는 요소의 최대 수를 나타냄
• ensureCapacity(int minCapacity) : 스택이 최소한 지정된 용량을 갖도록 함
• trimToSize() : 스택의 용량을 현재 스택 크기에 맞게 조정. 불필요한 메모리 사용을 줄일 수 있음

 

 

 

 

연결 리스트 기반 스택 (Deque 인터페이스)

구성요소

• 노드: 각 요소는 노드로 표현. 노드는 데이터와 다음 노드에 대한 참조(포인터)를 포함
• 헤드 포인터: 스택의 최상위 요소(맨 처음 또는 마지막에 추가된 요소)를 가리키는 포인터
• Size: 현재 스택에 저장된 요소의 수

 

작동 원리

• 노드 기반 구조: 스택의 각 요소는 연결 리스트의 노드로 표현. 각 노드는 데이터와 다음 노드를 가리키는 참조를 가짐
• 헤드를 사용한 연산: 스택 연산은 연결 리스트의 헤드(또는 테일)에서 수행됩니다. 새로운 요소는 리스트의 헤드에 추가되며, 헤드에서 제거됩니다.
• Push 연산: 새로운 요소를 스택의 맨 위에 추가할 때, 연결 리스트의 헤드에 새 노드를 추가
• Pop 연산: 스택의 맨 위에서 요소를 제거할 때, 연결 리스트의 헤드 노드를 제거하고 그 데이터를 반환
• Peek 연산: 스택의 최상단 요소를 확인할 때, 연결 리스트의 헤드 노드의 데이터를 조회

 

주요 메서드

• addFirst(E item) / offerFirst(E item): 스택의 최상단에 요소를 추가 (ArrayDeque에서 사용)
• removeFirst() / pollFirst(): 스택의 최상단에서 요소를 제거하고, 그 요소를 반환
• peekFirst(): 스택의 최상단 요소를 반환하지만, 제거하지 않음
• isEmpty(): 스택이 비어있는지 여부를 반환. 비어있으면 true, 그렇지 않으면 false를 반환
• size(): 스택에 저장된 요소의 수를 반환
• iterator() : 데크의 요소들을 순회하는 이터레이터를 반환
• descendingIterator() : 데크의 요소들을 역순으로 순회하는 이터레이터를 반환

 

 

 

배열 기반 스택 vs 연결 리스트 기반 스택

• 성능 차이
  • 배열 기반은 랜덤 액세스가 빠르지만 크기 조정에 비용이 듭니다.
  • 연결 리스트 기반은 요소 추가 및 제거가 빠르지만 랜덤 액세스가 느립니다.
• 용도
  • 배열 기반은 크기 변동이 적고, 빠른 인덱스 기반 접근이 필요할 때 적합합니다.
  • 연결 리스트 기반은 자주 크기가 변하거나 끝에서만 작업이 일어날 때 유리합니다.

 

스택의 장점과 단점

• 장점
  • 간단하고 사용하기 쉽습니다.
  • 데이터의 순서가 중요한 경우에 유용합니다.
• 단점
  • 크기가 제한적일 수 있습니다 (특히 배열 기반).
  • 중간 요소에 대한 접근이 비효율적입니다.

 

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」