[알고리즘][코딩 인터뷰 완전 분석 정리] 03 스택과 큐

스택 구현하기

• LIFO (Last In First Out)에 따라 자료를 배열함. 접시를 쌓아두는 것과 비슷한 구조
• 스택 연산 
  • pop() : 스택에서 가장 위에 있는 항목을 제거함.
  • push(item) : item 하나를 스택의 가장 윗 부분에 추가함.
  • peek() : 스택의 가장 위에 있는 항목을 반환.
  • isEmpty() : 스택이 비어 있을때에 true를 반환.
• 배열과 달리 상수 시간에 i번째 항목에 접근할 수 없다.하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수시간에 가능함. 배열처럼 원소들을 하나씩 옆으로 밀어줄 필요가 없다. 
• 재귀알고리즘을 사용할 때 유용하게 사용가능.

 

 

큐 구현하기

• FIFO(First In First Out)에 따라 자료를 배열.
• 매표소 앞에 서 있느 사람들이 움직이는 형태. 큐에 저장되는 항목들은 큐에 추가되는 순서대로 제거.
• 큐 연산
  • add(item) : item을 리스트의 끝 부분에 추가
  • remove() : 리스트의 첫 번재 항목을 제거
  • peek() : 큐에서 가장 위에 있는 항목을 반환
  • isEmpty() : 큐가 비어 있을 때에 true를 반환.
• 큐또한 연결리스트로 구현 가능. 연결 리스트의 반대 방향에서 항목을 추가하거나 제거하도록 구현한다면 근본적으로 큐와 같다. 
• 큐는 너비우선 검색(BFS Breadth-First search)을 하거나 캐시를 구현하는 경우에 사용.
• 너비우선 탐색을 하는 경우에 처리해야 할 노드의 리스트를 저장하는 용도로 큐를 사용.