2015년 1월 7일 수요일

[자료 구조] 스택 (Stack)

자바(Java)로 구현한 스택 예제


스택(Stack) 컨셉
스택(Stack) 컨셉

스택(Stack)이란 무었인가?

스택은 같은 타입의 자료를 "하나 다음 하나"라는 컨셉으로 순차적으로 저장하는 직선형 자료 구조이다. 우리가 스택에서 자료를 추출하고 삽입할 때 우리는 순렬의 끝에만 접근이 가능하다. 위 그림을 잠시 보자. 새로운 데이터는 스택의 최상위에 위치하게되고, 데이터 추출시, 우리는 오직 가장 최근에 삽입된 데이터만(최상위) 접근이 가능하다. 이 이유때문에 스택은 보통 "LIFO(Last In First Out)" 구조 라는, 가장 최근에 들어간게 가장 먼져 나온다는 뜻을 가진 어문으로 표현되기도 한다.

스택(Stack)은 실제로 어디에 사용되는가?

  • Operating Systems 
    • 프로그램에서 불러지는 함수(Method)들을 모두 Stack 이라는 자료형에 저장한다.
  • Compilers(컴파일러)
    • 컴파일러에서 수학기호들을 기계어(Machine Code)로 변환시, 괄호들을 매칭하거나 할 때.
  • JVM(Java Virtual Machine)자바 가상 머신
    • 자바 프로그램이 실행될 때 사용되는 JVM 에서도 스택은 사용된다. 각각의 스레드는 1개의 스택을 가지고 모든 메소드들을 트랙킹한다. 새로운 메소드들이 호출 될 때 마다, 새로운 프레임이 스택에 삽입되고, 메소드가 끝날 때 마다 스택에서 제거된다

스택(Stack)은 어떻게 구현될수 있을까?

앞에서 다룬 링크드 리스트와 달리 스택(Stack)은 추상 자료형(Abstract Data Type)이다. 추상 자료형이란 수학적 모델을 가진 자료형이고, 이는 곧 매우 다양한 방법으로 구현될 수 있음을 의미한다. 가장 자주 쓰이는 2가지 구현방법들은, ArrayList(어레이리스트)와 LinkedList(링크드 리스트)이다. 스택은 몇가지 필수적인 메소드들을 가지고 있는데 이는 아래와 같다
  • pop(추출)
    • 가장 최 상위에 위치한 자료를 추출한 후에 스택에서 제거한다
    • 이 작업은 O(1)의 복잡도를 가진다
  • push(삽입)
    • 스택의 최 상위에 새로운 자료를 삽입한다
    • 이 작업은 O(1)의 복잡도를 가진다
  • isEmpty
    • 스택이 empty 상태인지 확인한다
  • clear
    • 스택에 존재하는 모든 자료들을 삭제한다
  • peek
    • 가장 최 상위에 위치한 자료를 추출한다
    • pop 메소드와는 달리 스택에서 제거하지는 않는다.
    • 이 작업은 O(1)의 복잡도를 가진다

스택 Push 메소드
스택 Push 메소드

스택 Pop 메소드
스택 Pop 메소드

아래는 자바의 어레이리스트 api(java.util.ArrayList)로 구현한 스택(Stack) 자료형 이다


public class StackWithArrayList {
import java.util.*;//import arrayList

public class StackWithArrayList {
 private ArrayList stack;

 /**
  * 스택 인스턴스를 생성하는 컨스트럭터(Constructor)
  */
 public StackWithArrayList() {
  stack = new ArrayList();
 }

 /**
  * 스택을 최소 사이즈 s 로 생성한다
  * 
  * @param s 구현할 스택의 최소 사이즈
  */
 public StackWithArrayList(int s) {
  stack = new ArrayList();
  stack.ensureCapacity(s);
 }

 /**
  * 스택을 비운다
  */
 public void clear() {
  stack.clear();
 }

 /**
  * 스택이 Empty 상태인지 확인한다
  * 
  * @return 스택이 Empty 상태이면 true값을, 아니면 false 값을 반환한다.
  */
 public boolean isEmpty() {
  return stack.isEmpty();// 또는 "stack.size() == 0"를 이용할수도 있다
 }

 /**
  * 새로운 요소를 삽입한다
  * 
  * @param e 삽입될 새로운 요소
  */
 public void push(Object e) {
  stack.add(e);// ArrayList의 가장 마지막 index 에 새로운 요소를 삽입한다
 }

 /**
  * 스택에서 가장 최 상위에 위치한 데이터를 추출한 후 제거한다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object pop() {
  if (isEmpty()) {// 우선 스택이 empty 인걸 확인한 하고
   throw new EmptyStackException();
   // 그렇다면 Exception 을 던진다
  } else {
   return stack.remove(stack.size() - 1);
   // ArrayList.remove 메소드는 어레이에서 주어진 인덱스의 데이터를 제거후, 리턴한다 
  }
 }

 /**
  * 스택에서 가장 최상위에 위치한 데이터를 리턴한다, pop 메소드와는 달리 제거하지 않는다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object peek() {
  if (isEmpty()) {
   throw new EmptyStackException();

  } else {
   return stack.get(stack.size() - 1);
   // ArrayList.get 메소드는 주어진 인덱스에 저장된 값을 반환한다.
  }
 }
}


아래는 자바의 링크드리스트 api(java.util.LinkedList)로 구현한 스택(Stack) 자료형 이다

import java.util.EmptyStackException;
import java.util.LinkedList;

public class StackWithLinkedList {
 private LinkedList stack;

 public StackWithLinkedList() {
  this.stack = new LinkedList();
 }

 /**
  * 스택을 비운다
  */
 public void clear() {
  stack.clear();
 }

 /**
  * 스택이 Empty 상태인지 확인한다
  * 
  * @return 스택이 Empty 상태이면 True 값을, 아니면 false 값을 리턴한다
  */
 public boolean isEmpty() {
  return stack.isEmpty();// 또는 "stack.size() == 0" 구문을 이용할 수도 있다
 }

 /**
  * 스택에 새로운 데이터를 삽입한다.
  * 
  * @param e 삽입할 데이터
  */
 public void push(Object e) {
  stack.addLast(e);// 어레이리스트의 가장 마지막 인덱스에 추가한다.
 }

 /**
  * 스택에서 가장 최 상위에 위치한 데이터를 추출한 후 제거한다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object pop() {
  if (isEmpty()) {// 우선 스택이 empty 상태인지 확인한후
   throw new EmptyStackException();
   // empty 상태라면 Exception 을 던진다.
  } else {
   return stack.removeLast();
   // ArrayList.removeLast 메소드는 가장 마지막 인덱스에 위치한 자료를 어레이에서 리턴하고 제거한다
  }
 }

 /**
  * return 스택에서 가장 최상위에 위치한 데이터를 리턴한다, pop 메소드와는 달리 제거하지 않는다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object peek() {
  if (isEmpty()) {// 우선 스택이 empty 상태인지 확인한후
   throw new EmptyStackException();
   // empty 상태라면 Exception 을 던진다.
  } else {
   return stack.getLast();
   // ArrayList.getLast 메소드는 가장 마지막 인덱스에 위치한 데이터를 리턴한다.
  }
 }
}

댓글 1개:

  1. 잘 보았습니다.
    http://blog.daum.net/andro_java/913
    감사합니다.

    답글삭제