스택

예상 질문

자료 저장 형태 중 스택(Stack)과 큐(Queue)에 대해서 설명하시오. 스택과 큐는 어떤 차이가 있는지 설명하시오. 스택과 큐를 적용할만한 예를 들어 설명하시오.

이 질문을 하는 이유

스택과 큐는 자료 구조의 기본적인 개념이다. 각각 적합한 활용처가 있으며, 그 활용처가 무엇인지 숙지해야 한다. 또한 코딩의 기본이 되는 요소이기도 하므로, 코드 레벨로 구현할 수 있어야 한다. 기본 중의 기본이므로 반드시 숙달해야 할 영역이다.

CS 지식

스택(Stack)

책이 책상 위에 쌓여 있다고 가정하자. 제일 아래에 있는 책을 꺼내는 것보다는 제일 위에 있는 책을 꺼내는 것이 더 쉽다. 이런 방식으로 자료를 저장하고 사용하는 형태의 자료구조를 스택(Stack)이라고 한다. '쌓여 있다'는 의미 그대로, 후입선출(FILO: First In, Last Out) 방식으로 동작한다.

즉, 데이터를 스택에 입력한 뒤 가져오게 되면, 가장 마지막에 입력한 데이터가 가장 먼저 나온다.

큐(Queue)

큐는 줄을 서는 개념이다. 먼저 줄을 서 있는 사람이 먼저 기회를 얻는다. 즉, 선입선출(FIFO: First In, First Out) 구조이다.

데이터가 큐에 입력되면, 먼저 들어간 데이터가 먼저 꺼내져서 사용된다.

구현 관점

개념을 이해했다면 이제 어떻게 구현할 수 있을까?

사실 스택이나 큐는 많은 프로그래밍 언어에서 이미 라이브러리나 기본 클래스로 구현되어 있다. 예를 들어 Java의 경우 Stack, Queue 클래스를 직접 사용할 수 있다.

하지만, 스택이나 큐가 어떻게 동작하는지를 구현할 수 있어야 진정으로 이해한 것이다.

배열 기반 구현

• 스택과 큐는 모두 배열(Array)을 이용해서 구현할 수 있다.
• 배열의 현재 위치를 가리키는 인덱스 변수를 두고, 현재 위치를 변경하면서 값을 입력하거나 반환한다.

예를 들어, 숫자를 입력받는 스택이라면:

• push() 함수: 값을 저장하고 인덱스를 증가시킨다.
• pop() 함수: 현재 인덱스에서 값을 꺼내고 인덱스를 감소시킨다.

큐는 다음과 같이 구성할 수 있다:

• enqueue() 함수: 배열의 뒤쪽에 값을 넣고 rear 인덱스를 증가시킨다.
• dequeue() 함수: 앞쪽에서 값을 꺼내고 front 인덱스를 증가시킨다.

결론

• 스택은 후입선출(FILO), 큐는 선입선출(FIFO)
• 실제 프로젝트에서는 라이브러리를 활용하되, 내부 동작 방식은 반드시 숙지할 것
• 직접 구현해보는 과정을 통해 자료구조에 대한 이해도를 높일 수 있음