📌 서론.

스택, 큐, 덱은 특정 위치에서만 원소를 넣거나 뺄 수 있는 Restricted Structure 중 하나인 스택에 대해 배워보자.

스택이란?

• 한쪽 끝에서만 요소를 넣고 뺄 수 있는 자료구조.
• 후입선출 구조를 가진다. → LIFO(Last In First Out)

스택의 성질

스택의 성질	시간 복잡도
원소의 추가	O(1)
원소의 제거	O(1)
제일 상단 원소 확인	O(1)
제일 상단이 아닌 나머지 원소 확인	불가능

• 원소의 추가 O(1)
• 원소의 제거 O(1)
• 제일 상단 원소 확인 O(1)
• 제일 상단이 아닌 나머지 원소의 확인은 (원칙적으로) 불가능
  • 단! 배열을 기반으로 구현해서 확인은 가능. (해당 경우 시간 복잡도는 O(1))

스택 구현

• 배열 혹은 연결 리스트를 사용해서 구현할 수 있다. (배열을 사용한 구현이 더 쉬움)

배열을 통한 구현

package PracStack;

class ArrayStack {
  private int[] stack;
  private int top;
  private int capacity;

  public ArrayStack(int capacity) {
    this.capacity = capacity;
    stack = new int[capacity];
    top = -1;
  }

  public void push(int data) {
    if (isFull()) {
      throw new IllegalStateException("Stack is full");
    }
    stack[++top] = data;
  }

  public int pop() {
    if (isEmpty()) {
      throw new IllegalStateException("Stack is empty");
    }
    return stack[top--];
  }

  public int peek() {
    if (isEmpty()) {
      throw new IllegalStateException("Stack is empty");
    }
    return stack[top];
  }

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

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

  public static void main(String[] args) {
    ArrayStack stack = new ArrayStack(5); // 배열이기에 capacity를 정의해줘야함.
    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.push(30);
    stack.push(30);
    // stack.push(30); -> 주어진 capacity 이상 넣을 순 없음.

    System.out.println(stack.pop()); // 30
    System.out.println(stack.peek()); // 20
    System.out.println(stack.pop()); // 20
  }
}

배열을 통해 구현한 Stack은 정적 배열 이기에 capacity를 정의해주어야 한다.

하지만 우리는 Java에서 스택 자료구조를 쓸 때 capacity를 정의하지는 않는다.

이걸 구현하려면 연결 리스트로 만들어야한다.

LinkedList로 스택 구현.

class LinkedListStack {
  private static class Node {
    int data;
    Node next;

    Node(int data) {
      this.data = data;
      this.next = null;
    }
  }

  private Node top;

  public LinkedListStack() {
    this.top = null;
  }

  public void push(int data) {
    Node newNode = new Node(data);
    newNode.next = top;
    top = newNode;
  }

  public int pop() {
    if (isEmpty()) {
      throw new IllegalStateException("Stack is empty");
    }
    int data = top.data;
    top = top.next;
    return data;
  }

  public int peek() {
    if (isEmpty()) {
      throw new IllegalStateException("Stack is empty");
    }
    return top.data;
  }

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

  public static void main(String[] args) {
    LinkedListStack stack = new LinkedListStack();
    stack.push(10);
    stack.push(20);
    stack.push(30);

    System.out.println(stack.pop()); // 30
    System.out.println(stack.peek()); // 20
    System.out.println(stack.pop()); // 20
  }
}

🎯 결론.

스택은 데이터를 한 곳에서만 추가하고 제거할 수 있다는 특징이 있어서 많은 경우에 활용된다.

특히 괄호 쌍, DFS, Flood Fill 등에 기본적으로 사용되므로, 이러한 기본적인 자료구조를 정확히 이해하고 활용하는 것이 중요할 것 같다.