코딩 알고리즘 스택 큐 개념 이해

스택과 큐: 자료구조의 기초

프로그래밍에서 효율적인 데이터 관리와 처리를 위해서는 다양한 자료구조를 이해하는 것이 필수적입니다. 그 중에서도 스택(Stack)과 큐(Queue)는 가장 기본적이고 널리 사용되는 자료구조입니다. 이번 글에서는 이 두 가지 구조가 무엇인지, 어떻게 작동하는지, 그리고 어떤 상황에서 활용되는지를 살펴보겠습니다.

스택(Stack)

스택은 데이터를 쌓아 올리는 구조로, 물건을 쌓듯이 마지막에 들어온 것이 가장 먼저 나가는 특성을 지니고 있습니다. 이를 전문 용어로 LIFO(Last In, First Out)라고 부르며, 마지막에 쌓인 데이터가 가장 먼저 삭제된다는 의미입니다.

스택의 작동 원리

• Push: 데이터를 스택에 쌓는 작업입니다.
• Pop: 스택에서 데이터를 꺼내는 작업입니다.
• Top/Peek: 스택의 최상단 데이터 값을 조회하는 작업입니다.

스택의 활용 예시로는 웹 브라우저의 뒤로 가기 버튼, 코드 실행 취소(Undo), 괄호 유효성 검사 등이 있습니다. 예를 들어, 문자열을 역순으로 변환할 때 스택을 사용하면 간단히 해결할 수 있습니다. 문자열의 각 문자를 순차적으로 스택에 넣고 그 후 스택에서 모두 꺼내게 되면 원래 문자열의 역순이 생성됩니다.

스택의 한계

스택은 정해진 크기 이상으로 요소를 추가하려고 할 때 스택 오버플로우(Stack Overflow)가 발생하고, 비어 있는 상태에서 요소를 꺼내려 할 경우 스택 언더플로우(Stack Underflow)가 발생할 수 있습니다. 이러한 상황을 방지하기 위해서는 스택의 크기를 미리 정해 두고 관리해야 합니다.

큐(Queue)

큐는 선입선출(FIFO, First In, First Out) 구조를 지니고 있으며, 먼저 들어온 데이터가 먼저 나가는 방식입니다. 이를 이해하기 쉽게 설명하면, 놀이공원에서 줄 서 있는 상황과 유사합니다. 가장 먼저 들어간 사람이 가장 먼저 놀이기구를 이용할 수 있습니다.

큐의 작동 원리

• Enqueue: 데이터를 큐에 추가하는 작업입니다.
• Dequeue: 큐에서 데이터를 제거하는 작업입니다.

큐의 대표적인 예로는 프로세스 스케줄링, 프린터 작업 대기, 고객 서비스 대기열 등을 들 수 있습니다. 큐는 주로 소비자-생산자 문제처럼 데이터 흐름이 일정한 경우에 적합합니다. 예를 들어, 프린터에서 인쇄 요청을 처리할 때, 먼저 요청된 문서부터 처리하는 큐의 구조가 유용하게 사용됩니다.

원형 큐(Circular Queue)

큐의 연장선으로 원형 큐가 있습니다. 이 구조는 큐의 끝이 처음으로 돌아가는 형태입니다. 원형 큐는 메모리의 공간을 효율적으로 활용할 수 있으며, 큐가 가득 차도 데이터 삽입이 원활하게 이루어질 수 있도록 돕습니다.

스택과 큐의 차이점

스택과 큐는 모두 데이터를 저장하는 구조이지만, 그 운영 방식에서 큰 차이를 보입니다. 스택은 한쪽 끝에서만 삽입과 삭제가 이루어지며, 큐는 양쪽 끝에서 각각 삽입과 삭제가 이루어집니다. 이러한 차이는 서로 다른 종류의 문제를 해결하는 데에 특화되어 있습니다.

코딩 테스트에서의 활용

스택과 큐는 코딩 테스트에서도 자주 등장하는 주제입니다. 예를 들어, 프로그래머스의 코딩 테스트에서는 이 두 자료구조를 활용한 문제들이 많습니다. 기능 개발 문제, 괄호 검사 문제 등 다양한 상황에서 스택과 큐를 효과적으로 사용할 수 있습니다.

• 기능 개발: 각 기능의 진도가 100%인 경우 배포하는 문제.
• 괄호 검사: 주어진 문자열에서 괄호의 짝이 맞는지 확인하는 문제.

이와 같은 문제를 해결하기 위해서는 스택의 LIFO 특성을 활용하거나, 큐의 FIFO 특성을 적절히 활용하는 것이 좋습니다. 이를 통해 각 문제를 보다 효율적으로 풀 수 있습니다.

결론

스택과 큐는 컴퓨터 과학의 기초를 이루는 중요한 자료구조입니다. 이들을 이해하고 활용함으로써 알고리즘 문제를 보다 효과적으로 해결할 수 있습니다. 두 자료구조의 특성을 잘 파악하고 활용한다면 코딩 테스트뿐만 아니라 실무에서도 큰 도움이 될 것입니다. 앞으로 코딩을 하면서 스택과 큐를 적극적으로 활용해보시길 바랍니다!

자주 물으시는 질문