스택(Stack)
Stack에 대해서 설명해주세요
스택은 자료구조의 일종으로 저는 스택을 떠올릴 때 음식점에 수직으로 쌓인 접시를 생각합니다. 접시 하나당 하나의 데이터라고 상상합니다. 쌓여있는 접시에서 가장 아래있는 접시를 꺼내기 위해서는 위에 겹쳐져 있는 접시들 부터 차례대로 꺼내야할 것입니다. 애초에 맨 아래 부터 뺄 수 있는 구조가 아니죠.
그래서
스택은 나중에 즉 마지막에 들어온 데이터가 가장 먼저 나가는후입선출(LIFO)의 자료구조 입니다.
Stack이 사용되는 예시를 몇가지 들어주세요
가장 흔한 예는
웹브라우저 히스토리입니다. 앞으로 가기나 뒤로 가기 버튼을 클릭해서 앞 또는 뒤로 순서대로 웹사이트를 이동할 수 있습니다. 즉,스택의 가장 유용한 점은 작업의 이전 상태를 마지막 순서대로 메모리에 저장한다는 것입니다.
큐(Queue)
Queue에 대해서 설명해주세요
큐를 떠올릴 때 저는 음식점에 사람들이 서 있는대기줄을 떠올립니다. 대기줄에서는 가장 먼저 줄 선 사람이 먼저 음식점으로 입장하게 됩니다.
스택과는 반대로 먼저 들어온 데이터가 먼저 나가는선입선출(FIFO)의 자료구조입니다.
Queue가 사용되는 예시를 몇가지 들어주세요
큐가 사용되는 일반적인 예로는프린터가 있습니다. 집에 한 대의 프린터가 있고 세 대의 다른 컴퓨터에서 각각 인쇄를 요청했을 때, 먼저 인쇄 버튼을 클릭하는 사람이 첫번째 대기열에 들어가고 그 다음 사람이 차례로우선순위를 갖게 됩니다.
Stack과 Queue를 비교해서 설명해주세요
스택(Stack)
스택과큐를구현의 측면에서 설명드리겠습니다. 자바스크립트에는 스택과 큐라는 자료구조가 없기 때문에직접 구현해야합니다. 둘 다배열과연결 리스트자료구조로 구현할 수 있지만장단점이 있기 때문에 우선순위에 따라 선택할 수 있습니다.
스택을배열로 구현할 경우 데이터에 좀 더 빠르게 엑세스할 수 있습니다. 왜냐하면배열자료구조의 경우 각각의 데이터가메모리 상에서 순차적으로 바로 옆에 위치해있기 때문입니다.
반면,연결 리스트로 구현할 경우 메모리 상에서 흩어져 있고포인터를 구현하는데 좀 더 많은메모리가 소모됩니다.
장단점(Pros & cons)
하지만 그렇다면 스택을 무조건 배열로 구현하는 것이 더 유리한 것은 아닙니다. 이러한 부분은 저장해야하는 데이터의 스케일에 따라 우선순위가 달라질 수 있습니다.
배열은 최초에 할당한 메모리의 할당량을 초과할 경우 그것의 배수로 메모리 상에서 새로운 공간을 할당 해버리기 때문에 남은 빈 공간이 많아
메모리 낭비로 이어질 수 있습니다.
반대로, 연결리스트는 배열에 비해서 새로운 데이터를 할당할 때에
메모리 사이즈 측면에서 유동적입니다.
때문에 한가지를 답이 있는 문제라기 보다는 스택 안에 넣어야하는
자료의 양이 고정되어있고 그 데이터의 양을 우리가 미리 알고 있다면배열로 구현하는 것이유리하고, 고정적인 것이 아니라유동적으로 변경될 수 있다면연결리스트로 구현하는 것이 메모리 낭비를 줄일 수 있습니다.
큐(Queue)
큐의 경우 답이 좀 더 심플합니다. 무조건 연결 리스트로 구현하는 것이 유리합니다.
배열로 구현하면불리한 이유는 아시다시피배열은 인덱스가 존재합니다. 스택은 먼저 들어온 자료가 먼저 나가는 선입선출의 자료구조입니다. 스택을 배열로 구현할 경우 가장 맨 앞의 요소를 제거하는 작업인 shift는 모든 인덱스의 번호를 한칸씩 당기는 작업이기 때문에O(n)의 시간복잡도를 가집니다. 반면,연결 리스트는 head와 tail을 가리키는 포인터가 있기 때문에 단순하게 맨 앞의 자료를 제거한 후에 포인터만 다음 자료를 가리키도록(참조도록) 해주면 되기 때문에O(1)의 시간복잡도를 가집니다.
