스택과 큐

핵심 정리

스택과 큐는 자료를 한 줄로 쌓아 두고 꺼내는 선형 구조이다. 두 자료구조는 삽입과 삭제가 어느 쪽 끝에서 어떤 순서로 일어나는지에 따라 구분된다. 큐는 먼저 삽입된 데이터가 먼저 삭제되는 FIFO 구조이다. 이는 줄을 선 사람을 앞에서부터 처리하는 방식과 같으므로 선입선출이라고도 한다. 스택은 한쪽 끝에서만 자료를 삽입하고 삭제하는 선형 자료구조이다. 스택은 나중에 삽입된 데이터가 먼저 삭제되는 LIFO 구조이다. 이를 후입선출이라고 한다.

스택은 함수 호출과도 깊이 연결된다. 시스템 스택은 함수의 호출과 복귀에 따른 실행 순서를 관리한다. 함수의 반환 주소와 매개변수 등은 스택에 저장된다. 호출과 복귀 순서를 관리

큐는 먼저 도착한 순서대로 처리해야 하는 대기 상황에 적합하다. 은행 대기열은 선입선출 구조이므로 스택이 아니라 큐로 구현한다. 큐는 뒤에서 삽입하고 앞에서 삭제한다는 점에서 스택과 구별된다. 자료구조를 선택할 때는 먼저 들어온 데이터와 가장 최근에 들어온 데이터 중 어느 쪽을 먼저 처리해야 하는지 살펴본다.

자세히

스택의 push와 pop

스택의 기본 연산은 push와 pop이며, 두 연산 모두 top을 기준으로 동작한다. push는 top을 1 증가시킨 뒤 데이터를 저장하고, pop은 top을 1 감소시키는 방식으로 이해할 수 있다. 배열로 구현한 스택도 같은 기준을 따르므로 값을 꺼내는 시점과 top을 옮기는 시점의 순서를 정확히 구분해야 한다. 배열로 구현한 스택에서 push는 top을 증가시킨 뒤 값을 저장하고, pop은 값을 꺼낸 뒤 top을 감소시킨다. pop은 꺼낸 뒤 top 감소

입력 순서와 출력 순서의 관계는 스택의 구조에서 결정된다. D, C, B, A 순서로 스택에 입력한 자료는 BDCA 순서로 출력할 수 없다. C가 D보다 나중에 들어가 D 위에 쌓이므로, D를 꺼내려면 먼저 C를 꺼내야 하기 때문이다.

괄호 매칭과 진법 변환

괄호 매칭은 스택을 이용하는 대표적인 응용이다. 여는 괄호를 스택에 쌓아 두고 닫는 괄호를 만나면 가장 최근에 들어온 여는 괄호와 짝을 맞추므로, LIFO 성질을 이용한다.