스택

스택은 자주 사용하게 되는 자료구조 중 하나이다. 자료를 쌓을때 하나씩 비교 하기도 좋고 나또한 자주 사용한다.

스택은 접시를 쌓는것도 같다. 접시를 올리고 위에서부터 접시를 깨내듯이 뒤로 넣고 뒤로만 뺄수 있다.

스택의 마지막 요소를 top이라고 부르기도 한다.

재귀함수에서 보듯이 이어진 함수를 여러번 호출하면 스택이 쌓이게 된다.
스택을 쌓고나서 역순으로 하나씩 실행하게 된다.
각 함수는 일정 메모리를 차지하기 때문에 스택 메모리 안에 너무 많이 쌓이면 메모리 에러가 발생한다.

그래서 재귀함수 내에서도 리턴 값을 지정해서 함수가 무한으로 실행되지 않게 탈출 루트를 짜놓는 것이 중요하다.

자바스크립트로 구현하게 되면 stack 이라는 배열을 만들어주고 push메소드로 뒤로 넣어주고 pop메소드로 뒤에서 뺀다.

큐

큐는 순서대로 실행된다고 생각되면 된다. 뒤로 넣고 앞으로 빠진다. 순서대로 진행된다고 생각하면 된다.

스택에는 제일 위를 top으로 나타낸다고 하였다.
큐는 맨처음을 head로 나타내고 맨 끝이 rear로 나타내는 용어가 있다.

특수한 큐도 있는데 순환 큐 라고 부른다.

순환큐

front와 rear가 연결되어 있다. 1,2,3의 데이터가 있어서 순서대로 1->2->3 이렇게 진행되지만
이런 경우 3이 실행되고 다시 1로 넘어간다.

순환 큐가 사용되는 이유는 메모리 관리가 쉽기 때문이다. 하지만 자바스크립트에서 메모리를 알아서 정리해주기 때문에 효용성이 조금 떨어진다.

우선순위 큐

들어가고 빠지는 것은 같지만 들어갈때 제일 뒤에 넣는게 아니라 우선순위 순서를 따져서 데이터를 넣는다.
우선순위는 프로그래머가 직접 정해서 코드를 짤수 있지만 이를 구현하면 데이터를. 삽입하기 힘들다는 단점이 있다.

그래서 힙이라는 자료구조를 사용해서 구한다.

자바스크립트로 구현하게 되면 따로 que라는 배열을 만들어 놓고 거기에 데이터를 넣는다.
넣을때는 push메소드를 사용해서 뒤로 넣어주고 shift메소드로 앞으로 꺼내면 된다.

출처 : 제로초님 블로그
원본 : https://www.zerocho.com/category/Algorithm/post/580b9b94108f510015524097