들어가며

스택(Stack)과 큐(Queue)는 컴퓨터 과학에서 가장 기본적이면서도 중요한 자료구조 중 하나다.

이러한 자료구조는 데이터의 저장 및 처리 방법을 나타내는 데 사용되며 컴퓨터 프로그래밍과 알고리즘 개발에 핵심적이라고 볼 수 있다.

스택과 큐는 다양한 응용 프로그램에서 사용되며 데이터를 조직화하고 효율적으로 처리하는 데 도움이 되기 때문에 이렇게 글을 작성하며 공부해보려 한다.

Stack

스택은 데이터를 쌓아 올리는 형태로 관리하는 선형 데이터 구조로, 데이터를 추가하거나 제거할 때 맨 위에서만 이루어지는 "Last-In-First-Out" (LIFO) 원칙을 따른다.

즉, 스택은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 의미한다.

주요 특징

• 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고 데이터의 추가허는 연산인 push와 제거하는 연산을 pop이라 부르며 이는 탑(Top)에서만 이루어진다.
• 스택의 최상위 위치를 "탑(Top)"이라고 부르며 가장 최근에 들어온 자료를 가리키고 있다. 뒤에 추가되는 새로운 자료는 top이 가리키는 자료의 위에 쌓이게 된다.
• 함수 호출 스택, 뒤로 가기 버튼 기록 등 다양한 응용 분야에서 사용된다.
• 스택은 배열 또는 링크드리스트로 구현할 수 있다.

따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 된다.

그리고 이러한 스택의 구조를 후입선출 (Last-In-First-Out, LIFO) 구조라고 한다.

추가적으로 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며, 스택이 넘치는 경우 stack overflow라고 한다.

활용 예시

스택의 후입선출을 활용하여 여러분야에서 활용이 가능한테 아래의 예시가 대표적이다.

• 웹브라우저의 방문 기록 : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자붵 출력한다.
• 실행 취소 : 가장 나중에 실행된 것부터 실행을 취소한다.

Queue

큐는 데이터를 선입선출(First-In-First-Out, FIFO) 순서로 처리하는 자료 구조다.

주요 특징

이때 데이터를 삭제하는 연산만 이루어지는곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행된다.

큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue), 프론트에서 이루어지는 삭제 연산을 디큐(dnQueue)라고 부른다.

• 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성
• 접근 방법은 가장 첫 원소와 끝 원소로만 가능
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫번째 원소가 되는 것이며,
리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

활용 예시

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용.

• 우선순위가 같은 작업 예약
• 캐시 구현
• 콜센터 고객 대기
• 은행 업무