Home > Algorithm > 2024 > πŸ“¦[DS,Algorithm] μŠ€νƒ(Stack)

πŸ“¦[DS,Algorithm] μŠ€νƒ(Stack)
DataStructure Algorithm

1️⃣ μŠ€νƒ(Stack).

μŠ€νƒ(Stack)은 자료ꡬ쑰의 ν•œ μ’…λ₯˜λ‘œ, 데이터가 일렬둜 μŒ“μ΄λŠ” ꡬ쑰λ₯Ό 가지고 μžˆμŠ΅λ‹ˆλ‹€.

1️⃣ μŠ€νƒ(Stack)의 νŠΉμ§•.

β€œν›„μž…μ„ μΆœ(LIFO, Last In First Out)β€λ‘œ, κ°€μž₯ λ‚˜μ€‘μ— μ‚½μž…λœ 데이터가 κ°€μž₯ λ¨Όμ € κΊΌλ‚΄μ§„λ‹€λŠ” 점이 νŠΉμ§•μž…λ‹ˆλ‹€.

2️⃣ μŠ€νƒ(Stack)의 κΈ°λ³Έ μ—°μ‚°.

  1. ν‘Έμ‹œ(Push) : μŠ€νƒμ˜ 맨 μœ„μ— 데이터λ₯Ό μ‚½μž…ν•˜λŠ” μ—°μ‚°.

  2. 팝(Pop) : μŠ€νƒμ˜ 맨 μœ„μ— μžˆλŠ” 데이터λ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•˜λŠ” μ—°μ‚°.

3️⃣ μŠ€νƒ(Stack)의 뢀가적인 μ—°μ‚°.

  • 피크(peek) λ˜λŠ” 탑(top) : μŠ€νƒμ˜ 맨 μœ„μ— μžˆλŠ” 데이터λ₯Ό μ œκ±°ν•˜μ§€ μ•Šκ³  λ°˜ν™˜ν•˜λŠ” μ—°μ‚°.

  • isEmpty : μŠ€νƒμ΄ λΉ„μ–΄ μžˆλŠ”μ§€ μ—¬λΆ€λ₯Ό ν™•μΈν•˜λŠ” μ—°μ‚°.

  • size : μŠ€νƒμ— μžˆλŠ” λ°μ΄ν„°μ˜ 개수λ₯Ό λ°˜ν™˜ν•˜λŠ” μ—°μ‚°.

4️⃣ μŠ€νƒ(Stack)의 μ‹€μ œ μ‘μš© 사둀.

  • μ›Ή λΈŒλΌμš°μ €μ˜ λ°©λ¬Έ 기둝(λ’€λ‘œ κ°€κΈ° κΈ°λŠ₯)
  • ν•¨μˆ˜ ν˜ΈμΆœμ‹œμ˜ 호좜 μŠ€νƒ
  • μ—­ν΄λž€λ“œ ν‘œκΈ°λ²• 계산 λ“±

5️⃣ μŠ€νƒ(Stack)의 κ΅¬ν˜„.

μŠ€νƒμ€ λ°°μ—΄μ΄λ‚˜ μ—°κ²° 리슀트λ₯Ό μ΄μš©ν•˜μ—¬ κ΅¬ν˜„ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

배열을 μ΄μš©ν•œ μŠ€νƒ κ΅¬ν˜„μ€ κ³ μ •λœ 크기λ₯Ό 가지며, μ—°κ²° 리슀트λ₯Ό μ΄μš©ν•œ μŠ€νƒ κ΅¬ν˜„μ€ λ™μ μœΌλ‘œ 크기λ₯Ό μ‘°μ ˆν•  수 μžˆμŠ΅λ‹ˆλ‹€.

  • 배열을 μ΄μš©ν•œ μŠ€νƒ : κ³ μ •λœ 크기의 배열을 μ‚¬μš©ν•˜μ—¬ μŠ€νƒμ„ κ΅¬ν˜„ν•  수 μžˆμŠ΅λ‹ˆλ‹€. 이 경우 μŠ€νƒμ˜ 크기가 초과되면 더 큰 λ°°μ—΄λ‘œ λ³΅μ‚¬ν•˜λŠ” μΆ”κ°€ μž‘μ—…μ΄ ν•„μš”ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

  • μ—°κ²° 리슀트λ₯Ό μ΄μš©ν•œ μŠ€νƒ : λ™μ μœΌλ‘œ 크기λ₯Ό μ‘°μ ˆν•  수 μžˆλŠ” μ—°κ²° 리슀트λ₯Ό μ‚¬μš©ν•˜μ—¬ μŠ€νƒμ„ κ΅¬ν˜„ν•  수 μžˆμŠ΅λ‹ˆλ‹€. μ—°κ²° 리슀트의 λ…Έλ“œ μ‚½μž… 및 μ‚­μ œλŠ” O(1)의 μ‹œκ°„ λ³΅μž‘λ„λ₯Ό κ°€μ§€λ―€λ‘œ, μŠ€νƒ 연산을 효율적으둜 μˆ˜ν–‰ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

