[자료구조] 스택(Stack)이란?

📌 스택이란 무엇인가?

 스택(Stack)은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입 선출(LIFO, Last In First Out), 마지막에 들어온 것이 먼저 나간다는 뜻이다. 스택에 데이터를 넣는 작업을 푸시(push), 꺼내는 작업을 팝(pop)이라고 한다. 아래는 스택에 푸시와 팝을 하는 과정을 그림으로 표현한 것이다.

 

  후입 선출의 원리에 따라서 팝을 했을 때에 마지막에 푸시된 45가 꺼내지는 것을 볼 수 있다.

 

 

  🔍 스택의 특징

• 같은 구조, 크기의 자료를 한쪽으로만 넣고 뺄 수 있다. (Top에서만 가능)
• 재귀 알고리즘에서 재귀적 실행을 줄이기 위해서 사용된다.
• 구조가 단순하여 구현이 쉽고 데이터 저장/읽기 속도가 빠르다.

 

📌 스택의 구성요소

 스택의 클래스를 필드, 생성자, 메서드 순으로 살펴보자면 다음과 같다.

 

  🔍 스택의 필드

class IntStack {
	int max; // 스택의 용량
	int ptr; // 스택의 포인터
	int[] stk; // 스택의 본체인 배열
}

 위의 스택 클래스의 필드는 스택에 담기는 데이터의 형태가 정수 형태라면 정수형 배열인 int [], 문자 형태라면 char []로 유동적으로 설정해주면 된다. 

 max는 스택에 최대한 쌓을 수 있는 데이터의 수이다.

 ptr은 현재 스택에 쌓여 있는 데이터의 수를 나타내는 필드로 이는 max를 넘을 수 없도록 유의를 해야 한다.

 

// 스택이 비어있는 경우
pubilc class EmptyIntStackException extends RuntimeException {
	public EmptyIntStackException() {}
}
    
// 스택이 가득 차있는 경우
public class OverflowIntStackExcpetion extends RuntimeException {
	public OverflowIntStackExcpetion() {}
}

 main함수에서 예외처리를 하기 위해서 스택의 예외 처리 클래스를 따로 만들어주는 것이 좋다.

 

 

  🔍 스택의 생성자

스택의 생성자에서는 스택을 처음 생성할 때에 max값을 받아서 배열을 만들고 스택에 어떠한 데이터도 들어가 있지 않기에 ptr의 값을 0으로 선언해 준다. ptr이 접근이 가능한 값은 stk [0] ~ stk [max - 1] 이므로 max - 1까지 가능하다.

public IntStack(int capacity) {
    ptr = 0;
    max = capacity;
    try { 
    	stk = new int[max]; // 스택의 본체, 배열생성
    } catch (OutOfMemoryError e) { // 스택을 생성할 수 없음
    	max = 0;
    }
}

 스택의 본체, 배열의 생성에 실패할 경우에 (OutOfMemoryError) max값을 0으로 선언 함으로써 다른 메서드의 접근을 하지 못하게 해 준다.

 

 

  🔍 스택의 메서드

 스택의 메서드에는 기본적으로 푸시(push), 팝(pop)뿐만이 아니라 스택의 꼭대기에 있는 데이터를 확인하는 피크(peek), 스택의 바닥 쪽에서부터 데이터를 검색하는 indexOf, 스택의 모든 요소를 삭제하는 clear, 용량 확인을 위한 capacity, 스택에 쌓인 데이터 수를 확인하는 size 그리고 스택이 비어 있는지, 가득 찼는지 검사하는 IsEmpty, IsFull 메서드, 스택 안의 모든 데이터를 표시하는 덤프(dump) 등이 있다.

 

  ✏️ 푸시(push)

