큐, 리스트

스택의 활용

• 중위 표기법을 후위 표기법으로
• 후위 표기법의 수식을 계산

큐

• 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
• 뒤에서 삽입, 앞에서 삭제
• FIFO

리스트

• 순서를 가진 데이터의 집합을 가리키는 추상 자료형
• 중복 허용
• 순차 리스트: 배열 기반
• 연결 리스트: 메모리 동적 할당 기반
• 단순 배열을 이용한 순차 리스트
  • 자료의 삽입·삭제 연산 과정에서 연속적인 메모리 배열을 위해 원소 이동 작업 필요
  • 원소의 개수가 많고 연산이 빈번하게 일어날수록 작업에 소요되는 시간 크게 증가
  • 배열 크기가 정적인 경우, 실제로 사용될 메모리보다 크게 할당하여 메모리 낭비 초래
  • 메모리보다 많은 자료를 사용하여 새롭게 배열을 만들어 작업해야 하는 경우도 발생 가능
• 연결 리스트
  • 자료의 논리적인 순서와 메모리 상의 물리적 순서가 일치하지 않음
  • 개별적으로 위치하고 있는 각 원소를 연결하여 하나의 전체적 자료구조를 이룸
  • 순서를 맞추기 위한 작업이 필요치 않음
  • 크기가 동적 👉 효율적 사용 가능
  • 노드: 연결 리스트에서 사용하는 하나의 원소, 데이터와 링크로 구성
    • 헤드: 연결 리스트의 첫 노드 참조
  • 단순 연결 리스트: 노드가 하나의 링크 필드를 가지고 다음 노드와 연결되는 구조
  • 이중 연결 리스트: 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트로, 두 개의 링크 필드와 하나의 데이터 필드로 구성