[자료구조*알고리즘] 6.Java 스택(Stack) 정리

 

 

Java 스택(Stack) 정리

 

1. 스택(Stack)의 개요

2. 스택(Stack)의 동작

3. 배열을 이용한 구현

4. 스택(Stack) 테스트

5. 결과

 

 

 

 

1. 스택(Stack)의 개요

1) 맨 위에 있는 데이터를 먼저 꺼내는 형태이기 때문에 제일 마지막에 저장한 데이터를 제일 먼저 꺼내는 후입선출(LIFO - Last In First Out) 형태의 자료구조

2) 가장 최근에 입력된 데이터를 top 이라고 하며 스택은 top에서만 삽입, 삭제, 읽기 동작이 발생할 수 있다.

 

2. 스택(Stack)의 동작

1) 삽입 - Push

  스택(Stack)에 새로운 데이터를 삽입하는 작업을 push라고 한다. 이는 top 값을 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.

2) 삭제(추출) - Pop

  스택(Stack)에서 데이터를 제거하는 작업을 pop이라고 하며 이는 top이 가리키고 있는 자료를 삭제한 후 top 값을 하나 감소 시키도록 구현한다.

3) 읽기 - peek

  스택에서 top이 가리키는 데이터를 읽는 작업을 peek이라고 하며 top 값의 변화는 없다.

 

3. 배열을 이용한 구현

public class ArrayStack {
    
    private int top;
    private int maxSize;
    private Object[] stackArray;
    
    // 배열 스택 생성,  스택의 최대 크기로 생성
    public ArrayStack(int maxSize){
        
        this.maxSize = maxSize;
        this.stackArray = new Object[maxSize];
        this.top = -1;
    }
    
    // 스택이 비어있는지 체크
    public boolean empty(){
        return (top == -1);
    }
    
    // 스택이 꽉찼는지 체크
    public boolean full(){
        return (top == maxSize-1);
    }
    
    // 스택에 item 입력
    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;
    }

}

생성자를 통해 스택(Stack)의 최대 크기를 입력받아 데이터를 저장할 배열을 생성하고 top 값은 초기값으로 -1을 지정한다.
이는 스택에 데이터가 없다는 의미이다.
그리고 스택이 비었는지 여부를 반환하는 empty() 메소드와 스택이 다 찼는지 여부를 반환하는 full() 메소드를 정의한다. 

 

top 값은 맨 위에 위치한 데이터의 index 값이 되므로 top 값이 초기값(-1)일 경우에는 빈 스택이 되며 top 값이 배열의 크기 -1일 경우에는 스택에 데이터가 꽉 찼다는 의미이다.

 

push() 메소드는 top을 하나 증가 시킨 후 top 위치에 지정한 데이터를 삽입하면 되고,
peek() 메소드는 top 위치의 데이터를 반환하며,
pop() 메소드는 peek()를 호출하여 top 위치의 데이터를 반환하고 top 값을 하나 감소시킨다.

 

4. 스택(Stack) 테스트

public class StackTest {
    
    public static void main(String[] args){
        
        
        // 크기 5의 배열 스택 생성
        ArrayStack arrayStack = new ArrayStack(5);
        
        System.out.println("Array Stack 테스트");
        
        // 스택에 데이터 삽입
        for(int i=1; i<=5; i++){
            arrayStack.push("ArrayStack 데이터-" + i);
        }
        
        System.out.println(arrayStack.pop());
        System.out.println(arrayStack.pop());
        System.out.println(arrayStack.peek());
        System.out.println(arrayStack.peek());
        System.out.println(arrayStack.pop());
        System.out.println(arrayStack.pop());
        System.out.println(arrayStack.pop());
    
        System.out.println();
        
        // 연결리스트 스택 생성
        ListStack listStack = new ListStack();
        
        System.out.println("List Stack 테스트");
        
        // 스택에 데이터 삽입
        for(int i=1; i<=5; i++){
            listStack.push("ListStack 데이터-"+i);
        }
        
        listStack.push("ListStack 데이터-6");
        
        System.out.println(listStack.pop());
        System.out.println(listStack.pop());
        System.out.println(listStack.peek());
        System.out.println(listStack.peek());    
        System.out.println(listStack.pop());
        System.out.println(listStack.pop());
        System.out.println(listStack.pop());
        System.out.println(listStack.pop());
        
    }

}

 

 

5. 결과