선형 자료구조 : 스택(Stack)과 큐(Queue)에 대해 파악하기

스택(Stack)과 큐(Queue)는 프로그래밍에서 자주 사용되는 선형 자료구조로,
데이터의 삽입과 삭제 순서가 서로 다릅니다.

1. 스택(Stack)
스택은 후입선출(LIFO, Last In First Out) 원칙을 따르는 선형 자료구조로,
데이터의 삽입(push)과 삭제(pop)가 한쪽 끝(top)에서만 이루어집니다.
이는 책을 쌓아 놓고 가장 위에 있는 책을 먼저 꺼내는 것과 같이 마지막에 추가된 요소가 가장 먼저 제거됩니다.

1) 주요연산

• 'push' : 스택의 최상단(top)에 요소 추가
• 'pop' : 최상단 요소 제거 및 반환
• 'peek' /  'top' : 최상단 요소 확인 (제거하지 않음)
• 'isEmpty' : 스택이 비었는지 확인

# 배열기반 : 고정된 크기로 구현이 간단하지만, 동적 크기 조절이 어려움
stack = []
stack.append(1) # push
stack.pop()     # pop

# 연결 리스트 기반 : 동적 메모리 관리가 가능하지만 구현 복잡도가 높음
class Node:
	def __init__(self, data):
    	self.data = data
        self.next = None

2) 구현 : 배열이나 연결 리스트로 구현 가능하며, 'top' 포인터로 최상단 위치를 추적
→ 스택은 상대적으로 구현이 간단함
→ 단순한 구조로 인해 메모리 사용이 효율적

3) 사용예시

• 브라우저 뒤로 가기 기능
• 함수 호출 스택(재귀 함수 실행)
• 실행 취소(Undo)기능

 

2. 큐(Queue)
큐는 선입선출(FIFO, First In First Out) 원칙을 따르는 자료구조이며,
데이터가 들어오는 쪽을 rear(뒤), 나가는 쪽을(front)라고 합니다.
새로운 요소는 큐의 뒤쪽(rear)에 추가되고, 요소를 제거할 때는 앞쪽(front)에서 이루어지기에
가장 먼저 추가된 요소가 가장 먼저 제거됩니다.

1) 주요연산

• 'enqueue' : 큐의 후단(rear)에 요소 추가
• 'dequeue' : 전단(front) 요소 제거 및 반환 
• 'peek' / 'front' : 전단(front) 요소를 확인(제거하지 않음)
• isEmpty : 큐가 비었는지 확인
• isFull : 큐가 가득 찼는지 확인

2) 구현 : 배열 또는 연결 리스트로 구현되며, 'front'와 'rear' 두 개의 포인터를 사용
→ 큐는 두 개의 포인터를 관리해야 하므로 구현이 더 복잡함
→ front와 rear 포인터 관리로 인해 메모리 사용이 덜 효율적일 수 있다

3) 사용예시

• 프린터 작업 대기열
• CPU 작업 스케줄링
• 은행 번호표 시스템

스택 VS 큐 차이점

구분	스택(Stack)	큐(Queue)
작동원리	LIFO(Last In First Out)	FIFO(First In First Out)
삽입/삭제	한 끝(top)에서만 발생	삽입은 rear, 삭제는 front에서 발생
포인터	'top'	'front'
연산 이름	Push, Pop	Enqueue, Dequeue
사용 사례	실행 취소, 함수 호출관리	작업 대기열, 데이터 버퍼링

요약정리
1. 스택은 마지막에 추가된 데이터를 우선 처리할 때 유용합니다.(예 : 최근 작업 취소)
2. 큐는 순서대로 처리해야 하는 작업에 적합합니다.(예 : 주문 처리 시스템)
3. 두 구조 모두 데이터의 순차적 접근을 관리하지만, 삽입/삭제 지점과 처리 순서에서 근본적인 차이가 있습니다.