JAVA로 알아보는 자료구조 스택(Stack)

 

우리가 자료구조를 생각하면 무엇이떠오를까?

스택(Stack), 큐(Queue), 트리(Tree), 힙(Heap) 등 여러가지 자료구조를 생각해볼수 있다

그러면 우리는 자료구조를 왜쓸까?

 

이는 우리가 데이터를 꺼내거나, 넣을때 사용에맞는, 용도에맞는 자료구조를 사용하여 효율적으로 간편하게 구현하기 위해서일것이다

이번에는 여러가지 자료구조중 스택(Stack)의 특성에 대해서 알아보고 실제로 구현해보도록 하자

 

 

 

 

 

 

스택(Stack) 의 특징

---

우선 스택은 쌓다라는 의미를 가지고있고 선출후입(Last In First Out)이라는 특성을 가지고있다

쉽게말해 나중에 들어온게 먼저 나간다는 의미이며, 상자에 책을 적재한뒤 다시꺼낼때는 위에서 부터 꺼내는것과 같은 특성을 가지고있다

 

사용처는 ' 가장 최근에 수행했던 기능 ' 을 순서대로 불러오고싶을때 즉 인터넷 브라우저의 뒤로가기, 엑셀의 Undo 등 여러곳에 쓰인다

 

Stack<Element> stack = new Stack<>();

 

여기서 JAVA에서는 기본으로 Stack 클래스를 지원해주며 push()를 통해서 데이터를 집어넣고 pop()을 통해서 데이터를 꺼낼수있으며 peek(), empty(), search() 기능을 지원해준다

 

우리는 이런 메서드를 직접만들어보고 이런식으로 스택이 이런식으로 구현되어있다는 것을 알아보도록 하자

참고로 Java에서 메인메서드가 실행되면 호출스택과 같은 형식으로 불러와진다

 

 

 

 

 

 

 

 

 

JAVA에서 지원하는 Stack

---

처음으로 Java에서 만들어져있는 Stack을 활용해서 데이터가 어떤식으로 흘러가는지 알아보도록 하자

 

Stack<Integer> stack = new Stack<>();

 

가장처음 Stack을 new연산자를 이용해서 객체를 생성해주도록 한다

 

 

Stack<Integer> stack = new Stack<>();

for (int i=0; i<4; i++) {
            stack.push(i);
}

 

그다음 반복문을 통해 0, 1, 2, 3 총 4개의 값을 순서대로 push()를 통해서 넣어보자

그러면 현재 Stack 자료구조에는 0~3 총 4개의 정수가 적재되있다는 걸 알수있다

 

 

3

2

1

0

stack

 

가장 처음들어온 값인 0이 맨아래에 적재되고 가장 나중에 들어온값이 맨위에 적재되있다

 

        Stack<Integer> stack = new Stack<>();

        for (int i=0; i<4; i++) {
            stack.push(i);
        }

        for (int i=0; i<4; i++) {
            int pop = stack.pop();
            System.out.println("pop = " + pop);
        }

 

그다음 stack에 저장되어있는값을 반복문을통해 그대로 pop()하여 꺼내고 출력해보도록 하자

 

 

보면 pop()되어서 꺼내진 값을 변수에 담아서 출력하니 맨 위에있던 3이먼저 꺼내지고 위에서부터 아래로 차례대로 꺼내지는것을 확인할수있다

 

해당 반복문을 실행한후 stack을 다시 출력해보면 stack이 비워져있는것을 확인할수있다 (모두 꺼내어짐)

 

 

 

이제 우리가 더구현해야될 메서드인 peek(), search(), empty()를 수행한결과는 다음과같다

 

        Stack<Integer> stack = new Stack<>();

        for (int i=0; i<4; i++) {
            stack.push(i);
        }

        System.out.println("stack.peek = " + stack.peek());
        System.out.println("stack.search = " + stack.search(3));
        System.out.println("stack.empty = " + stack.empty());

 

peek은 값을 꺼내는것이아니라 맨위에있는 값을 출력한다 그다음 search(3)은 3번째 인덱스의 있는 값을 가져온다

