🌈 [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 문제가 어려웠다ㅠ

그래서 세문제인데도 잘 이해가 안되는 부분이 있어서 시간이 좀 걸렸다

오늘 이해를 마치고 내일 보지 않고 페어와 같이 잘 풀어봐야겠다!

 

( 본 게시물은 2022/09/22에 작성한 글을 옮긴 글입니다. 원문은 요기에 있음! )

728x90