JAVA의 Stack

자료구조 - 스택

스택은 가장 최근에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO) 구조입니다.

스택에는 삽입(PUSH) 연산과 삭제(POP) 연산이 존재하는데

삽입의 경우 가장 높은 위치(TOP)에 쌓이게 되며

삭제의 경우 가장 마지막에 들어온 데이터, 즉 TOP에 위치한 데이터가 삭제 됩니다.

---

JAVA로 Stack 구현

스택을 구현하는 방법은 2가지가 있습니다.

배열을 이용한 스택과 연결리스트를 이용한 스택입니다.

먼저 배열을 이용한 스택 구현입니다.

public class CStackArray {
 
    private int top;
    private int maxSize;
    private Object[] stackArray;
 
    // 최대 크기로 배열 생성
    public CStackArray(int maxSize){
        this.maxSize = maxSize;
        this.stackArray = new Object[maxSize];
        this.top = -1;
    }

스택의 가장 꼭대기를 가리키는 top 변수, 

배열의 최대 크기를 받는 maxSize 변수가 있습니다.

    // 스택이 비어있는지 체크
    public boolean empty(){
        return (top == -1);
    }
 
    // 스택이 꽉찼는지 체크
    public boolean full(){
        return (top == maxSize-1);
    }
 
    // 삽입연산
    public void push(Object item){
        if(full()) throw new ArrayIndexOutOfBoundsException((top+1)+">=" + maxSize);
        stackArray[++top] = item;
    }
 
    // 스택의 가장 위의 데이터 반환
    public Object peek(){
        if(empty()) throw new ArrayIndexOutOfBoundsException(top);
        return stackArray[top];
    }
 
    // 삭제연산
    public Object pop(){
        Object item = peek();
        top--;
 
        return item;
    }

empty, full 함수는 스택이 비었는지 차있는지를 체크해주고

push, pop 함수를 통해 삽입, 삭제 연산이 이루어집니다.

다음은 연결리스트를 이용한 스택입니다.

public class CStackList {
    
    private Node top;
    private class Node{
        private Object data;
        private Node nextNode;
 
        Node(Object data){
            this.data = data;
            this.nextNode = null;
        }
    }
 
    // 생성자를 통한 스택초기화
    public CStackList(){
        this.top = null;
    }

노드는 데이터 필드와 다음 노드를 가리키는 포인터 필드로 구성됩니다.

    // 스택이 비어있는지 확인
    public boolean empty(){
        return (top == null);
    }
 
    // 삽입연산
    public void push(Object item){
        Node newNode = new Node(item);
        newNode.nextNode = top;
        top = newNode;
    }
 
    // 스택의 가장 위의 데이터 반환
    public Object peek(){
        if(empty()) throw new ArrayIndexOutOfBoundsException();
        return top.data;
    }
 
    // 삭제연산
    public Object pop(){
        Object item = peek();
        top = top.nextNode;
        return item;
    }

배열과 마찬가지로 삽입, 삭제가 이루어집니다.

---

JAVA의 Stack

Java에서는 Stack을 편리하게 사용할 수 있도록 API를 제공합니다.

java.util.Stack<E>는 Vector를 상속받고 있으며,

주요 메소드는 다음과 같습니다.

Method	Description
boolean empty()	Stack이 비어있는지 알려줌
Object peek()	스택의 맨 위에 저장된 객체를 반환
Object pop()	스택의 맨위에 저장된 객체를 삭제
Object push(Object item)	스택에 객체를 삽입
int search(Object o)	스택에서 주어진 객체를 찾아서 위치를 반환

    // 스택이 비어있는지 확인
    public boolean empty(){
        return (top == null);
    }
 
    // 삽입연산
    public void push(Object item){
        Node newNode = new Node(item);
        newNode.nextNode = top;
        top = newNode;
    }
 
    // 스택의 가장 위의 데이터 반환
    public Object peek(){
        if(empty()) throw new ArrayIndexOutOfBoundsException();
        return top.data;
    }
 
    // 삭제연산
    public Object pop(){
        Object item = peek();
        top = top.nextNode;
        return item;
    }

Integer 타입의 Stack 객체를 생성한 다음,

push 함수를 통해 10, 20, 30 순서로 넣어줍니다.

그리고 스택이 비어있지 않으면 pop 함수를 통해 삭제해주는 코드입니다.