그리고 empty()는 해당 스택이 비어있으면 True를 반환한다 추가로 isfull() 해당 스택에 데이터가 있으면 true를 반환해준다

 

Stack을 구현할때는 정적인(처음에 크기를 할당해준다) Array로 구현한 stack과 LinkedList를 이용한 동적인 Stack이있다

Array는 처음에 사이즈를 정해주며, 구현의 난이도가 쉽지만 LinkedList는 Array랑 비교했을때 상대적으로 구현방법이 어렵다 하지만 동적으로 사이즈를 정하기때문에 편하다는 장점이있다

 

이해하기 쉽게 Array로 구현한 스택을 잠시 봐보도록하자

 

 

 

 

 

 

 

 

 

JAVA로 Stack을 구현하는 방법

---

 

 

이해를 돕기위해 최대한 불필요한 부분은빼고 Stack의 대표적인 기능인 pop(), push(), peek() 만 구현해보도록 하자

 

 

 

public interface ArrayStackInterface {

    void push(char item);
    char pop();
    char peek();
}

 

가장 처음 스택구현에 앞서 인터페이스를 선언해준다 push, pop, peek 메서드를 넣어주고 이제 해당 추상메서드들을 오버라이드하여 ArrayStack이란 새로운 스택을 만들어보자

 

 

 

 

public class ArrayStack implements ArrayStackInterface {

}

 

ArrayStack 클래스를 만들고 해당 인터페이스를 Implements 해준다

 

 

 

public class ArrayStack implements ArrayStackInterface {

    @Override
    public void push(char item) {

    }

    @Override
    public char pop() {

    }

    @Override
    public char peek() {

    }
}

 

 

그다음 구현해야할 메서드들을 오버라이드 시켜주고 이제 본격적으로 메서드에 기능들을 넣어보도록하자

 

 

public class ArrayStack implements ArrayStackInterface {

    private int index;
    private int size;
    private char[] stack;



    @Override
    public void push(char item) {

    }

    @Override
    public char pop() {

    }

    @Override
    public char peek() {

    }
}

 

 

가장처음 인스턴스 변수로 배열의 위치를 가르켜줄 index와, 배열의크기, 그다음 char[] stack을 선언해준다

char[] stack은 생성자를 통해 사용자가 사이즈를 넣어주면 해당 크기를 가진 배열을 stack에 선언해줄것이다

 

 

 

public class ArrayStack implements ArrayStackInterface {

    private int index;
    private int size;
    private char[] stack;


    ArrayStack(int size) {
        index = -1;
        this.size = size;
        stack = new char[size];
    }


    @Override
    public void push(char item) {

    }

    @Override
    public char pop() {

    }

    @Override
    public char peek() {

    }
}

 

 

new 연산자를 통해 객체를 생성하면 생성자로 사이즈를 받고 객체를 생성시점에 인스턴스변수들을 초기화해준다

index는 -1로 초기화시켜준뒤 size와 size만큼 가지는 char 배열을 각각의 인스턴스 변수들에게 넣어주게된다

 

 

    @Override
    public void push(char item) {
        stack[++index] = item;
    }

 

 

가장 처음 push() 메서드는 사용자에게 받은 데이터를 char[] stack에 넣어주게되며 index를 1증가시켜 순서대로 들어갈수 있도록해준다 (예시 : 1, 2, 3, 4를 넣으면 해당 배열에 1, 2, 3, 4가 들어가게된다)

 

 

    @Override
    public char pop() {
        return stack[index--];
    }

 

그다음 pop()을 수행하게되면 꺼내오는 값을 반환해주고 index는 이전을 가르킨다

(예시 : 1, 2, 3, 4에서 pop()을 수행하면 4라는 숫자를 반환하고 index는 3을 가르킨다)

 

 

    @Override
    public char peek() {
        return stack[index];
    }

 

peek()을 수행하게되면 현재 인덱스의 값을 반환한다

(예시 : 1, 2, 3, 4에서 peek()을 수행하게되면 가장 맨끝인 4를 반환한다)

 

 

위에 예시는 정말 간단하게 Stack을 구현한것으로 대충 원리만 알면 Stack이 어떤기능이고 어떤식으로 작동하는지 알수있을것이다