[자료구조] 스택(Stack) 자료구조 알아보기 & Java 예제 코드

오늘은 자료구조 중 Stack에 대해 정리해봤다.

 

---

 

스택(Stack)이란?

자료구조 중 하나로 후입선출(Last-In-First-Out, LIFO) 원칙에 따라 데이터를 저장하는 추상 자료형이다. 스택은 데이터를 저장하는 컨테이너로 데이터를 추가하거나 제거할 수 있다.

주요 연산을 살펴보면 다음과 같다.

1. push : 스택에 데이터를 추가하는 연산이다. 스택의 맨 위에 데이터를 삽입한다.
2. pop : 스택에서 데이터를 제거하는 연산이다. 스택의 맨 위에서 데이터를 삭제하고 반환한다.
3. peek 또는 top : 스택의 맨 위에 있는 데이터를 반환하지만, 스택에서 제거하지는 않는다.
4. isEmpty : 스택이 비어있는지 확인하는 연산이다.
5. size : 스택에 저장된 데이터의 개수를 반환한다.

출처 : https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

 

 

스택(Stack)의 장점 및 단점

장점

1. 단순하고 간단한 구조 : 스택은 간단한 원칙에 따라 동작하는 자료구조로 구현이 비교적 쉽다. 데이터의 추가와 제거가 매우 빠르게 이뤄진다.
2. 메모리 관리 용이 : 스택은 정해진 크기의 메모리를 사용하므로 메모리 관리가 간단하다. 필요한 만큼의 공간만 사용하고 남는 공간이 없다.

 

단점

1. 크기 제한 : 스택은 정적인 크기를 가지고 있어 크기가 제한되어 있다. 크기를 초과해 데이터를 추가할 수 없는 경우에는 오버플로우(overflow)가 발생한다.
2. 중간 데이터 접근의 어려움 : 스택의 원칙에 따라 데이터는 맨 위에서만 추가되고 제거된다. 중간에 있는 데이터에 접근하거나 수정하기 위해서는 맨 위의 데이터들을 순차적으로 제거해야 한다. 중간 데이터에 빈번한 접근이 필요한 경우에는 스택은 효율적인 자료구조는 아니다.
3.  

스택은 주로 함수 호출(Call Stack), 재귀 알고리즘, 뒤로 가기 기능 등에서 활용된다.

데이터를 일시적으로 저장하고 나중에 역순으로 처리해야 할 때 유용한 자료구조다.

 

 

 

Stack 예시 코드(Java)

먼저 Java에서 제공하는 Stack 클래스 먼저 확인해보자.

Stack 클래스는 java.util 패키지에 포함되어 있다.

아래는 Java의 Stack 클래스를 사용하는 예시 코드다.

 

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("스택 크기: " + stack.size()); // 출력: 3
        System.out.println("맨 위 데이터: " + stack.peek()); // 출력: 30

        System.out.println("Pop한 데이터: " + stack.pop()); // 출력: 30
        System.out.println("Pop한 데이터: " + stack.pop()); // 출력: 20
        System.out.println("스택이 비어있는지 확인: " + stack.isEmpty()); // 출력: false
    }
}

 

java.util.Stack 클래스를 사용해 스택을 생성한다.

제네릭(Generic)을 사용해 Stack에 저장되는 데이터의 타입을 지정할 수 있다.

위의 예시에서는 Integer 타입의 데이터를 저장하는 스택을 생성했다.

 

 

이제 이 Stack의 구현부를 좀 더 면밀히 살펴보자.

 

Java에서 스택을 구현하기 위해서는 기본적으로 배열(Array) 또는 연결 리스트(Linked List)를 사용할 수 있다.

 

배열(Array)을 이용한 스택(Stack)

아래는 Java에서 배열(Array)을 이용해 스택을 구현한 예시 코드다.

public class Stack {
    private int maxSize; // 스택의 최대 크기
    private int top; // 스택의 맨 위 인덱스
    private int[] stackArray; // 스택을 위한 배열

    public Stack(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1; // 스택이 비어있는 상태를 나타내기 위해 -1로 초기화
    }

    public void push(int data) {
        if (top == maxSize - 1) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }
        stackArray[++top] = data; // 스택의 맨 위에 데이터 추가
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("스택이 비어있습니다.");
            return -1;
        }
        return stackArray[top--]; // 스택의 맨 위 데이터 제거 후 반환
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어있습니다.");
            return -1;
        }
        return stackArray[top]; // 스택의 맨 위 데이터 반환
    }

    public boolean isEmpty() {
        return (top == -1); // 스택이 비어있는지 확인
    }

    public int size() {
        return top + 1; // 스택에 저장된 데이터의 개수 반환
    }
}

Stack 클래스가 정수형 데이터를 저장하는 배열을 사용하여 스택을 구현한다.

 

아래는 위에서 구현한 Stack 클래스를 사용한 예시 코드다.

public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack(5); // 크기가 5인 스택 생성

        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("스택 크기: " + stack.size()); // 출력: 3
        System.out.println("맨 위 데이터: " + stack.peek()); // 출력: 30

        System.out.println("Pop한 데이터: " + stack.pop()); // 출력: 30
        System.out.println("Pop한 데이터: " + stack.pop()); // 출력: 20
        System.out.println("스택이 비어있는지 확인: " + stack.isEmpty()); // 출력: false
    }
}

 

 

