Stack

정의

리스트 기반의 데이터 구조
L.I.F.O (Last In First Out Structure)

동작 방식

• 각 element 를 top 에 쌓는 방식으로 저장한다.
• 오직 Top 을 통해서 element 에 접근이 가능하고 관리할 수 있다.
  
  

사용 시점

• 가장 최근의 element 에 접근이 필요할 때
• 저장한 element 들의 순서를 유지하며 관리할 때
  
  

Push & Pop

• Push
  : stack 에 element 를 저장할 때 O(1)
• Pop
  : stack 에 element 를 삭제할 때 O(1)
  
  

provided method

method	description
stack.push(Object element)	stack 의 최상위(Top)에 요소 추가. return : element
stack.add(Object element)	stack 의 최상위(Top)에 요소 추가. return : true/false
stack.pop()	stack 의 최상위(Top)에 위치한 요소 삭제. return : element
stack.peek()	stack 의 최상위(Top)에 위치한 요소 반환. return : element
stack.search(Object element)	stack 안에 요소의 순번을 반환. return : 존재 O, element의 순번 / 존재 X, -1
stack.isEmpty()	stack 이 Empty 상태인지 확인. return : true/false
stack.clear()	stack 에 저장된 모든 데이터를 삭제하고 스택을 초기화. return :
stack.size()	stack 에 저장된 데이터의 개수를 반환 return : int

구현

stack 자료구조를 Array 와 LinkdedList, 두 가지 방식으로 구현할 수 있다.

Array, LinkedList 구현의 장단점

	Array	LinkedList
장점	데이터 접근 속도가 빠르다 (메모리를 동적으로 할당하지 않음)	크기가 가변적이다
단점	크기가 고정되어있다	데이터 접근 속도가 느리다 (삽입, 삭제시 메모리를 동적으로 할당/해제됨)

1. Array 방식

스택 구조는 배열과 동일하다.

배열로 Stack 구현 시 주의사항
  - 데이터가 없는 경우 pop 연산
  - 데이터의 개수가 배열의 크기를 넘는 경우 push 연산

class StackArray {
    int size;
    int index = 0;
    Object[] array;

    // 스택을 생성하는 생성자
    public StackArray(int size) {
        this.size = size;
        array = new Object[size];
    }

    //size
    int size() {
        return index;
    }

    //peek
    Object peek() {
        if(size() == 0){
            return null;
        }
        return array[index - 1];
    }

    //push
    Object push(Object o) {
        if(index < size) {
            array[index++] = o;
            return o;
        }
        else
            throw new ArrayIndexOutOfBoundsException();
    }

    //pop
    Object pop() {
        if(size() == 0)
            throw new ArrayIndexOutOfBoundsException();

        return array[--index];
    }

    //isEmpty
    Boolean isEmpty() {
        if(size() == 0)
            return true;
        else
            return false;
    }

    //search
    int search(Object o) {
        for (int i = array.length - 1 ; i >= 0 ; i--) {
            if(array[i].equals(o)){
                return array.length - i;
            }
        }
        return -1;
    }

    //clear
    void clear() {
        index = 0;
    }
}

2. LinkedList 방식

'가장 앞 노드를 삽입/삭제하는 연산' 기능만 가능한 단일 연결리스트이다.

LinkedList 로 Stack 구현 시 주의사항
  - 데이터가 없는 경우(head 에 null 값을 가질 경우) pop 연산

class Node<T> {
    Node<T> next = null;
    T data = null;
}

class StackList <T> {
    Node<T> head = null;

    T push(T data) {
        Node<T> tmp = new Node<>();
        tmp.data = data;

        if(!isEmpty()) {
            tmp.next = this.head;
        }

        this.head = tmp;

        return data;
    }

    //pop
    T pop() {
        if(isEmpty())
            throw new ArrayIndexOutOfBoundsException();

        T tmpData = this.head.data;
        Node<T> popped = this.head;
        this.head = this.head.next;

        popped.next = null;
        popped.data = null;

        return tmpData;
    }

    //peek
    T peek() {
        return head.data;
    }

    //isEmpty
    Boolean isEmpty() {
        if(this.head == null)
            return true;
        else
            return false;
    }

    //search
    int search(T o) {
        int index = 0;

        return index;
    }

    //clear
    void clear() {

    }
}

전체 코드

    
    public static void main(String[] args) {

        //------------------------------------------------
        System.out.println("\n\n");
        System.out.println("# java.util.Stack");
        Stack<Integer> stack1 = new Stack<>();

        System.out.print("입력 순서 : ");
        for(int i=0; i<10; i++){
            int result = stack1.push(i);
            System.out.print(result + " ");
        }

        System.out.println();
        System.out.println("stack1.peek() : " + stack1.peek());
        System.out.println("stack1.isEmpty() : " + stack1.isEmpty());
        System.out.println("stack1.search(9) : " + stack1.search(9));

        System.out.print("출력 순서 : ");
        while(!stack1.isEmpty()) {
            System.out.print(stack1.pop() + " ");
        }

        //------------------------------------------------
        System.out.println("\n\n");
        System.out.println("# 배열로 구현한 Stack");
        StackArray stack2 = new StackArray(10);

        System.out.print("입력 순서 : ");
        for(int i=0; i<10; i++){
            int result = (int) stack2.push(i);
            System.out.print(result + " ");
        }

        System.out.println();
        System.out.println("stack1.peek() : " + stack2.peek());
        System.out.println("stack1.isEmpty() : " + stack2.isEmpty());
        System.out.println("stack1.search(9) : " + stack2.search(9));

        System.out.print("출력 순서 : ");
        while(!stack2.isEmpty()) {
            System.out.print(stack2.pop() + " ");
        }

        //------------------------------------------------
        System.out.println("\n\n");
        System.out.println("# LinkedList로 구현한 Stack");
        StackList<Integer> stack3 = new StackList<>();

        System.out.print("입력 순서 : ");
        for(int i=0; i<10; i++){
            int result = (int) stack3.push(i);
            System.out.print(result + " ");
        }

        System.out.println();
        System.out.println("stack1.peek() : " + stack3.peek());
        System.out.println("stack1.isEmpty() : " + stack3.isEmpty());
        System.out.println("stack1.search(9) : " + stack3.search(9));

        System.out.print("출력 순서 : ");
        while(!stack3.isEmpty()) {
            System.out.print(stack3.pop() + " ");
        }

    }