자료구조: 스택(Stack)

1. 개요 (Introduction)

Stack은 데이터가 순서대로 쌓이고 제거되는 자료구조로, LIFO(Last-In-First-Out) 원칙을 따릅니다. 이는 가장 마지막에 추가된 요소가 가장 먼저 제거되는 특성으로, 마치 접시를 쌓아 올리고 하나씩 꺼내는 방식과 유사합니다. Stack은 주로 메모리 관리, 수식 계산, 웹 브라우저의 뒤로 가기 기능 등 여러 분야에서 활용됩니다.

https://www.geeksforgeeks.org/stack-data-structure/

 

2. Stack의 활용 예시 (Use Cases of Stack)

Stack은 일상적인 문제 해결과 알고리즘에서 자주 사용되는 자료구조입니다.

• 함수 호출 관리: 프로그래밍 언어의 런타임 시스템은 Stack을 사용하여 함수 호출을 관리합니다. 함수가 호출될 때마다 Stack에 새로운 프레임이 쌓이며, 함수가 끝나면 Stack에서 제거되어 호출한 함수로 돌아갑니다.
• 미로 탐색 및 경로 찾기: DFS(깊이 우선 탐색) 알고리즘에서 Stack을 사용하여 미로에서 가능한 경로를 찾거나 그래프 탐색을 수행할 수 있습니다.
• 문자열 역순 처리: 문자열을 Stack에 넣고 하나씩 Pop하여 역순으로 만들 수 있습니다.
• 수식의 괄호 짝 확인: 프로그래밍 언어의 구문 분석기 또는 컴파일러에서 Stack을 사용하여 수식의 괄호가 올바르게 열리고 닫혔는지 확인할 수 있습니다.

3. Stack의 동작 (Operations of Stack)

Stack은 주로 다음과 같은 동작을 제공합니다:

• Push: Stack의 맨 위에 새로운 데이터를 추가합니다.
• Pop: Stack의 맨 위 데이터를 제거하고 반환합니다. Stack이 비어 있을 경우 예외를 발생시킬 수 있습니다.
• Peek 또는 Top: Stack의 맨 위 데이터를 제거하지 않고 반환하여 Stack의 현재 상태를 확인할 수 있습니다.
• IsEmpty: Stack이 비어 있는지 확인하는 연산으로, 조건문에서 활용할 수 있습니다. 이러한 연산들은 대부분 O(1) 시간 복잡도로 수행되며, 간단하지만 매우 강력한 데이터 처리 방식을 제공합니다.

4. Golang으로 Stack 구현하기

Golang에서는 Stack 자료구조를 내장된 구조로 제공하지 않지만, 배열이나 slice를 활용하여 구현할 수 있습니다. slice는 크기가 동적으로 변하며, 요소를 쉽게 추가하고 제거할 수 있어 Stack을 표현하기에 적합합니다.

type Stack []int

// Push 연산: Stack의 맨 위에 새로운 요소를 추가합니다.
func (s *Stack) Push(v int) {
    *s = append(*s, v)  // slice에 새로운 요소를 추가하여 Stack을 확장
}

// Pop 연산: Stack의 맨 위 요소를 제거하고 반환합니다.
func (s *Stack) Pop() (int, bool) {
    if len(*s) == 0 {  // Stack이 비어있는지 확인
        return 0, false  // 비어있다면 기본값과 false를 반환
    }
    index := len(*s) - 1  // 마지막 인덱스를 찾음
    element := (*s)[index]  // 마지막 요소를 저장
    *s = (*s)[:index]  // 마지막 요소를 제외하고 slice 재조정
    return element, true  // 제거된 요소와 true 반환
}

// Peek 연산: Stack의 맨 위 요소를 제거하지 않고 반환합니다.
func (s *Stack) Peek() (int, bool) {
    if len(*s) == 0 {
        return 0, false
    }
    return (*s)[len(*s)-1], true
}

// IsEmpty 연산: Stack이 비어 있는지 확인합니다.
func (s *Stack) IsEmpty() bool {
    return len(*s) == 0
}

