스택과 큐

• 자료구조의 예시
• 
• 
• 
• 큐는 head 이상 rear 미만의 index data를 갖고있고 선입선출의 자료구조를 갖고있다.
• 
• 큐에서 push는 rear 위치에 자료를 추가하고 rear를 1증가
  pop은 head에서 자료를 제거하고 head를 1 증가시킴
  하지만 rear가 리스트의 한계를 벗어나면 더이상 data추가가 안 됨. 이를 방지하고자 나타난 것이 원형 큐
• 링크드 큐 : 연결리스트로 구형한 큐를 링크트 큐라고 하며 삽입과 삭제가 제한되지 않는 점과, 크기의 제한이 존재하지 않는 점이 편리하다.
• 스택과 큐는 선형 구조이다. 선형구조는 자료들이 선서를 가지고 연속된 자료구조이다.
• 정리
  파이썬의 배열을 사용하여 구현할 때 스택은 간편하게(append, pop) 구현이 가능하지만 큐의 경우는 여러 문제점이 발생한다. 즉, 스택은 파이썬의 리스트를 큐는 queue의 모듈의 Queue 클래스를 사용하면 된다.

문제풀 때 주의사항

• 이는 선입 선출의 개념으로 Stack의 개념과 비슷하다! 따라서 stack의 기술로 이 문제를 해결하면 된다.

  이처럼 어떤 문제를 풀어야 하나에 따라 필요한 자료구조를 적용하여 풀어야 한다.

요세푸스 순열

• n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.
• 이는 자료구조 중 Queue를 이용하여 푸는 것이 좋다. 그냥 배열을 사용할 수 있지만 시간상 불리함이 있다. 삽입과 삭제가 많은 작업이기 때문이다.