선형 자료구조: 스택(Stack)

vita12321 2023. 8. 21. 09:00

728x90

이 글에서는 선형 자료구조 중 하나인 스택(stack)에 대해 더욱 방대한 설명과 자바에서 스택을 사용하여 직접 구현한 예제 코드를 제공해 드리겠습니다.스택의 개념과 원리를 살펴본 뒤, 자바에서 스택을 사용하는 방법과 기본 연산에 대해 알아보겠습니다. 이어서 배열 기반 스택 구현과 연결리스트 기반 스택 구현의 예시를 들겠습니다.

1. 스택의 개념 및 원리

스택(stack)은 "Last In, First Out" (LIFO) 원칙에 따라 동작하는 선형 자료구조입니다. 즉, 가장 최근에 삽입된 데이터가 가장 먼저 삭제되는 구조를 가지고 있습니다. 스택은 데이터의 삽입과 삭제가 상단(top)으로 한정되기 때문에 구현이 간단하고 에러 발생 가능성이 낮습니다. 스택은 함수 호출과 메모리 관리에서 활용되며, 깊이 우선 탐색(DFS) 알고리즘, 후위 표기법(Postfix notation) 등 다양한 알고리즘에서 사용됩니다.

스택의 장점:

구현이 간단하며 에러 발생 가능성이 낮음
함수 호출과 메모리 관리에 유용
스택 기반 알고리즘에서 활용도가 높음

스택의 단점:

데이터 저장 용량이 제한적일 수 있음 (배열 기반 스택의 경우)
데이터 삽입과 삭제 위치 제한

2. 자바에서의 스택 사용법 및 주요 기능

자바에서 스택을 구현하려면 java.util.Stack 클래스를 사용할 수 있습니다. Stack 클래스는 다양한 자료형을 저장할 수 있도록 제네릭 형태로 제공됩니다.

스택 생성 및 초기화:

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

스택에 요소 추가 (push 연산):

stack.push(1);

stack.push(2);

stack.push(3);

스택에서 요소 제거 및 반환 (pop 연산):

int poppedElement = stack.pop(); // 3 반환

스택의 가장 상단 요소 반환 (peek 연산):

int topElement = stack.peek(); // 2 반환

스택이 비어있는지 확인 (empty 연산):

boolean isEmpty = stack.empty(); // false 반환

스택의 크기 확인:

int size = stack.size(); // 스택 크기 반환

3. 자바 배열 기반 스택 구현 예시

다음 예제는 배열을 이용하여 스택을 구현한 코드입니다.

public class ArrayStack {

    private int maxSize;

    private int top;

    private int[] stackArray;

 

    public ArrayStack(int maxSize) {

        this.maxSize = maxSize;

        this.stackArray = new int[maxSize];

        this.top = -1;

    }

 

    public void push(int value) {

        if (top < maxSize - 1) {

            stackArray[++top] = value;

        } else {

            System.out.println("Stack is full. Cannot push.");

        }

    }

 

    public int pop() {

        if (top >= 0) {

            return stackArray[top--];

        } else {

            System.out.println("Stack is empty. Cannot pop.");

            return -1;

        }

    }

 

    public int peek() {

        if (top >= 0) {

            return stackArray[top];

        } else {

            System.out.println("Stack is empty. Cannot peek.");

            return -1;

        }

    }

 

    public boolean isEmpty() {

        return top == -1;

    }

 

    public int size() {

        return top + 1;

    }

}

4. 자바 연결리스트 기반 스택 구현 예시

다음 예제는 연결리스트를 이용하여 스택을 구현한 코드입니다.

public class LinkedListStack<T> {

    private static class StackNode<T> {

        private T data;

        private StackNode<T> next;

 

        public StackNode(T data) {

            this.data = data;

        }

    }

 

    private StackNode<T> top;

 

    public void push(T value) {

        StackNode<T> newNode = new StackNode<>(value);

        newNode.next = top;

        top = newNode;

    }

 

    public T pop() {

        if (top == null) {

            System.out.println("Stack is empty. Cannot pop.");

            return null;

        }

        T value = top.data;

        top = top.next;

        return value;

    }

 

    public T peek() {

        if (top == null) {

            System.out.println("Stack is empty. Cannot peek.");

            return null;

        }

        return top.data;

    }

 

    public boolean isEmpty() {

        return top == null;

    }

 

    public int size() {

        int count = 0;

        StackNode<T> current = top;

        while (current != null) {

            count++;

            current = current.next;

        }

        return count;

    }

}

5. 결론

이 글에서는 선형 자료구조 중 하나인 스택에 대해 자세히 설명하였습니다. 구현의 간단함과 LIFO 원칙에 따른 높은 활용도로 인해 스택은 다양한 분야에서 활용됩니다. 자바의 기본 Stack 클래스를 사용하는 방법 외에도, 배열 기반 스택과 연결리스트 기반 스택을 구현하는 방법을 소개하였습니다. 이런 다양한 구현 방식을 숙지하여 문제 상황에 맞게 적절한 자료구조를 선택하고 활용하는 능력을 기르실 수 있길 바랍니다.

728x90