스택

스택

@24.03.21

스택(Last In, First Out → FIFO)

💡

기본적인 데이터 구조 중 하나로, 마지막에 추가된 요소가 가장 먼저 제거된다. → 후입선출

• 가장 위에 있는 요소만 접근 가능하며, 그 요소를 제거하면 그 아래에 있던 요소가 다음으로 제거될 요소가 된다.

• 예시
  • 웹 브라우저의 뒤로가기 기능
  • 함수 호출시의 반환 주소 저장
  • 괄호의 짝 맞춤 검사
  • 접시 쌓기

• 스택의 주요 연산
  • push : 스택의 가장 위에 새로운 요소 추가
  • pop : 스택의 가장 위 엤는 요소 제거 후 그 값 반환
  • peek/top : 스택의 가장 위에 있는 요소를 반환(제거는 않는다.)
  • isEmpty : 스택이 비어있는지 확인

• 기본적인 기능을 가진 스택 구현

  class Stack {
      private int maxSize; // 스택의 최대 크기
      private int top; // 현재 스택의 맨 위를 가리키는 인덱스
      private int[] stackArray; // 스택 요소를 저장할 배열
  
      // 스택 생성자
      public Stack(int maxSize) {
          this.maxSize = maxSize;
          stackArray = new int[maxSize];
          top = -1; // 스택이 비어있음을 나타내는 값
      }
  
      // 스택에 요소 추가
      public void push(int x) {
          if (isFull()) {
              System.out.println("스택이 가득 찼습니다.");
              return;
          }
          stackArray[++top] = x;
      }
  
      // 스택에서 요소 제거 후 반환
      public int pop() {
          if (isEmpty()) {
              System.out.println("스택이 비어있습니다.");
              return -1;
          }
          int poppedElement = stackArray[top];
          stackArray[top--] = 0;
          return poppedElement;
      }
  
      // 스택의 맨 위 요소 반환
      public int top() {
          if (isEmpty()) {
              System.out.println("스택이 비어있습니다.");
              return -1;
          }
          return stackArray[top];
      }
  
      // 스택이 비어있는지 확인
      public boolean isEmpty() {
          return (top == -1);
      }
  
      // 스택이 가득 찼는지 확인
      public boolean isFull() {
          return (top == maxSize - 1);
      }
  }