Stack

스택은 쌓는다는 의미를 가지고 있는 단어다. 자료 구조 중 선형 구조의 한 종류이며 말 그대로 자료를 쌓는 구조이다.

LIFO(Last in First Out)

스택의 특징중 하나는 후입선출 이라는 것, 나중에 들어온 것이 먼저 나간다. 배드민턴 셔틀콕 통이 좋은 예다. 셔틀콕 통의 뚜껑을 열면 제일 위에 있는 셔틀콕을 쓰고 다시 넣어놓고 이런식으로 위에 있는 것(나중에 넣은 것)부터 사용하게 된다.

Stack의 사용 사례

• 재귀 알고리즘 → 함수의 호출
• 웹 브라우저 방문기록

Stack의 구현

자바스크립트로 스택을 구현할때 주의할점은 후입선출을 지키는 것 뿐이다. class 문법으로도 가능하지만, 구현의 편의성을 생각하면 배열로 구현하는 것이 가장 편하다. 후입선출을 구현하기 위해선 배열의 메소드를 활용하면 된다.

• push and pop
  • 배열에 들어올땐 push() : 인덱스가 점차 증가하며 자료가 쌓인다.
  • 배열에서 나갈땐 pop() : 가장 큰 인덱스 부터 차례대로 사라진다.
• unshift and shift
  • 배열에 들어올땐 unshift() : 인덱스 0번에 계속 추가된다.
  • 배열에서 나갈땐 shift() : 인덱스 0번이 사라진다.

Queue

음악 재생 목록을 queue라고 부른다. queue를 따라서 음악이 순차적으로 재생된다.(셔플을 하지 않았을때를 가정하자) 스택과 마찬가지로 자료 구조 중 선형 구조의 한 종류이다.

FIFO(First in First Out)

큐의 특징은 선입선출이다. 편의점 알바를 할때 정말 많이 듣는 단어 선입선출... 먼저 들어온게 먼저 나간다.

Queue의 사용 사례

• 프린터의 출력 처리
• 티켓 카운터에서 번호표 순서대로 호출
• 프로세스 관리

Queue의 구현

Queue도 배열로 구현이 가능하다. 선입선출을 지켜 구현하기만 하면 된다.

• push and shift
  • 배열에 들어올땐 push() : 뒤에 추가된다.
  • 배열에서 나갈땐 shift() : 앞부터 없어진다.
• unshift and pop
  • 배열에 들어올땐 unshift() : 앞에 추가된다.
  • 배열에서 나갈땐 pop() : 뒤부터 없어진다.

잘 생각해보면 배열에서 구현할 경우 큐가 진행되면서 인덱스가 점점 증가하거나 감소하는 방향으로 움직이게 된다. 인덱스가 음수가 될 수 는 없으므로 큐의 길이 만큼 계속해서 인덱스가 재 지정되게 되는데 이는 원본 자료를 변형하는 결과로 이어진다.

이런 문제를 해결할 수 있는 방법으로 원형큐나 우선순위 큐가 있다.