Stack

앞으로의 코딩테스트를 준비하여 유용한 자료구조나 알고리즘을 정리해두기로 했다.

 

개념

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조 (Last In First Out)으로 되어있다

Java에서 배열, 리스트, Stack 클래스를 이용하여 사용할 수 있다.

한마디로 그릇이 쌓인 모습을 생각하면 된다

 

주요 연산

top()	스택의 가장 위(최근에 넣은) 데이터 반환
pop()	스택의 가장 위(최근에 넣은) 데이터 삭제
push()	스택의 가장 윗 데이터로 top의 자리 위에 메모리를 생성
is_emtpy()	스택이 비었다면 True 아니라면 False

 

리스트로 구현한 스택

class Node{
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class Stack{
    private Node top;

    public void push(int val){
        Node node=new Node(val);
        node.next=top;
        top=node;
    }

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

    public int pop(){
        if (isEmpty()){
            throw new EmptyStackException();
        }

        Node node=top;
        int data= node.data;
        top=top.next;
        node =null;
        return data;
    }

    public void printStack(){
        if(isEmpty()){
            System.out.println("stack 비었음");
        }else {
            Node node=this.top;

            while (node!=null){
                System.out.print(node.data+" ");
                node=node.next;
            }
            System.out.println("");
        }
    }
}