스택

스택은 컴퓨터 과학에서 사용되는 추상적 자료형(Abstract Data Type, ADT) 중 하나로, 후입선출(後入先出, Last-In First-Out, LIFO)의 원칙을 따른다. 즉, 가장 마지막에 스택에 추가된 요소가 가장 먼저 제거되는 자료구조이다.

스택은 접시를 쌓아놓는 모습에 비유할 수 있다. 접시를 쌓을 때는 맨 위에 접시를 놓고, 접시를 꺼낼 때도 맨 위의 접시를 꺼내듯이, 스택은 가장 최근에 입력된 데이터를 가장 먼저 꺼내는 방식으로 동작한다.

기본 연산

스택은 일반적으로 다음과 같은 기본 연산을 지원한다.

• Push: 스택의 맨 위에 새로운 요소를 추가하는 연산.
• Pop: 스택의 맨 위에 있는 요소를 제거하고 반환하는 연산.
• Peek (또는 Top): 스택의 맨 위에 있는 요소를 반환하되, 제거하지는 않는 연산.
• IsEmpty: 스택이 비어 있는지 확인하는 연산.
• Size: 스택에 저장된 요소의 개수를 반환하는 연산.

구현

스택은 배열(Array)이나 연결 리스트(Linked List)와 같은 다양한 자료구조를 사용하여 구현할 수 있다. 배열로 구현하는 경우, 스택의 크기를 미리 정해놓아야 하는 단점이 있지만, 메모리 접근 속도가 빠르다는 장점이 있다. 연결 리스트로 구현하는 경우, 스택의 크기를 동적으로 조절할 수 있지만, 배열에 비해 메모리 접근 속도가 느리다는 단점이 있다.

활용

스택은 다음과 같은 다양한 분야에서 활용된다.

• 함수 호출 스택: 프로그램 실행 중 함수가 호출될 때마다 호출 정보가 스택에 저장되고, 함수 실행이 완료되면 스택에서 해당 정보가 제거된다.
• 수식 계산: 중위 표기법으로 표현된 수식을 후위 표기법으로 변환하거나, 후위 표기법으로 표현된 수식을 계산하는 데 사용된다.
• 역추적(Backtracking): 미로 찾기, 게임 AI 등에서 탐색 경로를 저장하고 되돌아가는 데 사용된다.
• 웹 브라우저의 뒤로 가기: 방문한 웹 페이지들을 스택에 저장하여 뒤로 가기 기능을 구현한다.
• 문자열 역순 출력: 문자열을 스택에 넣었다가 다시 꺼내면 문자열이 역순으로 출력된다.

장단점

스택의 주요 장점은 다음과 같다.

• 간단한 자료구조: 구현 및 사용이 비교적 간단하다.
• 빠른 접근 속도: 맨 위의 요소에 빠르게 접근할 수 있다.

스택의 주요 단점은 다음과 같다.

• 제한적인 접근: 맨 위의 요소만 접근할 수 있으며, 중간에 있는 요소에 접근하려면 모든 상위 요소를 제거해야 한다.
• 고정 크기: 배열로 구현하는 경우 스택의 크기가 고정되어 있어, 스택 오버플로우가 발생할 수 있다. (연결 리스트로 구현하면 이 단점은 해소 가능)