연결 리스트(Linked List)를 이용한 스택(Stack)

아래는 Java에서 연결 리스트(Linked List)를 이용해 스택을 구현한 예시 코드다.

public class Stack {
    private Node top; // 스택의 맨 위 노드

    private class Node {
        int data;
        Node next;

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

    public void push(int data) {
        Node newNode = new Node(data); // 새로운 노드 생성

        if (isEmpty()) {
            top = newNode; // 스택이 비어있을 경우 새로운 노드를 맨 위로 설정
        } else {
            newNode.next = top; // 새로운 노드의 다음 노드로 현재의 top을 설정
            top = newNode; // 새로운 노드를 스택의 맨 위로 설정
        }
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("스택이 비어있습니다.");
            return -1;
        }

        int poppedData = top.data; // 스택의 맨 위 데이터 저장
        top = top.next; // top을 다음 노드로 이동하여 맨 위를 변경
        return poppedData; // 저장한 데이터 반환
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어있습니다.");
            return -1;
        }

        return top.data; // 스택의 맨 위 데이터 반환
    }

    public boolean isEmpty() {
        return (top == null); // 스택이 비어있는지 확인
    }

    public int size() {
        int count = 0;
        Node currentNode = top;
        while (currentNode != null) {
            count++;
            currentNode = currentNode.next;
        }
        return count; // 스택에 저장된 데이터의 개수 반환
    }
}

Stack 클래스 내부에 Node 클래스를 정의해 연결 리스트를 구성한다.

 

아래는 위에서 구현한 Stack 클래스를 사용하는 예시 코드다.

public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack(5); // 크기가 5인 스택 생성

        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("스택 크기: " + stack.size()); // 출력: 3
        System.out.println("맨 위 데이터: " + stack.peek()); // 출력: 30

        System.out.println("Pop한 데이터: " + stack.pop()); // 출력: 30
        System.out.println("Pop한 데이터: " + stack.pop()); // 출력: 20
        System.out.println("스택이 비어있는지 확인: " + stack.isEmpty()); // 출력: false
    }
}

 

 

그렇다면 Stack을 구현할 때 Array와 Linked List 중 어떤 방법을 사용하는 것이 좋을까?

개인적으로는 배열(Array)를 사용하는 것이 좋다고 생각한다.

 

배열(Array)을 사용한 스택 구현은 간단하고 효율적이다.

• 스택의 기본 연산인 push와 pop을 상수 시간(O(1))에 수행할 수 있고,
• 메모리 상에 연속적으로 요소를 저장하기 때문에 메모리 캐시 효율성이 높아 성능적으로 우수하다.
• 또한, 인덱스를 사용해 요소에 빠르게 접근할 수 있다.
• 따라서 데이터를 스택에 추가하거나 삭제할 때 배열의 인덱스를 조정, 즉, 배열의 맨 끝에 데이터를 추가하거나 제거할 수 있으므로 단순하고 빠른 구현이 가능하다.
•  

연결 리스트(Linked List)를 사용한 스택 구현은 배열에 비해 메모리 사용량이 더 많고 포인터 연산이 추가로 필요하기 때문에 성능적으로 좀 떨어질 수 있다.

• push와 pop 연산은 여전히 O(1) 시간 복잡도를 가지지만,
• 추가적인 포인터 조정이 필요해 배열보다는 더 많은 작업이 수행되어야 한다.
• 하지만 스택의 크기가 동적으로 변해야 하거나 스택의 크기가 미리 알려지지 않을 때 유용하다.
• 따라서 Linked List를 사용한 스택은 동적 크기 조절이 용이하고, 메모리 할당과 해제가 유연하게 이루어질 수 있으며, 데이터의 삽입과 삭제가 빈번하게 발생하는 경우에 선택할 수 있다.

 

 

개인적으로 헷갈렸던 부분은

‘그래서 데이터의 삽입과 삭제에서 더 효율적인 건 배열과 연결 리스트 중 무엇인가?’였다.

 

정리해보면 다음과 같다.

 

배열(Array)을 사용한 스택 구현은

• 인덱스를 통해 데이터에 빠르게 접근할 수 있어 데이터의 추가와 삭제는 비교적 간단하게 이루어질 수 있다.
• 하지만 데이터의 추가와 삭제에는 데이터 이동이 필요하므로 효율성 면에서는 제한이 있을 수 있다.

 

반면 연결 리스트(Linked List)를 사용한 스택 구현은

• 인덱스가 없어 데이터에 접근하는 데는 배열에 비해 비효율적일 수 있다.
• 하지만 데이터의 추가와 삭제 연산 자체는 데이터 이동이 필요하지 않아 효율적이다.
•  

따라서, 배열을 사용한 스택은 데이터 접근 속도가 중요하고 크기가 정해진 경우에 유리할 수 있다.

반면에 데이터의 추가와 삭제가 빈번하게 발생하거나 크기의 제한이 없는 상황에서는 연결 리스트를 사용한 스택이 효율적일 수 있다.

 

스택 구현 시 배열과 연결 리스트 중의 선택은 구현해야 하는 기능과 상황에 따라 유연하게 이루어져야 할 것 같다.