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();
    }
    
}