[자료구조-03] 스택(Stack)

1. 스택(Stack)이란?

스택의 구조

 

- 데이터를 일시적으로 저장하기 위해 사용하는 자료구조

- 후입선출 구조를 가짐

- 후입선출(LIFO, Last In First Out) : 가장 나중에 넣은 데이터를 가장 먼저 꺼냄

 

- 푸시(push) : 스택에 데이터를 넣는 작업

  팝(pop) : 스택에서 데이터를 꺼내는 작업

  꼭대기(top) : 푸시와 팝을 하는 위치

  바닥(bottom) : 스택의 가장 아랫부분

 

※ Java 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용함

void x() {...}

void z() {
    x();
}

int main() {
    z();
}

main 실행 - z 실행 - x 실행(아래 그림) - x 종료 - z 종료 - main 종료

 

x 메서드가 실행 중일 때의 스택

 

 

2. 스택 구현

1) 필드

- int형 값을 저장하는 스택을 만든다고 가정

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

 

 

(1) 스택 본체용 배열 stk

- 푸시한 데이터를 저장하는 스택 본체의 배열

- 인덱스 0인 요소 : 스택의 바닥(bottom)

- 가장 먼저 푸시된 데이터를 저장하는 곳 : stk[0]

 

(2) 스택 용량 max

- 스택의 용량(스택에 쌓을 수 있는 최대 데이터 수)을 나타내는 필드

- skt의 요솟수와 같음

 

(3) 스택 포인터 ptr

- 스택에 쌓여 있는 데이터 수를 나타내는 필드

- 스택 포인터(stack pointer)라고 함

 

 

-> 스택이 비어 있으면 ptr = 0

-> 스택이 가득 차 있으면 ptr = max

 

2) 생성자

public IntStack(int capacity) {
    ptr = 0;
    max = capacity;
    try {
    	stk = new int[max];
    } catch (OutOfMemoryError e) {
    	max = 0;
    }
}

- 스택 본체용 배열을 생성하는 등 준비 작업을 수행

 

(1) 생성 시 스택은 비어있으므로 스택 포인터 ptr = 0

(2) 매개변수 capacity로 전달받은 값을 스택 용량을 나타내는 max에 복사

(3) 요솟수가 max인 배열 stk의 본체를 생성

 

 

3) 푸시(push)

public int push(int x) throws OverflowIntStackException {
    if (ptr >= max)
    	throw new OverflowIntStackException();
    return stk[ptr++] = x;
}

- 스택에 데이터를 푸시하는 메서드

- 스택이 가득 차서 푸시할 수 없는 경우, 예외 OverflowIntStackException을 던짐

 

(1) 전달받은 데이터 x를 배열 요소 stk[ptr]에 저장

(2) 스택 포인터 ptr을 증가시킴

(3) 메서드의 반환값으로 푸시한 값을 반환

 

※ 스택이 가득 찼는지 확인하는 조건문을 관계 연산자(>=) 대신 등가 연산자(==)를 사용하면 스택 본체 배열의 상한과 하한을 벗어나0서 잘못 접근하는 것을 막을 수 있음

if (ptr == max)

 

4) 팝(pop)

public int pop() throws EmptyIntStackException {
    if (ptr <= 0)
    	throw new EmptyIntStackException();
    return stk[--ptr];
}

- 스택의 꼭대기에서 데이터를 팝(제거)하고 그 값을 반환하는 메서드

- 스택이 비어서 팝할 수 없는 경우, 예외 EmptyIntStackException을 던짐

 

(1) 스택 포인터 ptr을 감소시킴

(2) stk[ptr]에 저장되어 있는 값을 반환

 

 

5) 피크(peek)

public int peek() throws EmptyIntStackException {
    if (ptr <= 0)
    	throw new EmptyIntStackException();
    return stk[ptr - 1];
}

- 스택의 꼭대기에 있는 데이터를 몰래 엿보는 메서드

- 스택이 비어있는 경우, 예외 EmptyIntStackException을 던짐

 

(1) 꼭대기의 요소 stk[ptr-1]의 값을 반환

(2) 스택 포인터는 변화하지 않음

 

 

6) 기타 메서드

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


// (2) 모든 요소 삭제
public void clear() {
    ptr = 0;
}


// (3) 스택 용량 반환
public int capacity() {
    return max;
}


// (4) 데이터 수 확인
public int size() {
    return ptr;
}


// (5) 비어있는지 확인
public boolean isEmpty() {
    return ptr <= 0;
}


// (6) 가득 찼는지 확인
public boolean isFull() {
    return ptr >= max;
}


// (7) 스택 안의 모든 데이터를 바닥 -> 꼭데기 순서로 출력
public void dump() {
    if (ptr <= 0)
    	System.out.println("스택이 비어 있습니다.");
    else {
        for (int i = 0; i < ptr; i++)
        	System.out.print(stk[i] + " ");
        System.out.println();
    }
}

 

 

 

 

 

 

참고 - Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 (저자 : 보요 시바타, 출판 : 이지스 퍼블리싱)