Stack

스택의 특징

스택은 후입선출(Last in First out: LIFO)의 특징을 가진 자료구조이다.

후입선출이란 '나중에 들어온 것이 먼저 나간다'는 의미이다.

 

서 있는 긴 원통을 생각해보자.

여러 개의 원형 블럭을 원통에 넣는다. 그리고 원통에서 블럭을 하나 빼보자. 그 블럭은 가장 마지막에 들어간 블럭이다.

 

이것이 후입선출의 예시이며, 스택은 후입선출로 데이터를 관리한다.

 

스택은 대표적으로 페이지 뒤로가기, 실행 취소, 수식 괄호 검사 등에 사용된다.

 

스택 구현

스택 인터페이스 구현부

public interface StackInterface<T> {

	/**
	 * 스택의 최상단에 요소를 추가한다.
	 * @param element: 스택에 추가할 요소
	 * @return 스택에 추가된 요소
	 */
	T push(T element);

	/**
	 * 스택의 최상단 요소를 제거하고 반환한다.
	 *
	 * @return 제거된 요소
	 */
	T pop();

	/**
	 * 스택의 최상단 요소를 제거하지 않고 반환한다.
	 * @return 스택 맨 위에 있는 요소
	 */
	T peek();

	/**
	 * 스택 최상단과 목표 요소의 거리를 반환
	 * @param element: 목표 요소
	 * @return 목표 요소와 스택 최상단의 거리
	 */
	int search(T element);

	/**
	 * 스택의 요소 개수를 반환
	 * @return 스택의 요소 개수
	 */
	int size();

	/**
	 * 스택의 모든 요소를 삭제
	 */
	void clear();

	/**
	 * 빈 스택인지 여부를 반환
	 * @return 빈 스택이면 true, 아니면 false
	 */
	boolean empty();
}

 

스택 구현부

스택의 메소드 중에 search(...)를 주의하자.

search(...)는 목표 데이터의 인덱스를 반환한다. 

 

일반적인 자료구조는 인덱스는 맨 앞의 데이터로부터 목표 데이터의 거리를 반영한다.

그러나 스택은 인덱스는 스택의 최상단 데이터, 즉 맨 뒤의 데이터로부터 목표 데이터의 거리를 반영한다.

 

[1, 2, 3, 4]의 순서로 데이터가 저장되어 있다면, 4의 인덱스는 0이다.

public class Stack<T> implements StackInterface<T> {

	private static final int DEFAULT_CAPACITY = 10; // 기본 용적 크기

	private T[] array; // 저장 공간
	private int size; // 요소 개수

	// 기본 용적 크기: 0
	@SuppressWarnings("unchecked")
	public Stack() {
		this.array = (T[]) new Object[0];
		this.size = 0;
	}

	// 기본 용적 크기: capacity
	@SuppressWarnings("unchecked")
	public Stack(int capacity) {
		this.array = (T[]) new Object[capacity];
		this.size = 0;
	}

	// 용적 크기 재조정
	@SuppressWarnings("unchecked")
	private void resize() {

		// 기본 용적 크기: 0
		if (array.length == 0) {
			array = (T[]) new Object[DEFAULT_CAPACITY];
			return;
		}

		// 용적 크기 == 요소 개수
		if (array.length == size) {
			int newCapacity = array.length * 2;

			array = Arrays.copyOf(array, newCapacity);
			return;
		}

		// 요소 개수 < 용적 크기/2
		if ((array.length / 2) > size) {
			int newCapacity = array.length / 2;

			array = Arrays.copyOf(array, Math.max(DEFAULT_CAPACITY, newCapacity));
		}
	}

	// 스택 최상단에 요소 추가
	@Override
	public T push(T element) {
		// 요소 추가 전에 용적 크기 재조정
		resize();

		array[size] = element;
		size++;

		return element;
	}

	// 스택 최상단 요소를 제거하고 반환
	@Override
	public T pop() {
		// 요소가 없을 경우 예외 발생
		if (size == 0) {
			throw new EmptyStackException();
		}

		// 삭제될 요소를 반환하기 위한 임시 저장
		T element = array[size - 1];
		// 삭제될 요소 삭제
		array[size - 1] = null;

		size--;
		resize();

		return element;
	}

	// 스택 최상단 요소 반환
	@Override
	public T peek() {
		// 요소가 없으면 예외 발생
		if (size == 0) {
			throw new EmptyStackException();
		}

		return array[size - 1];
	}

	// 스택 최상단과 목표 요소의 거리 반환(시작 값: 1)
	@Override
	public int search(T element) {
		// 저장된 요소가 없으면 예외 발생
		if (size == 0) {
			throw new EmptyStackException();
		}

		// 목표 요소가 null이면 예외 발생
		if (element == null) {
			throw new IllegalArgumentException();
		}

		// 스택 최상단부터 순회하면서 요소 탐색
		for (int i = size - 1; i >= 0; i--) {
			// 요소를 찾으면 거리 반환
			if (array[i].equals(element)) {
				return size - i;
			}
		}

		// 목표 요소가 없을 경우 -1 반환
		return -1;
	}

	// 저장된 요소 개수 반환
	@Override
	public int size() {
		return size;
	}

	// 저장 공간 비우기
	@SuppressWarnings("unchecked")
	@Override
	public void clear() {
		this.array = (T[]) new Object[size];
		size = 0;
		// 용적 크기 -> 기존 크기/2
		resize();
	}

	// 스택이 비어있다면 true, 비어있지 않다면 false
	@Override
	public boolean empty() {
		return size == 0;
	}

	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();

		stringBuilder.append("[");

		for (int i = 0; i < size; i++) {
			stringBuilder.append(" ").append(array[i]);
		}

		stringBuilder.append(" ]");

		return stringBuilder.toString();
	}
}

 

실제 사용

public class Main {

	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<>();

		for (int i = 0; i < 10; i++) {
			stack.push(i + 1);
		}

		System.out.println("stack = " + stack);
		//stack = [ 1 2 3 4 5 6 7 8 9 10 ]

		///////////////////////////////////////////////////////////////////////
		for (int i = 0; i < 10; i++) {
			System.out.print(stack.search(i + 1) + " ");
		}

		System.out.println();
		// 10 9 8 7 6 5 4 3 2 1

		///////////////////////////////////////////////////////////////////////
		int peek = stack.peek();
		System.out.println("peek = " + peek); // peek = 10
		System.out.println("stack = " + stack); // stack = [ 1 2 3 4 5 6 7 8 9 10 ]

		///////////////////////////////////////////////////////////////////////
		int pop = stack.pop();
		System.out.println("pop = " + pop); // pop = 10
		System.out.println("stack = " + stack); // stack = [ 1 2 3 4 5 6 7 8 9 ]

		///////////////////////////////////////////////////////////////////////
		System.out.println("stack.empty() = " + stack.empty()); // stack.empty() = false
		stack.clear();
		System.out.println("stack.empty() = " + stack.empty()); // stack.empty() = true
	}
}

---