🌈 [Section2] 3. 자료구조1

📕 오늘 배운 내용!

• 스택 (Stack)
• 큐 (Queue)

---

✏️ 자료구조

• 자료(데이터)를 체계적으로 정리하여 저장하고 활용하는 구조 그 자체

• 구현 방식에는 제한 X

• Stack, Queue, Tree, Graph 의 네가지 구조

Java에서는 Stack을 Stack 클래스로 구현하여 제공
But, Queue는 Queue 인터페이스만 있고 별도의 클래스가 없음 ➜ Queue 인터페이스를 구현한 클래스 사용

---

✏️ 스택 (Stack)

• 데이터(data)를 순서대로 쌓는 자료구조 Ex.프링글스

• Stack에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'

  Ex. 대표적으로 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 사용됨

  1. 새로운 페이지로 접속하면 ➜ 현재 페이지 Prev Stack에 보관
  2. 이전 페이지로 돌아갈 때 ➜ 현재 페이지를 Next Stack에 보관 / Prev Stack에 가장 나중에 보관된 페이지(현재 페이지의 전에 쌓인 페이지)를 현재 페이지로 가져옴
  3. 다시 앞서 방문한 페이지로 이동할 때 ➜ Next Stack의 가장 마지막으로 보관된 페이지를 가져옴
  4. 마지막으로 현재 페이지를 Prev Stack에 보관

✔ Stack의 특징

1. LIFO (Last In First Out)

2. 데이터는 하나씩만 넣고 뺄 수 있음

3. 하나의 입출력 방향 (제한적 접근)

✔ Stack 메서드

( 먼저 클래스에 메서드 만들고 메인에서 사용해야함 )

• push() - 스택에 데이터를 추가

• pop() - 마지막으로 저장된 데이터를 스택에서 꺼냄(삭제)
  (비어있으면 EmptyStackException 발생)

• peek() - 스택에 가장 나중에 추가된 데이터 반환

• size() - 스택의 크기 반환

• show() - 현재 스택에 포함되어 있는 모든 데이터 반환(그냥 읽어옴)

• clear() - 스택의 모든 데이터 삭제

• empty() - 스택이 비어있는지 boolean 타입으로 반환

• search(data) - 스택에서 data를 찾아 그 위치를 int 타입으로 반환
  (못찾으면 -1 반환)
  (배열과 달리 위치(인덱스)가 1부터 시작)

  💡 push() 와 add() 차이

  • push()
    • stack에서 제공
    • 리턴값이 < E >
      ⠀
  • add()
    • List에서 제공
    • 리턴값이 boolean

✔ Stack 클래스의 단점

• synchronized 키워드가 붙어있기 때문에 Thread-safe 하다
• 초기 용량을 설정할 수 있는 생성자가 없다 보니 데이터의 삽입을 많이 하게 되면 배열을 복사해야 하는 일이 빈번하게 발생 가능

---

✏️ 큐 (Queue)

• Stack과 반대되는 개념

• 들어간 순으로 차례로 나옴 Ex.톨게이트

• Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'

  Ex. 대표적으로 프린터로 문서를 순서대로 인쇄할 때 사용됨

  1. 문서 작성 후 출력버튼 누르면 ➜ 해당 문서가 인쇄 작업(임시기억장치의) Queue에 들어감
  2. 프린터가 인쇄 작업 Queue에 들어온 문서를 들어온 순서대로 인쇄

• 컴퓨터 장치들 사이에서 데이터 주고받을 때, 각 장치 사이의 속도 차이, 시간 차이 극복을 위해 임시 기억 장치의 자료구조로 Queue 사용 ➜ 버퍼(buffer)

  💡 버퍼링(buffering)
  컴퓨터의 CPU에서는 이벤트를 규칙적으로 처리하는데 대부분의 컴퓨터 장치에서는 이벤트가 불규칙하게 발생하기 때문에 그 불규칙적인 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용하는 것
  ⠀
  Ex. 컴퓨터 / 프린터 사이의 데이터(data) 통신
  ( 프린터는 속도가 느리고 컴퓨터의 CPU는 데이처 처리 속도가 그에 비해 빠름 )

  1. CPU가 빠르게 인쇄에 필요한 데이터(data) 만들고, 인쇄 작업 Queue에 저장 후 다른 작업 함
  2. 프린터는 인쇄 작업 Queue에서 데이터(data) 받아서 일정한 속도로 인쇄

✔ Queue의 특징

1. FIFO(First In First Out)

2. 데이터는 하나씩만 넣고 뺄 수 있음

3. 두개의 입출력 방향

✔ Queue 메서드

( 먼저 클래스에 메서드 만들고 메인에서 사용해야함 )

• add(data) - 큐에 데이터 추가
  (성공하면 true를 반환, 저장공간이 부족하면  IllegalStateException 발생)

• poll() - 가장 먼저 추가된 데이터를 큐에서 꺼냄(삭제)
  (비어있으면 null을 반환)

• size() - 큐의 크기 반환

• peek() - 큐의 데이터를 삭제 없이 반환(그냥 읽어옴)
  (비어있으면 null을 반환)

• element() - 큐의 데이터를 삭제 없이 반환(그냥 읽어옴)
  ( peek 와 달리 비어있으면  NoSuchElementException 발생)

• show() - 큐에 들어있는 모든 데이터 반환(그냥 읽어옴)

• clear() - 큐에 들어있는 모든 데이터를 삭제

---

🌈 느낀점

오늘을 개념이 생각보다 괜찮길래 뭐지?? 했는데 coplit 문제가 어려웠다ㅠ 그래서 세문제인데도 잘 이해가 안되는 부분이 있어서 시간이 좀 걸렸다 오늘 이해를 마치고 내일 보지 않고 페어와 같이 잘 풀어봐야겠다!