public int push(int x) throws OverflowIntStackException {
    if (ptr >= max) // 스택이 가득 차있는 경우 예외
    	throw new OverflowIntStaackException();
    return stk[ptr++] = x;
}

 스택에 데이터를 푸시하는 메서드로. 스택이 가득 차서 푸시가 불가능한 경우에는 OverflowIntStackException을 throw 한다. ptr이 가능한 범위는 0 ~ max까지로 스택이 가득 차있는 경우의 조건문을 (ptr == max)로 설정이 가능하지만 프로그래밍 실수로 인한 ptr의 범위가 max를 초과할 수도 있으므로 스택의 용량을 초과하는 포인터의 접근을 사전에 막기 위해서 (ptr >= max)로 해주는 게 좋다.

 스택의 푸시는 사실상 stk[ptr++] = x;의 한 줄을 통해서 구현된 것으로 스택의 포인터에 넣고자 하는 데이터를 넣고 포인터를 증가시켜 삽입한 데이터를 반환한다.

 

 

  ✏️ 팝(pop)

public int pop() throws EmptyIntStackException {
    if (ptr <= 0) // 스택이 비어있는 경우 예외
    	throw new EmptyIntStackException();
    return stk[--ptr];
}

 푸시와 같은 이유로 프로그래밍 실수로 인한 스택의 잘못된 포인터 접근을 미연에 방지하고자 스택에 데이터가 없는 경우 던질 EmptyIntStackException 예외의 조건문을 (ptr <= 0)로 설정한다. 

 팝을 하는 코드는 ptr의 값을 감소시킨 후 stk [ptr--]로 스택의 꼭대기에 있는 값을 반환한다. 스택에서 접근이 가능한 데이터를 ptr을 통해서 조절하므로 팝 메서드의 작동을 데이터를 null이나 다른 임의의 값으로 변경할 필요 없이 ptr의 값을 감소시키면 데이터를 꺼내는 것과 같은 효과를 낼 수 있다.

 

 

  ✏️ 피크(peek)

public int peek() throws EmptyIntStackException {
    if (ptr <= 0) // 스택이 비어있는 경우 예외
    	throw new EmptyIntStackException();
    return stk[ptr - 1];
}

 피크는 ptr의 값을 변경하지 않고 스택의 꼭대기에 있는 값을 반환해준다.

 

 

  ✏️ indexOf

public int indexOf(int x) {
    for (int i = ptr - 1; i >= 0; i--) {
        if (x == stk[i]) // 검색 성공
            return i;
    return -1; //검색 실패
}

 스택의 본체, 배열 stk에 검색하고자 하는 데이터 x가 있는지 스택의 꼭대기에서부터 검색하고 검색에 성공하면 x가 들어있는 인덱스를 반환해준다 만약 검색에 실패하면 -1을 반환한다.

 

 

  ✏️ clear

public void clear() {
    ptr = 0;
}

 ptr을 0으로 초기화 시켜주어 스택의 모든 값을 삭제하는 효과를 내는 메서드 clear이다.

 

 

  ✏️ capacity

public int capacity() {
    return max;
}

 스택의 용량을 반환해주는 capacity 메서드이다.

 

 

  ✏️ size

public int size() {
    return ptr;
}

 스택에 현재 쌓여 있는 데이터의 수를 알려주는 size 메서드이다.

 

 

  ✏️ IsEmpty, IsFull

public boolean isEmpty() {
    return ptr <= 0;
}

public boolean IsFull() {
    return ptr >= max;
}

 ptr을 통해서 스택이 비어 있는지 검사하는 IsEmpty메서드, 스택이 가득 찼는지 검사하는 IsFull메서드이다. 반환하는 값은 boolean형이다.

 

 

  ✏️ 덤프(dump)

public void dump() {
    if (ptr <= 0)
        System.out.println("스택이 비어 있습니다.");
    else {
        for (int i = 0l i < ptr; i++)
            System.out.print(stk[i] + " ");
        System.out.println();
    }
}

  스택의 0번째 index부터 ptr - 1의 인덱스까지, 바닥에서 꼭대기까지 출력하는 덤프 메서드이다.