스택과 큐

스택(Stack)

스택은 프링글스 통처럼 들어가는 입구와 나가는 입구가 동일한 구조의 자료구조를 의미합니다. 위에서 차곡차곡 쌓았다면, 꺼낼 때도 위에서 부터 꺼내야 합니다.

• 후입선출(Last In First Out): 마지막에 추가된 노드가 먼저 나가는 방식을 의미합니다.
• 노드를 추가하는 작업을 Push 라 하고, 위에서 부터 꺼내는 작업을 Pop 이라 합니다. 자바스크립트의 메소드인 push() 와 **pop()**이 동일한 동작을 수행합니다.
• 스택이 허용된 용량을 초과하는 경우를 스택 오버플로우 현상이라 부릅니다. 스택 오버플로우가 발생하는 원인 중 하나로 무한재귀를 경험할 때 발생할 수 있습니다.
• 크롬이나 파이어폭스 같은 이런 친구들은 각자 스택의 용량이 다르지만 일반적으로 1000~ 10000 사이로 유지되고 있습니다. 스택 오버플로우는 이러한 용량의 한계를 넘을 정도로 많은 함수가 호출되는 경우 발생하게 되고, 브라우저 상에서는 maximum call stack size 라는 에러가 발생하는 것을 볼 수 있습니다.

1등 → 2등 → 3등 순으로 들어왔지만, 나가는 순서는 3등 → 2등 → 1등 순인 것을 볼 수 있습니다.

큐(Queue)

큐는 대기열입니다.

• 선입선출(First In Last Out): 노드가 들어온 순서대로 먼저 나가는 구조를 의미 합니다.
• 큐는 동시적으로 많은 요청을 처리해야 할 때, 선착순으로 우선 도착한 순서대로 하나 씩 뽑아서 처리할 떄 사용할 수 있습니다.
• 큐는 연결 리스트와 자바스크립트 배열 모두 구현할 수 있습니다.
• 큐를 자바스크립트로 구현할 때 대기열에 추가하는 동작을 JS에서는 push() 로 구현할 수 있으며, 순차적으로 먼저들어온 노드를 꺼내는 동작은 shift() 를 사용하여 구현할 수 있습니다.