func main() {
    stack := Stack{}

    stack.Push(10)
    stack.Push(20)
    stack.Push(30)

    fmt.Println(stack.Peek())  // Output: 30, true
    fmt.Println(stack.Pop())   // Output: 30, true
    fmt.Println(stack.Pop())   // Output: 20, true
    fmt.Println(stack.IsEmpty()) // Output: false
    fmt.Println(stack.Pop())   // Output: 10, true
    fmt.Println(stack.IsEmpty()) // Output: true
}

코드 설명:

• Push 메서드: slice에 append를 사용하여 새 요소를 추가합니다. 이는 Stack의 맨 위에 요소를 넣는 것과 동일한 효과를 냅니다.
• Pop 메서드: Stack이 비어 있는 경우를 먼저 확인한 후, 마지막 요소를 변수에 저장하고 slice를 재조정하여 그 요소를 제거합니다. 최종적으로 제거된 요소와 true를 반환합니다.
• Peek 메서드: Stack의 맨 위 요소를 반환하지만, 요소를 제거하지는 않습니다.
• IsEmpty 메서드: Stack이 비어 있는지 확인하는 부가적인 메서드로, 비어 있을 경우 true를 반환합니다.

Golang에서 제네릭을 활용한 Stack 구현

package main

import "fmt"

// 제네릭 Stack 정의
type Stack[T any] struct {
    elements []T
}

// Push 메서드
func (s *Stack[T]) Push(value T) {
    s.elements = append(s.elements, value)
}

// Pop 메서드
func (s *Stack[T]) Pop() (T, bool) {
    var zero T
    if len(s.elements) == 0 {
        return zero, false
    }
    lastIndex := len(s.elements) - 1
    value := s.elements[lastIndex]
    s.elements = s.elements[:lastIndex]
    return value, true
}

// Peek 메서드
func (s *Stack[T]) Peek() (T, bool) {
    var zero T
    if len(s.elements) == 0 {
        return zero, false
    }
    return s.elements[len(s.elements)-1], true
}

// IsEmpty 메서드
func (s *Stack[T]) IsEmpty() bool {
    return len(s.elements) == 0
}

func main() {
    var stack Stack[int]
    stack.Push(10)
    stack.Push(20)
    fmt.Println(stack.Peek())    // Output: 20, true
    fmt.Println(stack.Pop())     // Output: 20, true
    fmt.Println(stack.IsEmpty()) // Output: false
}

Stack에서 append와 slicing 사용

Stack은 LIFO(Last In, First Out) 구조이므로, 마지막에 추가된 요소를 가장 먼저 제거합니다. 이를 위해 append로 요소를 추가하고, slicing을 통해 마지막 요소를 제거합니다.

type Stack[T any] struct {
    elements []T
}

func (s *Stack[T]) Push(value T) {
    s.elements = append(s.elements, value)  // append로 요소 추가
}

func (s *Stack[T]) Pop() (T, bool) {
    var zero T
    if len(s.elements) == 0 {
        return zero, false
    }
    lastIndex := len(s.elements) - 1
    value := s.elements[lastIndex]
    s.elements = s.elements[:lastIndex] // slicing으로 마지막 요소 제거
    return value, true
}

 

• Push에서는 append를 사용해 요소를 Stack의 맨 끝에 추가합니다.
• Pop에서는 slicing을 통해 맨 끝 요소를 제거합니다.

 

5. Java로 Stack 구현하기

Java에서는 java.util.Stack 클래스를 통해 기본적인 Stack 구현을 제공합니다. 이 클래스는 LIFO 원칙을 따르며, Push와 Pop 같은 기본 연산을 포함하여 매우 직관적으로 사용할 수 있습니다.

import java.util.Stack;

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

        // Push 연산: Stack의 맨 위에 요소 추가
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // Peek 연산: Stack의 맨 위 요소 확인
        System.out.println("Top element: " + stack.peek());  // Output: 30

        // Pop 연산: Stack의 맨 위 요소 제거
        System.out.println("Removed element: " + stack.pop());  // Output: 30
        System.out.println("Removed element: " + stack.pop());  // Output: 20

        // IsEmpty 연산: Stack이 비어있는지 확인
        System.out.println("Is stack empty? " + stack.isEmpty());  // Output: false
        stack.pop();
        System.out.println("Is stack empty? " + stack.isEmpty());  // Output: true
    }
}

