🦠Cell Algorithm : 스택과 큐

스택과 큐는 리스트에서 조금 더 발전한 형태의 자료구조이다. 스택과 큐의 구조는 비슷하지만 처리 방식은 다르다.

---

• 스택
  1. 후입선출(LIFO)
     
     • 가장 마지막에 사입된 데이터가 가장 먼저 나오는 구조
     • 스택의 위치는 top이라는 개념이 있다.
     • 재귀 함수 알고리즘 원리와 일맥상통하다.
  2. 스택에 사용되는 코드
     
     • 위치
       • top : 스택에서 가장 위에 있는 데이터를 가리는 영역이다.
     • s.append(data) : top의 새로운 데이터를 삽입
     • s.pop() : top위치에 현재 데이터를 삭제하고 확인하는 연산
     • s[-1] : top위치에 현재 있는 데이터를 단순 확인하는 연산
  3. 스택을 이용한 알고리즘
     • 우선 탐색
     • 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아두어야 한다.
  4. 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아두어야 한다.

---

• 큐
  1. 선입후출(FIFO)
     
     • 먼저 들어가는 데이터가 먼저 나오는 구조
     • 큐의 위치는 top이라는 개념은 따로 없다. rear와 front라는 개념이 존재
     • 파이썬에선 덱(deque)을 이용해서 큐를 사용한다. 리스트를 이용해서 구현이 가능하다만 덱을 이용해야 빠르다.
     • 덱에 관한 영상을 참고하길 바란다.
  2. 큐에 사용되는 코드
     
     • 위치
       • rear : 큐에서 가장 끝 데이터를 가리키는 영역이다.
       • front : 큐에서 가장 앞의 데이터를 가리키는 영역이다.
     • s.append(data) : rear 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
     • s.popleft() : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
     • s[0] : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.
  3. 큐를 이용한 알고리즘
     • 너비 우선 탐색(BFS)
     • 우선 순위 큐 : 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터를 먼저 나오는 자료구조(6장에서 설명)
       • 힙을 이용해서 우선 순위 큐를 구현 : 힙은 트리 종류 중 하나이다.

---