6️⃣ μ‹œκ°„ λ³΅μž‘λ„

μŠ€νƒμ˜ 각 연산은 일반적으둜 λ‹€μŒκ³Ό 같은 μ‹œκ°„ λ³΅μž‘λ„λ₯Ό κ°€μ§‘λ‹ˆλ‹€.

  1. Push : O(1)
    • 데이터λ₯Ό μŠ€νƒμ˜ 맨 μœ„μ— μΆ”κ°€ν•˜λŠ” 연산은 항상 μΌμ •ν•œ μ‹œκ°„ 내에 μ™„λ£Œλ©λ‹ˆλ‹€.
  2. Pop : O(1)
    • 데이터λ₯Ό μŠ€νƒμ˜ 맨 μœ„μ—μ„œ μ œκ±°ν•˜λŠ” 연산도 항상 μΌμ •ν•œ μ‹œκ°„ 내에 μ™„λ£Œλ©λ‹ˆλ‹€.
  3. Peek λ˜λŠ” Top : O(1)
    • μŠ€νƒμ˜ 맨 μœ„μ— μžˆλŠ” 데이터λ₯Ό ν™•μΈν•˜λŠ” 연산은 데이터 μ ‘κ·Όλ§Œ ν•„μš”ν•˜κΈ° λ•Œλ¬Έμ— μΌμ •ν•œ μ‹œκ°„ 내에 μ™„λ£Œλ©λ‹ˆλ‹€.
  4. isEmpty : O(1)
    • μŠ€νƒμ΄ λΉ„μ–΄ μžˆλŠ”μ§€ ν™•μΈν•˜λŠ” 연산은 μŠ€νƒμ˜ 크기만 ν™•μΈν•˜λ©΄ λ˜ν”„λ‘œ μΌμ •ν•œ μ‹œκ°„ 내에 μ™„λ£Œλ©λ‹ˆλ‹€.
  5. Size : O(1)
    • μŠ€νƒμ— μžˆλŠ” λ°μ΄ν„°μ˜ 개수λ₯Ό λ°˜ν™˜ν•˜λŠ” 연산은 μŠ€νƒμ˜ 크기 정보λ₯Ό μœ μ§€ν•˜κ³  있으면 μΌμ •ν•œ μ‹œκ°„ 내에 μ™„λ£Œλ©λ‹ˆλ‹€.

7️⃣ μŠ€νƒ κ΅¬ν˜„.

// Stack
public class Stack {
  private int maxSize; // μŠ€νƒμ˜ μ΅œλŒ€ 크기
  private int top; // μŠ€νƒμ˜ 맨 μœ„λ₯Ό κ°€λ¦¬ν‚€λŠ” 인덱슀
  private int[] stackArray; // μŠ€νƒμ„ μ €μž₯ν•  λ°°μ—΄

  // μƒμ„±μž
  public Stack(int size) {
    maxSize = size;
    stackArray = new int[maxSize];
    top = -1; // μŠ€νƒμ΄ λΉ„μ–΄μžˆμŒμ„ λ‚˜νƒ€λƒ„
  }

  // μŠ€νƒμ— 값을 ν‘Έμ‹œν•˜λŠ” λ©”μ†Œλ“œ
  public void push(int value) {
    if (isFull()) {
      System.out.println("μŠ€νƒμ΄ 가득 μ°ΌμŠ΅λ‹ˆλ‹€.");
      return;
    }
    stackArray[++top] = value;
  }

