> [JAVA 자료구조] Stack(스택) 개념과 사용

관리 메뉴

개발 기록

> [JAVA 자료구조] Stack(스택) 개념과 사용 본문

알고리즘 & 자료구조/자료구조

> [JAVA 자료구조] Stack(스택) 개념과 사용

1z 2020. 10. 1. 16:06

https://www.geeksforgeeks.org/stack-data-structure

■

1. 개념

마지막에 삽입된 요소가 먼저 나오는 후입선출(Last In First Out; LIFO)의 선형 데이터 구조.

ex.책 더미: 새 책 맨 위에 올린다. 위에 있는 책을 제거하지 않고는 중앙, 아래 책을 가져갈 수 없다.

(1) 사용사례

① 함수 호출 관리

- 함수 호출 및 반환 추적 : 함수가 호출될 때마다 해당 함수 정보를 스택에 push하고, 함수가 반환될 때 해당 정보를 pop하여 함수 호출 순서를 추적한다.

- 재귀 함수 처리

- 함수의 중첩 호출 처리

- 예외 처리

② 실행 취소 / 다시 실행 작업

③ 표현식 평가 및 구문 분석 : 후위 표기법, 수식 트리 구성

④ 웹 브라우저의 '뒤로가기' 기능 : 각 페이지의 URL 이 스택에 푸시 되고, 뒤로 버튼을 누르면 가장 최근의 url 이 팝업된다.

⑤ 깊이 우선 탐색(DFS)

(2) 장점/ 단점

☞ 장점

- 단순성: 간단하고 이해하기 쉬운 데이터 구조

- 효율성: 스택의 푸시 및 팝 작업은 일정한 시간 (O(1)) 으로 수행될 수 있어 데이터에 대한 효율적인 액세스 제공

- 제한된 메모리 사용량: 스택은 푸시된 요소만 저장하면 되므로 다른 데이터 구조에 비해 메모리 효율성이 높다.

☞ 단점

- 제한된 액세스: 맨 위에 요소만 액세스할 수 있으므로 특정 순서로 요소에 접근할 수 없다.

- 고정 크기 스택: 오버플로 오류(가득 찬 스택에 요소를 추가할 경우), 언더플로 오류(비어 있는 스택에 요소를 제거할려고 할 경우)

* (<->동적 크기 스택: 스택이 가득 차면 새 요소를 수용할 수 있도록 자동으로 크기가 늘어나고, 스택이 비어 있으면 크기가 줄어든다.)

■

2. 사용법

java.util.Stack 클래스를 통해 스택을 구현할 수 있다.

* Stack 클래스는 Vector 클래스를 상속받았기 때문에, Vector 클래스의 메서드를 사용할 수 있다.

(1) 'Stack' 객체 생성

import java.util.Stack; 

//int형의 빈 스택 생성
Stack<Integer> stack = new Stack<>();

(2) 요소 추가: push()

스택에 순서대로 10, 20, 30을 추가합니다. 스택의 맨 위에 요소가 추가된다.

Stack<Integer> stack = new Stack<>(); 
stack.push(10);
stack.push(20);
stack.push(30);

(3) 요소 제거 및 반환: pop()

pop() 메소드는 스택의 맨 위 요소를 제거하고 반환한다. 아래의 예제는 30을 제거하고 반환한다.스택의 값을 모두 제거하고싶다면 clear() 메서드를 사용하면 된다.

int topElement = stack.pop();
System.out.println("Popped Element: " + topElement);

//전체 값 제거
stack.clear();

(4) 맨 위 요소 확인: peek()

peek() 메소드는 스택의 맨 위 요소를 확인한다. 스택의 상태를 변경하지 않고도 요소를 확인할 수 있으며 가장 마지막에 들어간 값이 출력된다.

int topElement = stack.peek();
System.out.println("Top Element: " + topElement);

(5) 기타 메서드

- isEmpty(): 스택이 비어있는지 여부 확인 => 스택이 비어있다면 true, 그렇지 않다면 false 반환

- search(Object): 요소를 검색 => 맨 위(맨 위가 1)부터 순차적으로 요소를 검색하며 검색이 성공하면 해당 요소의 위치를 반환하고 검색이 실패하면 -1을 반환한다.

Stack<String> stack = new Stack<>();

// 스택에 요소 추가
stack.push("Apple");
stack.push("Banana");
stack.push("Orange");

// 스택이 비어있는지 확인
if (stack.isEmpty()) {
    // 스택에서 요소 검색
    int index1 = stack.search("Banana");
    System.out.println("Index of 'Banana': " + index1); // 출력: Index of 'Banana': 2
}

■

3 . Stack 과 Vector

★ Stack 클래스는 Vector 클래스를 확장하여 구현되었기 때문에 Vector 클래스의 메서드를 사용하여 내부적으로 배열처럼 요소를 조작할 수 있다. 그러나 스택의 후입선출(LIFO)의 구조를 유지해야 하므로, 스택의 동작 방식에 맞게 공개된 메서드(push(), pop(), peek() 등)를 통해 요소를 추가하고 제거해야 한다.

★ 내부적으로 배열을 사용하고 확장한 것은 구현의 편의성을 위한 것이지, 스택의 동작 방식을 무시하거나 LIFO 계약을 위반하는 것을 허용하는 것은 아니다.

★ Stack 클래스보다는 Deque 인터페이스와 그 구현체를 사용하는 것을 권장하고 있다.

// ArrayDeque: Deque 인터페이스 구현클래스
Deque<Integer> stack = new ArrayDeque<>(); 
stack.push(10);
stack.push(20);
int topElement = stack.pop();
System.out.println("Top Element: " + topElement); // 출력: Top Element: 20