자료구조 (Stack)

Stack

• 한 쪽 끝에서만 데이터를 넣고 뺼수 있는 선형 구조
• LIFO : List In First Out 특징
• push : 데이터 넣는 것
  pop : 데이터 꺼내는 것

Array를 이용한 Stack 구현법

• top : 데이터를 pop할 때 어떤 데이터를 꺼내야 하는지 위치에 대한 값
  데이터가 push 될 때는 top이 위로,
  데이터가 pop 될 때는 top이 아래로 이동
• top 에 값이 없으면 "-1" 반환
  (top이 -1 값이면 데이터 존재하지 않으므로 이동하지 말고 예외 발생)
• 데이터 push 시 top가 마지막 index와 동일하면 stack이 꽉 찬 것

ArrayStack 예제

• Stack 을 인터페이스로 만들어 상속 받는 방식을 한번 구현해 봤다.

package arrayStack;

public interface Stack {
    boolean isEmpty();
    boolean isFull();
    void push(String data);
    String pop();
    String peek();
}

• ArrayStack 방식은 순서만 잘 지켜주면 된다.

package arrayStack;

public class ArrayStack implements Stack {

     int top = -1;
     int stackSize;
     String[] stack;

    public ArrayStack(int stackSize) {
        this.stackSize = stackSize;
        stack = new String[this.stackSize];
    }

    @Override // stack이 비어있는 상태인지 확인
    public boolean isEmpty() {
        //stack top가 -1 인 경우 데이터가 없는 상태 -> turn or false return
        return (top == -1);
    }

    @Override // stack이 가득찬 상태인지 확인
    public boolean isFull() {
        //stack top가 stack의 마지막 인덱스와 동일한 경우 -> turn or false return
        return (top == stack.length - 1);
    }

    @Override //stack에 data 추가
    public void push(String data) {
        if (isFull()) {
            System.out.println("Stack is Full");
        } else {
            stack[++top] = data;
            System.out.println("push data :" + data);
        }
    }

    @Override //stack에 마지막 data 확인 후 삭제
    public String pop() {
        if (isEmpty()) {
            System.out.println("Stack is Empty");
        }else
            System.out.println("Deleted Data :" + stack[top]);
            return stack[top--];

        }


    @Override //stack의 마지막 data 확인
    public String peek() {
        if (isEmpty()) {
            System.out.println("Peek is fail");
            return null;
        } else {
            System.out.println("peek data :" + stack[top]);
            return stack[top];
        }
    }

    // 스택에 저장된 모든 데이터를 출력
    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(stack[i] + " ");
            }
        }
    }
}

• 실행을 직접 해보자

package arrayStack;

public class Main {
    public static void main(String[] args) {
        ArrayStack arrayStack = new ArrayStack(5);

        arrayStack.push("A");
        arrayStack.push("B");
        arrayStack.push("C");
        arrayStack.push("D");
        arrayStack.push("E");

        arrayStack.printStack();

        arrayStack.pop();

        arrayStack.printStack();

        arrayStack.pop();

        arrayStack.printStack();

        arrayStack.pop();

        arrayStack.printStack();

        arrayStack.push("F");

        arrayStack.printStack();

        arrayStack.peek();

        arrayStack.printStack();

    }
}

• 결과값

push data :A
push data :B
push data :C
push data :D
push data :E
Stack elements : A B C D E Deleted Data :E
Stack elements : A B C D Deleted Data :D
Stack elements : A B C Deleted Data :C
Stack elements : A B push data :F
Stack elements : A B F peek data :F
Stack elements : A B F 

List를 이용한 Stack 구현법

• Array를 이용한 Stack과 다르게 List를 이용한 Stack에서는
  top를 head와 동일 시 한다.
• 데이터를 pop 할 때 head가 null이면 데이터 존재하지 않는다 -> 예외 발생

ListStack 예제

• 단일 연결 리스트를 공부했다면 리스트를 이용한 스택도 그와 다르지 않다.
  우선 Node Class를 따로 만들어 준디

package listStack;

public class Node {

    Node nextNode;
    String data;

    Node(String data){
        this.data = data;
        this.nextNode = null;
    }
}

• ListStack을 만들어 준다

package listStack;

public class ListStack {

    public Node top;

    public ListStack() {
        this.top = null; // 생성자와 stack 값이 없어 null;
    }

    public boolean isEmpty() {
         return (top == null);
    }

    //data를 스택의 top에 넣는다
    public void push(String data) {
        Node node = new Node(data);
        node.data = data;
        if(!isEmpty()){
            node.nextNode = top;
        }
        top = node;
    }

    // top 노드를 스택에서 제거
    public Object pop() {
        if (isEmpty()) {
            throw new RuntimeException("stack is empty");
        }

        Node removeNode = top;
        Object tempData = removeNode.data;
        top = removeNode.nextNode;


        removeNode.data = null;
        removeNode.nextNode = null;
        return tempData;
    }

    // top 노드의 데이터를 return
    public Object peek() {
        if (isEmpty()) throw new ArrayIndexOutOfBoundsException();

        return top.data;
    }
}

• 실행하는 파일

package listStack;

public class Main {
    public static void main(String[] args) {

        ListStack listStack = new ListStack();

        System.out.println("List Stack 테스트");

        // stack에 데이터 삽입

        for (int i = 1; i <= 5; i++) {
            listStack.push("ListStack data : " + i);
        }

        listStack.push("ListStack data : 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());
    }

}

• 결과값

List Stack 테스트
ListStack data : 6
ListStack data : 5
ListStack data : 4
ListStack data : 4
ListStack data : 4
ListStack data : 3
ListStack data : 2
ListStack data : 1