스택(Stack) - Array와 LinkedList로 구현

스택이란?

LIFO(Last In First Out) 구조를 갖는 자료구조를 말한다. 즉, 나중에 삽입된 데이터가 먼저 삭제되는 구조이다.

데이터를 일시적으로 저장할 때 매우 유용한 선형 데이터 구조이다.

 

 

 

스택 연산

스택에는 push, pop과 같은 주요 연산과 peek(top), empty, size 등의 연산을 가질 수 있다.

 

1. push:
   스택의 맨 위에 데이터를 삽입하는 연산
2. pop:
   스택의 맨 위에 있는 데이터를 삭제하고 반환하는 연산
3. peek 또는 top:
   스택의 맨 위에 있는 데이터를 삭제하지 않고 반환하는 연산
4. empty:
   스택이 비어 있는지를 확인하는 연산
5. size:
   스택에 있는 데이터의 개수를 반환하는 연산

 

 

 

구현

스택은 배열이나 연결리스트를 사용하여 구현할 수 있다.

데이터 크기 예측 가능한 경우         ->   배열
메모리 사용이 제한된 환경             ->   배열
데이터 크기 미리 예측 불가/가변적 ->   연결리스트

 

 

 

배열을 사용한 구현

• 배열을 사용하면 인덱스를 이용해 빠르게 맨 위 요소를 쉽게 접근할 수 있다. 
• 또한 연결리스트에 비해 비교적 단순하고 직관적으로 구현 가능하다.
• 배열은 알아서 메모리 관리가 이루어지므로 추가적인 포인터 관리가 필요하지 않다.
• 배열은 연속된 메모리 블록에 저장되므로, 각 요소에 대한 추가 메모리 오버헤드가 없다.
• 스택의 크기를 미리 정해야한다는 단점이 있다.

class ArrayStack {
    private int maxSize;
    private int top;
    private int[] stackArray;

    public ArrayStack(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1;
    }

    public void push(int value) {
        if (top == maxSize - 1) {
            throw new StackOverflowError("Stack is full");
        }
        stackArray[++top] = value;
    }

    public int pop() {
        if (top == -1) {
            throw new EmptyStackException();
        }
        return stackArray[top--];
    }

    public int peek() {
        if (top == -1) {
            throw new EmptyStackException();
        }
        return stackArray[top];
    }

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

    public int size() {
        return top + 1;
    }
}

 

 

연결리스트를 사용한 구현

• 연결리시트는 필요에 따라 크기를 동적으로 조절할 수 있다.
• 필요한 만큼 메모리를 할당하므로, 배열에서 발생할 수 있는 미사용 공간의 낭비가 없다.
• 각 요소가 다른 메모리 위치에 저장되므로, 배열보다 접근시간이 느릴 수 있다.
• pop과 push  연산에 별도의 포인터가 필요하다

class ListNode {
    int value;
    ListNode next;

    ListNode(int value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedListStack {
    private ListNode top;

    public LinkedListStack() {
        top = null;
    }

    public void push(int value) {
        ListNode newNode = new ListNode(value);
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (top == null) {
            throw new EmptyStackException();
        }
        int value = top.value;
        top = top.next;
        return value;
    }

    public int peek() {
        if (top == null) {
            throw new EmptyStackException();
        }
        return top.value;
    }

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

    public int size() {
        int size = 0;
        ListNode current = top;
        while (current != null) {
            size++;
            current = current.next;
        }
        return size;
    }
}

 

 

 

스택 활용

 

• 함수 호출 스택:
  • 함수 호출과 복귀 주소를 관리하는 데 사용. 호출된 함수는 스택에 push, 함수가 반환되면 스택에서 pop
• 괄호 균형 검사:
  • 프로그램의 괄호가 균형을 이루는지 검사할 때 사용. 여는 괄호는 스택에 push, 닫는 괄호는 스택에서 pop.
• 백트래킹 알고리즘:
  • 미로 탐색, 퍼즐 해결 등 경로를 추적하는 데 사용. 현재 경로를 스택에 저장하고, 잘못된 경로를 pop하여 이전 상태로 돌아감.
• 후위 표현식:
  • 수학적 표현식을 변환하는 알고리즘에서 사용. 중위 표현식을 후위 또는 전위 표현식으로 변환하는 과정에서 사용.