[자료구조] 스택과 큐

[자료구조] 스택과 큐

 

1. 정의

1. 스택

• Stack : 쌓는다는 의미 → 차곡차곡 쌓는 자료구조
• LIFO : Last In First Out 구조

• 

• top에 있는 자료가 가장 최신의 자료
• 한쪽에서 자료의 삽입과 삭제가 반복 됨

 

1.2 큐

• Queue : 줄서서 기다린다는 의미 → 먼저 들어오는게 먼저 나가는 자료 구조
• FIFO : First In First Out 구조

• 

• 큐의 양끝에서 자료 추가와 삭제가 이루어짐

2. 구현

2.1 스택

• class Stack<T> {
  
    static class Node<T> {
      private T data;
      private Node<T> next;
  
      public Node(T data) {
        this.data = data;
      }
    }
  
    private Node<T> top;
  
    //데이터 제거
    public T pop() {
      if (top == null) {
        throw new EmptyStackException();
      }
      T item = top.data;
      top = top.next;
      return item;
    }
  
    //데이터 입력
    public void push(T item) {
      Node<T> newNode = new Node<>(item);
      newNode.next = top;
      top = newNode;
    } 
  
    //맨 위의 데이터를 반환
    public T peek() {
      if (top == null) {
        throw new EmptyStackException();
      }
          return top;
    }
  
    //스택이 비었는지 확인
    public boolean isEmpty() {
      return top == null; 
    }
  }

 

2.2 큐

•     class Queue<T> {
  
      class Node<T> {
        private T data;
        private Node<T> next;
  
        public Node(T data) {
          this.data = data;
        }
      }
  
      private Node<T> first;
      private Node<T> last;
  
      //데이터 추가
      public void add(T item) {
        Node<T> newNode = new Node<>(item);
  
        //마지막이 존재 == 저장된 데이터가 있음
        if (last != null) {
          last.next = newNode;
        }
  
        last = newNode;
  
        //첫번째가 없음 == 저장된 데이터가 없음
        if (first == null) {
          first == last;
        }
      }
  
      //데이터 제거
      public T remove() {
  
        //데이터가 없으면
        if (first == null) {
          throw new NoSuchElementException();
        }
  
        T data = first.data;
        first = first.next;
  
        if (first == null) {
          last = null;  //변경한 first가 null이면 데이터가 비어있으므로 
        }
  
        return data;
      }
  
      public T peek() {
  
        //큐가 비어있으면
        if (first == null) {
          throw new NoSuchElementException();
        }
  
        return first.data;
      }
  
      public boolean isEmpty() {
        return first == null;
      }
    }

---

※ 참조

• 자바로 구현하고 배우는 자료구조 - 네이버 부스트 코스
• Stack & Queue - 엔지니어대한민국