ArrayDeque로 Stack 대체 구현: Java의 java.util.Stack 클래스는 비교적 오래된 자료구조로 성능이 최적화되지 않은 면이 있습니다. 대신 ArrayDeque를 사용하여 Stack을 대체하는 것이 일반적이며, 이 경우 Stack의 모든 연산을 동일하게 수행할 수 있으면서 더 나은 성능을 제공합니다.

import java.util.ArrayDeque;
import java.util.Deque;

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

        // Push 연산
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // Peek 연산
        System.out.println("Top element: " + stack.peek());  // Output: 30

        // Pop 연산
        System.out.println("Removed element: " + stack.pop());  // Output: 30
        System.out.println("Removed element: " + stack.pop());  // Output: 20

        // IsEmpty 연산
        System.out.println("Is stack empty? " + stack.isEmpty());  // Output: false
        stack.pop();
        System.out.println("Is stack empty? " + stack.isEmpty());  // Output: true
    }
}

코드 설명:

• Push 연산: push() 메서드를 사용하여 Stack의 맨 위에 요소를 추가합니다.
• Pop 연산: pop() 메서드는 Stack의 맨 위 요소를 제거하고 반환합니다. 빈 Stack에서 호출하면 예외가 발생하므로 주의가 필요합니다.
• Peek 연산: peek() 메서드는 Stack의 맨 위 요소를 제거하지 않고 반환합니다.
• IsEmpty 연산: isEmpty() 메서드는 Stack이 비어 있는지 여부를 반환하여 Stack 상태를 확인하는 데 유용합니다.

ArrayDeque는 Stack을 구현할 때 java.util.Stack보다 가볍고 효율적이기 때문에 대체 구현으로 추천됩니다.

6. Stack의 시간 복잡도 (Time Complexity of Stack Operations)

Stack 자료구조의 각 연산은 효율적이며, 대부분의 경우 O(1) 시간 복잡도를 가집니다. 이는 Stack이 LIFO 구조로 동작하여 데이터의 추가 및 제거가 Stack의 맨 위에서만 이루어지기 때문입니다. 각 연산의 시간 복잡도를 구체적으로 살펴보겠습니다.

1. Push (삽입) 연산 - O(1)

• 설명: Push 연산은 Stack의 맨 위에 요소를 추가하는 작업입니다. 일반적으로 Stack의 배열 또는 리스트 끝에 새로운 요소를 추가하는 방식으로 이루어지며, 이때 요소를 찾거나 정렬하지 않고 마지막 위치에 추가하기만 하면 되므로 O(1) 시간 복잡도를 가집니다.
• 예외 상황: 만약 Stack이 배열 기반으로 구현되어 있고 배열의 크기를 초과하게 되면, 배열의 크기를 늘리기 위해 새로운 메모리를 할당하고 기존 요소를 복사해야 합니다. 이 경우 재할당 시에는 O(n) 시간이 걸리지만, 이는 전체 연산에서 드물게 발생하는 일이므로, 평균적으로는 O(1) 시간 복잡도를 갖습니다.

2. Pop (삭제) 연산 - O(1)

• 설명: Pop 연산은 Stack의 맨 위 요소를 제거하고 반환하는 작업입니다. Stack의 마지막 요소만을 참조하여 제거하기 때문에 O(1) 시간 복잡도를 가집니다. 배열이나 리스트에서 요소를 제거해도 메모리의 나머지 요소들을 이동할 필요가 없기 때문에 매우 빠르게 수행됩니다.
• 주의 사항: Stack이 비어 있는 상태에서 Pop 연산을 수행하려고 하면, 일반적으로 예외를 발생시키거나 에러 처리를 해야 합니다. 이를 위해 비어 있는지 확인하는 검사 작업이 추가될 수 있지만, 이 또한 상수 시간에 해결될 수 있습니다.

3. Peek (최상단 요소 확인) 연산 - O(1)

• 설명: Peek 연산은 Stack의 맨 위 요소를 반환하는 작업입니다. 요소를 반환할 때 Stack에서 제거하지 않으며, 단순히 마지막 위치의 요소를 참조하여 반환하기만 하므로 O(1) 시간 복잡도를 가집니다.
• 예외 처리: Stack이 비어 있는 상태에서 Peek을 수행할 경우, Pop과 마찬가지로 에러를 처리하거나 기본값을 반환하는 코드가 추가될 수 있습니다.

