2022.08.22 목 - Stack & Queue

📄 학습내용

자료구조

• 자료구조 : 여러 데이터를 저장하고 다루는 방법
• 데이터(data) : 모든 자료의 값들
  
  • 이러한 데이터를 가공해야 가치가 있음
• 상황에 필요한 자료구조를 사용해서 문제 해결 가능

 

Stack

• 스택(Stack) : 데이터를 순서대로 쌓아서 역순으로 사용하는 구조
• 특징
  1. LIFO(Last In First Out) 또는 FILO(First In Last Out)
  2. 하나의 입출력 방향(제한적 접근)
  3. 하나의 데이터만을 입출력 가능
• 구조
  • top : 마지막에 들어온 요소
  • push : 데이터 넣기
  • pop : 데이터 빼기
• 구현 - Stack 데이터 타입 이용

Stack<String> stack = new Stack<>();

 

Queue

• 큐(Queue) : 데이터를 순서대로 쌓아서 사용하는 구조
• 큐의 종류
  • 선형큐(Linear Queue)
  • 원형큐(Circular Queue)
  • 디큐(Dequeue)

 

• 선형큐(Linear Queue)
  • 구조가 선형인 큐
  • 특징
    1. FIFO(First In Firt Out) 또는 LILO(Last In Last Out)
    2. 입출력 방향 고정
    3. 하나의 데이터만을 입출력 가능
  • 구조
    • front : 처음 요소
    • rear : 마지막 요소
    • enqueue : 데이터 넣기
    • dequeue : 데이터 빼기
  • 장치끼리 통신을 할 때 발생하는 속도/시간 차이를 줄이기 위해서 사용(buffer)
  • 구현 - Queue 데이터 타입을 LinkedList로 구현

Queue<Integer> queue = new LinkedList<>();

 

 

• 원형큐(Circular Queue)
  • 구조가 원형인 큐
  • 배열로 구현된 선형큐에서 계속해서 데이터를 넣고 뺐을 때 발생하는 문제(배열 포화 상태)를 보안한 큐
  • 구조
    • front : 처음 요소의 앞을 가리킨
    • rear : 마지막 요소
    • 공백상태 : front == rear
    • 포화상태 : front == (rear + 1) % QUEUE_SIZE
    • 공백상태와 포화상태 구분을 위해서 공간 하나는 사용하지 않음

 

• 덱(Dequeue, Double Ended Queue)
  • 양방향에서 입출력이 가능한 큐
  • 특징
    1. stack과 queue 구현해서 사용 가능
    2. 양방향으로 데이터 추가, 삭제

 

⭐ 공부 난이도

Stack, Queue ☆☆☆☆★

 

🌕 느낀점

  오늘은 이전에 배운 지식이 있어서 큰 어려움 없이 끝낼 수 있었다. 그래서 선형큐 말고 다른 큐에 대해서 공부를 추가적으로 진행하였다. 오늘 페어프로그래밍하면서 같이 푼 문제도 그렇게 어려운 것 같지 않았는데 테스트에서 실패했다. 일정이 있어서 마무리를 못했었는데, 일정 마무리하고 코드를 조금만 손보니 쉽게 해결되었다.