[TIL] 자료구조 : 스택, 큐

🙏🏻 자료구조

  - 여러 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것

  - 상황마다 데이터를 효율적으로 다룰 수 있어 특정한 상황에 놓은 문제를 해결하는데 특화

💡 데이터 ?

  - 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값

  - 데이터를 체계적으로 정리하여 저장해두는 것은 데이터 활용에 유리함

 

 

---

📍 Stack 스택

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

  - 데이터를 순서대로 쌓는 구조

  - 감자칩 통이 Stack, 감자칩은 데이터로 비유할 수 있음

  - 가장 먼저 들어간 첫 번째 감자칩은 가장 나중에 나오며, 가장 나중에 들어간 세 번째 감자칩이 가장 먼저 나옴 = LIFO

  - 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근

  - 감자칩을 넣는 것, 즉 데이터를 넣는 것을 PUSH 라고 함

  - 감자칩을 꺼내 먹는 것, 즉 데이터를 꺼내는 것을 POP 이라고 함

  

▪️ Stack의 특징

  ① LIFO ( Last In First Out )

   - 먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조

stack.push(4);
stack.push(3);
stack.push(2);
stack.push(1);

  → 데이터는 스택 안에  1️⃣

                                     2️⃣

                                     3️⃣

                                     4️⃣ 처럼 담김

stack.pop();
stack.pop();
stack.pop();
stack.pop();

  → 데이터가 나올 때는 1 부터 나오기 시작 : 1️⃣→2️⃣→3️⃣→4️⃣

  ② 데이터를 하나씩만 넣고 뺄 수 있음

  ③ 하나의 입출력 방향을 가짐

---

▪️ Stack 메서드

 ① push( )

   - 스택에 데이터 추가

 ② pop( )

   - 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터 리턴

 ③ size( )

   - 스택에 있는 데이터의 크기 리턴

 ④ peek( )

   - 가장 나중에 추가된 데이터 조회

 ⑤ show( )

   - 현재 스택에 포함되어 있는 모든 데이터를 String 타입으로 변환하여 리턴

 ⑥ clear( )

   - 현재 스택에 포함되어 있는 모든 데이터 삭제

 ⑦ empty( )

   - 스택이 비어있는지 여부를 판단할 때 사용

---

▪️ Stack 구현시 배열 / 링크드 리스트 구현

  1️⃣ 배열

   - 장점 : 구현이 쉽고 데이터 접근 속도(조회) 빠름

   - 단점 : 최대 개수를 정해야만 사용 가능

  2️⃣ 링크드 리스트

   - 장점 : 데이터의 최대 개수가 한정되지 않으며 삽입, 삭제가 용이

   - 단점 : 조회가 힘듬 (노드를 따라가며 조회히가 때문)

---

📍 Queue 큐

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

  - 선입선출의 구조를 가지는 구조

  - 빨대를 예시로 들어보면 빨대는 큐, 버블티는 데이터를 의미

  - 각 장치 사이의 속도 및 시간 차이를 극복하기 위해 임시기억 장치의 자료구조로 사용 = buffer

  - 먼저 들어온 데이터는 먼저 나가는 FIFO, LILO을 특징

  - 입력과 출력의 방향이 고정되어 있으며 두 곳을 접근 가능

   - 데이터를 넣는 것을 enqueue, 꺼내는 것은 dequeue

▪️ Queue 의 특징

  ① FIFO ( First In First Out )

   - 먼저 들어간 데이터는 제일 처음으로 나옴

queue.add(4);
queue.add(3);
queue.add(2);
queue.add(1);

  → 데이터는 큐 안에 | 1️⃣ |

                                 | 2️⃣ |

                                 | 3️⃣ |

                                 | 4️⃣ | 처럼 담김

queue.poll();
queue.poll();
queue.poll();
queue.poll();

  → 데이터가 나올 때는 먼저 들어간 4 부터 나오기 시작 : 4️⃣→3️⃣→2️⃣→1️⃣

  ② 데이터를 하나씩만 넣고 뺄 수 있음

  ③ 두 개의 입출력 방향을 가짐

---

💡 컴퓨터와 프린터 사이의 데이터 통신

---

▪️ Queue 메서드

 ① add( )

   - 큐에 데이터 추가

 ② poll( )

   - 가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터 리턴

 ③ size( )

   - 큐에 있는 데이터의 크기 리턴

 ④ peek( )

   - 가장 먼저 추가된 데이터 조회

 ⑤ show( )

   - 현재 큐에 포함되어 있는 모든 데이터를 String 타입으로 변환하여 리턴

 ⑥ clear( )

   - 큐에 포함되어 있는 모든 데이터 삭제

---

▪️ Queue 구현

  ①  순차 큐

   - 배열로 큐를 구현한 것

   - 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 함 

  ②  원형 큐

   - 첫번째 요소가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결

   - 메모리 공간을 잘 활용하지만 배열로 구현되어 있기 때문에 큐 크기 제약

  ③  링크드 리스트 큐

    - 큐의 단점을 극복하기 위해 가장 많이 사용하는 방식

    - 크기 제한이 없고 미리 정하지 않아도 되어 삽입 삭제가 편리함

    - 큐의 길이를 늘릴 수 있어 오버 플로우가 발생하지 않음