[자료구조 Java] 스택(Stack) 개념 정리 + 자바로 구현하기

 

스택(Stack)이란?

 

가장 늦게 들어간 요소가 가장 먼저 나오고 가장 먼저 들어간 요소가 가장 늦게 나오는

후입선출(LIFO: Last in First Out) 입출력 형태를 갖는 자료구조.

 

주요 연산으로 pop(), push()이 있다.

pop은 가장 늦게 들어온 요소를 삭제하는 연산이고, push는 요소를 맨 앞에 삽입하는 연산이다.

 

 

 

구현 방법은 두 가지가 있다.

 

1. 배열을 이용한 구현

2. 리스트를 이용한 구현

 

두 가지 구현의 장단점은 결국 배열과 리스트의 장단점과 동일하다.

 

배열을 이용한 구현

장점: 구현이 간단하며 별도로 메모리를 동적으로 할당하지 않기에 속도가 빠르다.

단점: 크기가 고정

 

리스트를 이용한 구현

장점: 크기가 가변적

단점: 삽입, 삭제시 메모리를 동적으로 할당/해제하기에 속도가 느리다.

 

 

배열을 이용한 Stack 구현

 

 

배열을 이용한 stack의 형태는 다음과 같다.

사실 배열 자체가 stack 구조이기에 구현 자체에 큰 어려움은 없다.

 

top 변수는 배열의 가장 마지막으로 저장된 요소의 index를 저장한다.

처음에 아무런 값도 저장하지 않는 스택에서 top은 -1을 저장한다.

배열의 시작은 언제나 index 0이기에 별도로 bottom 변수를 만들 필요는 없다.

 

push 연산시 top은 기존 저장하던 index+1을 저장하고 해당 index에 데이터를 저장한다.

pop 연산시 top은 기존 저장하던 index -1 을 저장한다 해당 index에 null값을 저장한다.

 

size 변수는 배열의 크기를 나타낸다.

 

public class ArrayStack {

        int size;
        int top = -1;
        Object[] stack;

        public ArrayStack(int size) {
            this.size = size;
            stack = new Object[size];
        }
    
    ...
    
    }

 

제너릭으로 배열을 만들 수는 없어 Object로 이루어진 배열을 선언하였다.

Stack 선언시 크기를 입력받을 수 있게 구현하였다.

 

 

 

push, pop 구현시 주의할 점 두 가지는 데이터가 없는 경우의 pop연산과 크기가 꽉 찬 상태에서의 push연산에 대해 꼭 처리를 해줘야 한다는 점이다.

 

1. 데이터가 없는 경우의 pop연산

 

데이터가 없는 경우에 pop연산을 하는 경우 별도로 'ArrayIndexOutOfBoundsException' 예외를 발생하도록 예외처리를 해준다.

 

    public Object pop() {
        if (isEmpty())
            throw new ArrayIndexOutOfBoundsException();

        Object poppedData = stack[top];
        stack[top--] = null;

        return poppedData;
    }

 

 

2. 크기가 꽉찬 상태에서의 push연산

 

더 이상 배열에 저장할 공간이 없는 상태에서 push연산을 하는 경우 마찬가지로 별도로

 'ArrayIndexOutOfBoundsException' 예외를 발생하도록 예외처리를 해준다.

 

    public Object pop() {
        if (isEmpty())
            throw new ArrayIndexOutOfBoundsException();

        Object poppedData = stack[top];
        stack[top--] = null;

        return poppedData;
    }
    
        public boolean isEmpty() {
        return top == -1;
    }

 

 

리스트를 이용한 Stack 구현

 

 

리스트를 이용한 stack의 구현은 다음과 같이 단일 연결리스트와 유사한 형태이다..

단지 '가장 앞 노드를 삽입하는 연산'과 '가장 앞 노드를 삭제하는 연산'만이 구현된 단일 연결리스트라고 봐도 무방하다.

 

head변수는 항상 맨 앞의 노드(가장 늦게 삽입된 노드)를 가리키다.

 

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

public class ListStack<T> {
    Node<T> head = null;
    Node<T> buttom = null;

....

}

 

 

 

1. push연산

 

1. 새로운 노드의 next변수에 head가 가리키는 노드의 주소값을 저장한다.
2. head에는 새로운 노드의 주소값을 저장한다.

    public void push(T data) {
        //스택 맨 위에 요소를 추가
        Node<T> newNode = new Node<>();
        newNode.data = data;

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

 

2. pop연산

 

1. 삭제할 노드의 데이터를 임시 저장한다.
2. head는 삭제할 노드의 next변수 값인 다음 노드 주소값을 저장한다.
3. 삭제할 노드의 데이터와 next변수에 null값을 저장한다.

(어느 노드도 해당 노드를 참조하지 않기에 java garbagecollector에 의해 메모리 할당 해제됨)

 

 pop연산시 주의할 점은 head가 null값을 가지고 있는 경우 데이터가 없기에 별도로 예외처리를 발생시켜야 한다.

배열로 구현한 stack과 달리 동적으로 메로리를 할당하기에 push연산시 스택의 크기를 초과하지 않기에 push연산에서 별도 예외처리 설정을 필요하지 않다.

 

    public T pop(){
        //스택 맨 위의 요소를 삭제하며 반환
        if(isEmpty())
            throw new ArrayIndexOutOfBoundsException();

        T tmp = this.head.data;
        Node<T> poppedNode = this.head;
        this.head = this.head.next;

        poppedNode.next = null;
        poppedNode.data = null;

        return tmp;
    }

 

 

코드 실행

public class Main {
    public static void main(String[] args) {
        System.out.println("배열로 구현한 stack");
        ArrayStack arrayStack = new ArrayStack(1000);
        System.out.println("1,2,3,4,5 순으로 push()");
        arrayStack.push(1);
        arrayStack.push(2);
        arrayStack.push(3);
        arrayStack.push(4);
        arrayStack.push(5);

        System.out.print("stack 가장 위에 있는 데이터: ");
        System.out.println(arrayStack.peek());

        int arrayindex = arrayStack.top;
        for (int i = 0; i <= arrayindex; i++) {
            System.out.print("pop된 데이터: ");
            System.out.println(arrayStack.pop());
        }

        //ArrayIndexOutOfBoundsException 예외 발생
//        System.out.printf("pop된 데이터: ");
//        System.out.println(arrayStack.pop());

        System.out.println("----------------------------------------------");
        System.out.println("list로 구현한 stack");
        ListStack<Integer> listStack = new ListStack<>();

        System.out.println("1,2,3,4,5 순으로 push()");
        listStack.push(1);
        listStack.push(2);
        listStack.push(3);
        listStack.push(4);
        listStack.push(5);

        System.out.print("stack 가장 위에 있는 데이터: ");
        System.out.println(listStack.peek());
        
        while(!listStack.isEmpty()){
            System.out.print("pop된 데이터: ");
            System.out.println(listStack.pop());
        }

        //ArrayIndexOutOfBoundsException 예외 발생
//        System.out.print("pop된 데이터: ");
//        System.out.println(listStack.pop());

    }
}

 

- 실행 결과 - 

 

전체 코드

https://github.com/you88311/data-structure/tree/main/stack/src

GitHub - you88311/data-structure

 

 

---

참고

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼

 

c언어로 쉽게 풀어쓴 자료구조 - 천인국, 공용해, 하상호