스택과 큐의 차이점을 설명해보세요.

TCP/IP가 "스택"이라고 언급되는 경우가 종종 있다. 이것은 데이터교환의 클라이언트와 서버 양단에서 모든 데이터가 지나가는 계층들인 TCP, IP 그리고 기타 다른 것들을 지칭하는 것이다. TCP/IP의 것들과 비슷한 계층의 명확한 그림이, 네트웍 통신에 관련된 참조모델인 OSI의 정의에서 제공되고 있다.

스택이라는 용어는 때로 TCP/IP의 계층들을 지원하는 유틸리티를 포함하기 위해 사용된다. 넷스케이프에서 발간한 핸드북에 보면 "인터넷에 성공적으로 접속하기 위해서는, 넷스케이프와 TCP/IP 소프트웨어로 구성되는 TCP/IP 스택, 소켓 소프트웨어, 그리고 하드웨어 드라이버 소프트웨어 등과 같은 응용 소프트웨어가 필요하다. 셰어웨어를 포함하여, 몇몇 유명한 윈도우용 TCP/IP 스택들이 사용 가능하다."라는 구절이 있다.

프로그래밍에서, 스택이란 처리해야 할 요청을 저장하는 데이터 저장소 또는 버퍼이다. IBM의 컴퓨터 사전에 보면, 스택은 항상 푸시다운 목록이라고 나와 있는데, 이는 새로운 요청이 들어오면 그것은 이전의 것을 밑으로 눌러 내린다는 의미이다. 스택을 바라다보는 또 다른 방법은, 처리할 항목을 항상 스택의 최상위로부터 가져오는 프로그램이라고 이해하는 것이다 (이것은 먼저 도착한 것을 먼저 처리하는 "FIFO"와는 아주 다른 방법이다).

큐는 사람들이나 물건들이 처리를 기다리며 서있는 줄을 말하는데, 줄의 맨 앞에서부터 순서대로 처리된다. 컴퓨터 프로그래밍에서의 큐는 데이터가 들어간 순서대로 제거되는 자료구조를 말한다. 이러한 순서를 가리켜 흔히, 선입선출(FIFO ; first in, first out)이라고 한다. 이와는 반대로 스택이라는 자료구조는 먼저 들어간 데이터가 가장 나중에 제거되는 형식인데, 이것을 LIFO (last in, first out)라 한다.

스택은 LIFO(last in first out)이고, 큐는 FIFO(first in first out)이다. 간단하게 설명하자면 스택은 밑이 막힌 통에 값을 차례대로 저장해놨다가 그 값이 필요 할 때는 가장 위에부터 꺼내는 것이다. 이런 구조를 어디다가 쓰는지 궁금할 수 있는데, C에서는 함수 호출을 할 때 아주 필수적으로 쓰인다. 함수가 함수를 부르고 하는 단계를 들어갈 때마다 현재 함수에서 사용되는 값을 스택에다가 집어넣고 부르는 함수에 쓰일 값들에 대한 작업을 시작한다. 이렇게 하면 함수가 호출되기 전의 상태가 제대로 저장이 된다.

큐는 스택과 반대로 뻥 뚫린 통에 값을 차례대로 저장해놓으면 넣은 순서대로 값이 빠져 나오는 것이다. 좋은 예로 키보드 입력인데, 키보드로 값을 입력하면 차례대로 임시 버퍼에 쌓이게 된다. 그러면 프로그램에서는 이 입력 값을 이용하기 위해서 입력된 순서대로 값을 꺼내오게 된다.

(1) 선형(Linear)큐

선형 큐는 여러 개의 데이터 항목들이 하한부터 차례로 저장되는 모양을 가진다. 새로운 데이터 항목의 삽입은 rear에서 일어나고, 이 위치는 rear 포인터라는 지시자가 가리킨다. 데이터 항목의 삭제는 front에서 일어나며, 이 위치는 front 포인터라는 지시자가 가리킨다. front 포인터와 rear 포인터는 초기에 하한에서 시작하여 삽입과 삭제가 반복됨에 따라 상한 쪽으로 이동한다.

(2) 이동(Moving)큐

큐에서 더 이상 자료를 삽입할 수 없는 상태인 rear=N이면 오버플로우(overflow)가 발생한다. 이 오버플로우를 해결하는 방법에는 2가지 방법이 있는데 이동 큐(Moving Queue) 방식과 환형 큐(Circular Queue)방식이다. 동 큐 방식은 큐 의 원소들을 이동시키는 방법이며 원형 큐 방식은 큐 구조를 원형으로 연결하여 rear포인터의 값을 변화시켜 가용공간에 원소를 삽입하는 방식이다.

(3) 환형(Circular)큐

환형 큐 방식이란 이동 큐(Moving Queue) 방식의 단점을 보완하기 위한 방법으로 크기 n인 1차원 배열 형태의 큐를 원형(Circular)으로 구성하여 배열의 처음과 끝을 연결하여 만든 것을 말한다.

오버플로우가 발생했을 때 큐 구조가 원형으로 구성되어 있으므로 rear 포인터 값을 변화시켜 새로운 가용공간에 원소를 삽입하므로, 오버플로우 시 이동 큐 방식에서처럼 원소들을 이동시 필요가 없으므로 소요되는 시간을 절약할 수 있다.