Java 배열로 스택(Stack) 구현하기

Java 배열로 스택(Stack) 구현하기

Java의 배열을 이용하여 스택(Stack)을 구현하는 방법에 대해 알아보겠습니다.

1. 스택(Stack)

스택은 제한적으로 접근할 수 있는 나열된 구조입니다. 후입선출(LIFO: Last In First Out)의 자료구조이며, 접근이 목록의 끝(Top 또는 Top Pointer)에서만 일어나기 때문에 Pushdown List 라고도 합니다. 스택에서 입력은 push, 출력은 pop, Top 위치의 데이터 확인은 peek 를 사용합니다.

스택은 추상자료형(Abstract Data Type)으로 수학적 모델을 가졌으며 구현 방법을 따로 명시하고 있지 않다는 점에서 자료구조와 차이를 보입니다. 이러한 특징은 다양한 방법으로 구현될 수 있음을 의미합니다.

다음은 스택이 실제로 사용되는 몇 가지 경우입니다.

• 운영체제(OS: Operating System)
  프로그램에서 사용되는 함수들을 스택 자료형에 저장하여 사용합니다.
  
• 컴파일러(Compiler)
  수학 기호들을 기계어로 변환시 사용합니다. (괄호 등을 매칭하는 경우)
• 자바 가상 머신(JVM: Java Virtual Machine)
  JVM 내에서 메서드가 실행, 종료될 때 스택 프레임을 이용하여 관리합니다. 

1.1. 스택의 구현

다음은 일반적으로 스택에 사용되는 필수적인 메서드들입니다.

• pop
  스택의 가장 최상위(마지막)에 위치한 데이터를 추출한 후에 스택에서 삭제합니다.
  
• push
  스택의 가장 최상위(마지막)에 데이터를 삽입합니다.
• isEmpty
  스택이 empty 상태인지 확인합니다.
• clear
  스택에 저장된 모든 데이터를 삭제하고 스택을 초기화합니다.
  
• peek
  스택의 가장 최상위(마지막)에 위치한 데이터를 추출합니다.
  pop 메서드와는 달리 스택에서 데이터를 삭제하지 않습니다.

다음은 Java로 구현한 스택의 소스코드입니다.

/*
 * @ TITLE Stack (배열로 구현한 스택)
 */
interface Stack{
    boolean isEmpty();
    boolean isFull();
    void push(char item);
    char pop();
    char peek();
    void clear();
}
 
public class ArrayStack implements Stack {
    
    private int top;
    private int stackSize;
    private char stackArr[];
 
    // 스택을 생성하는 생성자
    public ArrayStack(int stackSize) {
        top = -1;    // 스택 포인터 초기화
        this.stackSize = stackSize;    // 스택 사이즈 설정
        stackArr = new char[this.stackSize];    // 스택 배열 생성
    }
    
    // 스택이 비어있는 상태인지 확인
    public boolean isEmpty() {
        // 스택 포인터가 -1인 경우 데이터가 없는 상태이므로 true 아닌 경우 false를 return
        return (top == -1);
    }
    
    // 스택이 가득찬 상태인지 확인
    public boolean isFull() {
        // 스택 포인터가 스택의 마지막 인덱스와 동일한 경우 true 아닌 경우 false를 return
        return (top == this.stackSize-1);
    }
    
    // 스택에 데이터를 추가
    public void push(char item) {
        if(isFull()) {
            System.out.println("Stack is full!");
        } else {             
            stackArr[++top] = item;    // 다음 스택 포인터가 가리키는 인덱스에 데이터 추가
            System.out.println("Inserted Item : " + item);
        }
    }
    
    // 스택의 최상위(마지막) 데이터 추출 후 삭제
    public char pop() {
        if(isEmpty()) {
            System.out.println("Deleting fail! Stack is empty!");
            return 0;
        } else { 
            System.out.println("Deleted Item : " + stackArr[top]);
            return stackArr[top--];
        }                
    }
    
    // 스택의 최상위(마지막) 데이터 추출
    public char peek() {
        if(isEmpty()) {
            System.out.println("Peeking fail! Stack is empty!");
            return 0;
        } else { 
            System.out.println("Peeked Item : " + stackArr[top]);
            return stackArr[top];
        }
    }
    
    // 스택 초기화
    public void clear() {
        if(isEmpty()) {
            System.out.println("Stack is already empty!");
        } else {
            top = -1;    // 스택 포인터 초기화
            stackArr = new char[this.stackSize];    // 새로운 스택 배열 생성
            System.out.println("Stack is clear!");
        }
    }
    
    // 스택에 저장된 모든 데이터를 출력
    public void printStack() {
        if(isEmpty()) {
            System.out.println("Stack is empty!");
        } else {
            System.out.print("Stack elements : ");
            for(int i=0; i<=top; i++) {
                System.out.print(stackArr[i] + " ");
            }
            System.out.println();
        }
    }
 
    public static void main(String args[]) {
        int stackSize = 5;
        ArrayStack arrStack = new ArrayStack(stackSize);
        
        arrStack.push('A');
        arrStack.printStack();
        
        arrStack.push('B');
        arrStack.printStack();
        
        arrStack.push('C');
        arrStack.printStack();
        
        arrStack.pop();
        arrStack.printStack();
        
        arrStack.pop();
        arrStack.printStack();
        
        arrStack.peek();
        arrStack.printStack();
        
        arrStack.clear();
        arrStack.printStack();
    }
    
}

위의 코드를 실행하면 다음과 같은 결과가 출력됩니다.

이상으로 Java의 배열로 구현한 스택에 대해서 알아봤습니다.

※ 참고 문헌

• ko.wikipedia.org, 스택, https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

• donghoson.tistory.com, 배열로 스택 구현하기, https://donghoson.tistory.com/m/158?category=799812

• muckycode.blogspot.com, [자료 구조] 스택 (Stack), https://muckycode.blogspot.com/2015/01/stack.html