리스트, 스택, 큐

대표적인 선형 자료구조인 리스트, 스택, 큐를 간단하게 구분해 본다.
각 자료구조는 나중에 자세한 글로 정리해보겠다.

리스트

• 데이터를 순차적으로 저장하는 선형 자료구조
• 배열과 연결 리스트로 나눌 수 있음

배열

• 크기가 고정된 연속된 메모리 블록에 데이터를 저장
• 인덱스를 통해 O(1) 시간에 데이터 접근 가능
• 중간에 데이터 변경이 있는 경우, 데이터 이동이 필요해 평균 O(n)의 시간이 소요됨

예시: [10, 20, 30, 40, 50]

연결 리스트

• 각 노드가 데이터와 다음 노드를 가리키는 포인터를 갖고 있음
• 한 방향으로만 연결된 단일 연결 리스트
• 양 방향으로 연결된 이중 연결 리스트
• 마지막 노드가 첫 노드를 가리키는 환형 연결 리스트
• 삽입과 삭제는 O(1) 시간에 가능, 하지만 특정 위치의 데이터에 접근하려면 O(n)의 시간 소요

예시: 10 -> 20 -> 30 -> 40 -> NULL

스택

• LIFO(Last In First Out) 구조를 따르는 선형 자료구조
• 마지막에 들어온 데이터가 먼저 나가는 후입선출 구조
• Push: 스택의 맨 위에 데이터를 추가
• Pop: 맨 위에 있는 데이터를 제거 후 반환
• Peek(Top): 맨 위에 있는 데이터를 반환

예시: 괄호 검사, 되돌리기

큐

• FIFO(First In First Out) 구조를 따르는 선형 자료구조
• 먼저 들어온 데이터가 먼저 나가는 선입선출 구조
• 일반 큐: 기본적인 FIFO 구조의 큐
• 순환 큐: 큐의 양 끝이 연결되어 있어 효율적인 공간 활용
• 우선순위 큐: 각 요소의 우선순위 부여, 높은 순서대로 처리
• 덱: 양쪽 끝에서 삽입/삭제가 가능한 큐
• 두 개의 포인터(Front, Rear)를 사용해 삽입과 삭제 관리

예시: 프린터 대기열, 네트워크 패킷 처리, 프로세스 스케줄링