스택과 큐(선형큐, 원형큐)의 개념을 정의하고 삽입, 삭제, 연산 방법에 대해 설명하시오.

1. 스택의 개념

스택은 데이터를 일시적으로 저장하는 선형 자료구조로서 후입선출(LIFO, Last In First Out) 원칙에 따라 동작하는 구조이다. 즉, 가장 마지막에 넣은 데이터가 가장 먼저 꺼내지는 구조로, 이는 일상생활에서도 쉽게 찾아볼 수 있다. 예를 들어, 책 더미, 접시 쌓기, 또는 브라우저의 뒤로가기 버튼이 스택 구조의 실생활 예시이다. 스택은 한 쪽 끝에서만 삽입과 삭제가 일어나는 특성을 가지고 있으며, 이를 `탑` 또는 `스택의 꼭대기`라고 부른다. 구현 방식에는 배열을 이용하거나 연결 리스트를 활용하는 방법이 있는데, 이 때 배열을 사용할 경우 크기 제한이 있으나 구현이 간단하다. 스택의 대표적인 연산은 삽입인 `푸쉬(push)`, 삭제인 `팝(pop)`, 그리고 현재 꼭대기 원소를 확인하는 `탑(top)`, 그리고 스택이 비어있는지 검사하는 `비어있음(empty)`이다. 푸쉬 연산은 새로운 원소를 스택의 맨 위에 넣는 과정으로, 이때 배열에서는 인덱스를 하나씩 증가시키며 데이터 저장 위치를 할당한다. 팝 연산은 맨 위 원소를 제거하는데, 이 과정에서 원소를 제거하고 그 값을 반환하며, 만약 스택이 비어있다면 오류가 발생한다. 탑 연산은 현재 …