4. IsEmpty (비어있는지 확인) 연산 - O(1)

• 설명: IsEmpty 연산은 Stack이 비어 있는지를 확인하는 연산입니다. 이는 Stack의 크기 또는 상태를 확인하는 간단한 작업으로, 단순히 크기가 0인지 비교하거나 비어 있는지 확인하는 작업이므로 O(1) 시간 복잡도를 가집니다.
• 활용: Pop 또는 Peek 연산 전에 Stack이 비어 있는지 확인하는 데 자주 사용됩니다.

Stack의 효율성과 한계

Stack은 데이터의 추가 및 제거가 매우 빠르고, 상수 시간에 수행될 수 있어 메모리 관리와 계산 시 효율적입니다. 하지만 다음과 같은 한계도 존재합니다:

1. 중간 데이터 접근의 한계: Stack은 LIFO 구조이기 때문에, 맨 위에 있는 데이터 외에는 중간 데이터를 직접 참조하거나 수정할 수 없습니다. 따라서 Stack에 저장된 중간 데이터에 접근하려면 모든 요소를 하나씩 꺼내야 하므로 O(n) 시간이 걸립니다.
2. 고정 크기 Stack의 메모리 제한: 배열 기반의 Stack은 고정된 크기로 정의될 때 메모리 한계가 발생할 수 있습니다. 이러한 경우, Stack이 가득 차면 더 큰 배열을 할당해야 하므로 공간과 시간이 추가로 소요됩니다.
3. 한 방향성의 자료 흐름: Stack은 오직 한 방향으로만 데이터를 추가 및 삭제할 수 있는 구조이므로, 양방향으로 데이터를 다뤄야 하는 경우에는 큐(Queue)나 이중 연결 리스트 같은 다른 자료구조가 더 적합할 수 있습니다.

Stack의 시간 복잡도와 다른 자료구조 비교

Stack과 같은 선형 자료구조 중 Queue와의 시간 복잡도를 비교하면 다음과 같은 차이점이 있습니다:

• Stack과 Queue는 모두 O(1) 시간 복잡도의 삽입 및 삭제 연산을 제공하지만, Queue는 FIFO(First-In-First-Out) 방식으로 동작하여 처음 들어온 요소가 먼저 제거되는 반면, Stack은 LIFO(Last-In-First-Out) 방식으로 마지막에 들어온 요소가 먼저 제거됩니다.

7. Stack을 활용한 문제 해결 (Problem Solving with Stack)

Stack을 활용하여 다양한 문제를 해결할 수 있습니다:

• 괄호 유효성 검사: 여는 괄호는 Push하고 닫는 괄호는 Pop하여 괄호가 올바른지 검사합니다.
• 중위/후위 표기법 변환: Stack을 사용하여 중위 표기법을 후위 표기법으로 변환하거나 계산을 수행할 수 있습니다.
• Daily Temperature 문제: 각 날짜의 온도가 이전과 비교하여 더 높은 온도가 나오기까지 걸리는 날 수를 구하는 문제입니다. Stack을 활용하여 이전 온도와 비교하여 해결할 수 있습니다.

8. Stack 사용 시 주의점 및 Best Practices

Stack 자료구조를 사용할 때는 다음과 같은 주의사항이 필요합니다:

• Stack Overflow 방지: 재귀 함수 또는 무한히 많은 데이터를 Stack에 추가할 경우 Stack Overflow가 발생할 수 있습니다. 특히 재귀를 사용할 때는 호출이 너무 깊어지지 않도록 유의해야 합니다.
• 가독성: Stack을 활용한 코드는 때때로 직관적이지 않을 수 있습니다. 예를 들어 수식 계산처럼 복잡한 로직에서는 Stack의 동작을 명확히 이해하고, 주석을 활용하여 코드를 문서화하는 것이 좋습니다.

9. 결론 (Conclusion)

Stack은 간단하지만 강력한 자료구조로, 다양한 문제 해결에 적용될 수 있습니다. Golang과 Java를 통해 Stack을 구현하고 활용해 보면서, 자료구조의 기본 개념과 응용력을 향상시킬 수 있습니다.