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() : 스택에 현재 저장된 데이터의 개수를 반환합니다.