자료 구조 (4) : 스택(Stack)

스택

목록의 끝(top)에서만 접근이 가능한 선형 자료 구조

 

• 주요 연산
  • push : 스택의 top에 데이터를 삽입
  • pop : 스택의 top의 데이터를 제거 후 반환
  • peek : 스택의 top의 데이터를 반환(제거하지 않음)
• 특징
  • 후입선출(LIFO) : 가장 최근에 삽입된 데이터가 먼저 제거
  • 스택에서 Top에서부터만 접근 가능
• 사용 상황(시간 순으로 이전 작업을 확인해야 하는 경우)
  • 괄호 검사
  • 되돌리기(Ctrl + z)
  • 사이트 뒤로 가기, 앞으로 가기
  • DFS
  • 함수 호출, 콜 스택
• 시간 복잡도

	단일
삽입(push)	O(1)
삭제(pop)	O(1)
조회(peek)	O(1)
조회(전체)	O(n)
크기(size)	O(1)

 

Stack 구현 예시

 

import java.util.*;

public class ListStack<T> {

  private LinkedList<T> list = new LinkedList<>();

  public ListStack() {}

  public ListStack(T elem) {
    push(elem);
  }

  public int size() {
    return list.size();
  }

  public boolean isEmpty() {
    return size() == 0;
  }

  public void push(T elem) {
    list.addLast(elem);
  }

  public T pop() {
    if (isEmpty()) throw new EmptyStackException();
    return list.removeLast();
  }

  public T peek() {
    if (isEmpty()) throw new EmptyStackException();
    return list.peekLast();
  }

  public int search(T elem) {
    return list.lastIndexOf(elem);
  }
}