  // μŠ€νƒμ—μ„œ 값을 νŒν•˜λŠ” λ©”μ†Œλ“œ
  public int pop() {
    if (isEmpty()) {
      System.out.println("μŠ€νƒμ΄ λΉ„μ–΄μžˆμŠ΅λ‹ˆλ‹€.");
      return -1; // μ—λŸ¬λ₯Ό λ‚˜νƒ€λ‚΄κΈ° μœ„ν•΄ -1 λ°˜ν™˜
    }
    return stackArray[top--];
  }

  // μŠ€νƒμ˜ λ§₯ μœ„ 값을 λ°˜ν™˜ν•˜λŠ” λ©”μ†Œλ“œ
  public int peek() {
    if (isEmpty()) {
      System.out.println("μŠ€νƒμ΄ λΉ„μ–΄μžˆμŠ΅λ‹ˆλ‹€.");
      return -1; // μ—λŸ¬λ₯Ό λ‚˜νƒ€λ‚΄κΈ° μœ„ν•΄ -1 λ°˜ν™˜
    }
    return stackArray[top];
  }

  // μŠ€νƒμ΄ λΉ„μ–΄μžˆλŠ”μ§€ ν™•μΈν•˜λŠ” λ©”μ†Œλ“œ
  public boolean isEmpty() {
    return (top == -1);
  }

  // μŠ€νƒμ΄ 가득 μ°ΌλŠ”μ§€ ν™•μΈν•˜λŠ” λ©”μ†Œλ“œ
  public boolean isFull() {
    return (top == maxSize -1);
  }

  // μŠ€νƒμ˜ 크기λ₯Ό λ°˜ν™˜ν•˜λŠ” λ©”μ†Œλ“œ
  public int size() {
    return top + 1;
  }
}

// Main
public class Main {

  public static void main(String[] args) {
    Stack stack = new Stack(5); // 크기가 5인 μŠ€νƒ 생성

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    System.out.println("μŠ€νƒμ˜ 맨 μœ„ κ°’ : " + stack.peek());
    System.out.println("μŠ€νƒμ˜ 크기 : " + stack.size());

    while (!stack.isEmpty()) {
      System.out.println("팝 : " + stack.pop());
    }

    System.out.println("μŠ€νƒμ˜ 크기 : " + stack.size());
  }
}
/*
===좜λ ₯===
μŠ€νƒμ˜ 맨 μœ„ κ°’ : 5
μŠ€νƒμ˜ 크기 : 5
팝 : 5
팝 : 4
팝 : 3
팝 : 2
팝 : 1
μŠ€νƒμ˜ 크기 : 0
*/

μ£Όμš” λ©”μ„œλ“œ μ„€λͺ…

  • push(int value) : μŠ€νƒμ˜ 맨 μœ„μ— 값을 μΆ”κ°€ν•©λ‹ˆλ‹€. μŠ€νƒμ΄ 가득 찼을 경우, μ—λŸ¬ λ©”μ‹œμ§€λ₯Ό 좜λ ₯ν•©λ‹ˆλ‹€.
  • pop() : μŠ€νƒμ˜ 맨 μœ„ 값을 μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€. μŠ€νƒμ΄ λΉ„μ–΄ μžˆμ„ 경우, μ—λŸ¬ λ©”μ‹œμ§€λ₯Ό 좜λ ₯ν•˜κ³  -1을 λ°˜ν™˜ν•©λ‹ˆλ‹€.
  • peek() : μŠ€νƒμ˜ 맨 μœ„ 값을 λ°˜ν™˜ν•˜μ§€λ§Œ, μŠ€νƒμ—μ„œ μ œκ±°ν•˜μ§€λŠ” μ•ŠμŠ΅λ‹ˆλ‹€. μŠ€νƒμ΄ λΉ„μ–΄ μžˆμ„ 경우, μ—λŸ¬ λ©”μ‹œμ§€λ₯Ό 좜λ ₯ν•˜κ³  -1을 λ°˜ν™˜ν•©λ‹ˆλ‹€.
  • isEmpty() : μŠ€νƒμ΄ λΉ„μ–΄ μžˆλŠ”μ§€ μ—¬λΆ€λ₯Ό ν™•μΈν•©λ‹ˆλ‹€.
  • isFull() : μŠ€νƒμ΄ 가득 μ°ΌλŠ”μ§€ μ—¬λΆ€λ₯Ό ν™•μΈν•©λ‹ˆλ‹€.
  • size() : μŠ€νƒμ— ν˜„μž¬ μ €μž₯된 λ°μ΄ν„°μ˜ 개수λ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.