1 분 소요

스택Stack

  • 데이터를 일시적으로 보관하는 자료구조
  • 물건을 쌓아 올리듯 잘를 쌓아 올린 형태의 자료구조
  • 스택에 저장된 자료는 선형구조를 갖는다.
    • 자료 간의 관계가 1대 1의 관계를 가짐
  • 후입선출 구조(LIFO,Last-In-First-Out)
  • 마지막에 삽입한 자료를 가장 먼저 꺼낸다.

스택 후입 선출 구조

  • 스택 주요 연산
    • push
      • 스택에 요소를 저장한다. ➡ 삽입
    • pop
      • 스택에서 요소를 꺼낸다. ➡ 삭제
    • peek
      • 스택 top에 있는 요소를 반환
  • java.util.Stack 주요 메서드
    • push()
      • 스택에 요소를 저장한다. ➡ 저장
    • pop()
      • 스택에서 요소를 꺼낸다 😊➡ 삭제
    • isEmpty()
      • 스택의 빈 상태 체크
    • size()
      • 스택에 저장된 요소 개수를 반환

Queue

BFS

  • 데이터를 일시적으로 보솬하는 자료구조
  • 선입 선출 구조(FIFO, First-In-First-Out)
  • 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 자료구조
  • 큐에 데이터를 넣는 작업인큐라고 하고 데이터를 꺼내는 작업디큐라고 한다.

큐 선입 선출 구조

  • 큐 주요연산
    • enQueue
      • 큐에 요소를 삽입
    • deQueue
      • 큐의 요소를 삭제
  • java.util.Queue 주요 메서드
    • offer()
      • 큐에 요소를 저장한다. ➡ 삽입
    • poll()
      • 큐에서 요소를 꺼낸다 ➡ 삭제
    • isEmpty()
      • 큐 빈 상태 체크
    • size()
      • 큐에 저장된 요소개수를 반환 구현은 LinkedList 또는 ArrayDeque

Queue 를 이용한 다시줘 캔디~♬ 시뮬레이션을 해 보자

1번이 줄을 선다.

1번이 한 개의 캔디를받는다.

1번이 다시 줄을선다.

새로 2번이 들어와 줄을선다.

1번이 두 개의 캔디를 받는다. 1번 다시 줄을 선다.

새로 3번이 들어와 줄을 선다.

2번이 한 개의 캔디를 받는다. 2번이 다시 줄을선다.

새로 4번이 들어와줄을선다.

1번이 세 개의 캔디를받는다. 1번이 다시 줄을 선다

새로 5번이 들어와 줄을선다.

3번이 한 개의 캔디를 받는다.

…..

20개의 캔디가 있을때 마지막 것을누가 가져갈까?

업데이트:

댓글남기기