JavaScript Array methods의 사용을 최소화하는 스프린트를 통해 구현해본 내용을 정리했다.

Stack

개념

stack에 처음 추가한 element가 제일 마지막으로 나온다.
후입선출 LIFO === FILO ( last in, first out )

용어	뜻
top	데이터가 입출력되는 위치( top의 데이터가 0인 상태를 bottom이라고 한다. )
.push	입력, top의 위치에 데이터를 입력하고, top을 증가시킨다.
.pop	출력 및 삭제, top을 감소시키고, 해당위치의 데이터를 삭제한다.

이해한대로 그려본 그림

method

"맨 위"를 가리키는 top
"스택의 상단"을 참조하는 동안 push는 element를 stack의 "맨 위"에 추가하고 pop은 stack의 "맨 위"element를 제거하고 반환

Method	Execution	Return Value
push(element)	요소를 스택의 최상단에 추가	none
pop()	스택의 최상단에서 요소를 제거하고 반환	top의 값
peek()	스택의 최상단에 위치하는 요소를 확인하고 반환	top의 값
size()	스택의 현재 요소 개수를 반환	stack의 길이
isEmpty()	스택이 비어있는지 확인	boolean값

Stack의 Method를 pseudocode로 구현하기

1. stack을 생성한다.

stack생성 {
  비어있는 객체
  비어있는 top
}
  
class Stack{
  constructor(){
    this.storage = {}
    this.top = 0
  }
}

2. 메서드

push(element){
  element가 객체에 하나 추가되면
  stack의 높이, top이 1씩 증가한다.
}

pop(){
  element가 삭제되면
  그 삭제된 element를 반환한다.
  stack의 높이, top이 1씩 줄어든다.
  
}

peek(){
  만약 storage가 비어있다면
  undefined를 반환
  그렇지 않으면
  this.storage[this.top-1]을 반환한다.
}

size(){
  return this.top;
}

isEmpty(){
  
  if(this.top === 0){
    return true;
  }
  return false;
}

배열을 이용하거나 후에 나오는 개념인 Linked List를 이용해서도 구현할 수 있다고 한다.

Stack 사용 예

프로그램 수행 시에 사용한다.

프로그램에서 함수1를 호출 >> 프로그램 위에 함수1이 쌓이고 함수1를 수행하는 중에 함수2가 호출되면, 함수1 위에 함수2가 stack처럼 쌓인다.
함수2의 실행이 완료되면 함수1이 실행되고, 함수1의 실행이 완료되면 프로그램 실행시작.

예시) 쌓여있는 접시 더미, 하노이의 탑

function 의 호출될 때 Stack 에 쌓이게 되는데
“stack overflow”는 메모리가 비어있는 상태에서 데이터를 꺼내려고 했을 때 발생하는 오류의 일종
실수로 재귀함수, 무한루프 등을 호출로 인해 한계를 넘어 섰을 때 stack overflow가 발생한다.
재귀함수를 호출해서 오류가 나는 경우: 바로 함수를 연이어 호출하면 스택처럼 메모리에 쌓이고(push) 쌓인 역순으로 하나씩 실행되는데(pop) 여러 함수가 중첩되어 호출되면 스택처럼 쌓여서 에러가 자주 발생한다.

참고)

자료구조	가져오기	추가하기	삭제하기
Stack	O(n)	O(1)	O(1)

Queue

개념

대기열로 이해할 수 있다. 대기열 순번 1이 먼저 입장한다. 나중에 줄 서는 사람은 맨 끝에 줄을 서고 맨 앞에서부터 입장한다.
선입선출 FIFO

Q. front가 2이고, rear가 6인 큐의 요소 개수는? (front와 rear는 요소를 가리키는 포인터이다.)
Correct Answer : 5
용어 | 뜻
:---- :| ----
front | 가장 앞에 있는 데이터를 가리키는 정보
head | dequeue 하였을 시 출력되는 값 (유의어: front, first 등)
rear | 맨 뒤에 있는 데이터를 가리키는 정보, queue의 마지막 값의 인덱스를 가리킨다.
tail | enqueue 하였을 시 출력되는 값 (유의어: rear, back, last 등)

큐가 가득 찼을 때 삽입할 수 없으며 큐가 비어있을 때 삭제할 수 없다.

이해한대로 그려본 그림

method

Method	Execution	Return Value
enqueue(element)	요소를 큐의 뒤(rear)에 추가	none
dequeue()	요소를 queue의 앞(front)에서 제거하고 반환	제거한 값
peek()	queue의 front에 위치하는 요소를 확인하고 반환	front의 값
size()	queue의 현재 요소 개수를 반환	queue의 길이
isEmpty()	queue가 비어있는지 확인	boolean값

Queue의 Method를 pseudocode 로 구현하기

1.queue를 생성한다.

queue생성{
  비어있는 front;
  비어있는 rear;
}

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

2. method

값을 추가하고 삭제할 때 front와 rear를 재설정해주는 작업이 필요할 것 같다.

enqueue(element){
  element가 객체에 하나 추가되면
  방금 추가한 값을 rear로 변경한다.
  맨 뒤의 위치값 rear이 1씩 늘어난다. 
}

dequeue(){
  storage가 비어있다면
  storage를 반환한다.
  큐가 비어있다는 것은 front와 rear의 값이 같은 경우
  
  queue의 첫번째 element의 값을 제거한다.
  그럼 front는 그 다음 element가 된다.
  제거된 element를 반환한다.
}

peek(){
  만약 storage가 비어있다면
  undefined를 반환한다.
  그렇지 않으면
  this.storage[this.front] 값을 반환한다.
}

size(){
  만약 추가된 elements보다 같거나 많은양의 elements를 제거하면 
  0을 반환한다.
  아닌 경우에는
  return this.rear - this.front;
}

isEmpty(){
  만약 front가 this.size이라면
  true를 리턴한다.
  그렇지 않으면
  false를 리턴한다.
}

동작

queue "맨 위"에 항목을 저장하고 "맨 앞"에서 검색

자바스크립트의 배열로 따지면 맨 뒤에 element를 추가하는 push(enqueue)와 맨 앞 element를 제거하는 shift(dequeue) 메소드만 있는 데이터 구조

추가로 맨 앞의 데이터를 알 수 있는 front가 있다.

stack에는 "맨 위"를 가리키는 top만 있었다면 queue에는 "맨 앞"을 가리키는 head와 "맨 위"을 가리키는 rear 두 개가 있다.

대기열의 특성 중 하나는 특정 용량이 없다
이미 포함 된 요소 수에 관계없이 항상 새 요소를 추가 할 수 있다.

배열을 이용하거나 후에 나오는 개념인 Linked List를 이용해서도 구현할 수 있다고 한다.

Queue 사용 예

여러개의 작업이 수행되고 있는 중에 새로운 작업이 수행되어야 하는 경우

대기열은 데이터를 처리할 시간이 충분하지 않을 때 유용하다.
처리할 수 없는 데이터를 대기열에 추가해두었다가 가능해졌을 때 처리한다. 대기열은 도착한 순서대로 처리되도록 한다.

기존에 수행되던 작업 중에서 가장 먼저 메모리에 올라온 작업이 out(실행)되고
새로운 작업을 메모리에 올린다. 이 경우에 운영체제는 현재 수행 중인 작업을 queue의 형태로 관리한다.

프로그램의 event발생 시(버튼 누르기, 윈도우 크기조정, 메뉴 선택 등) 발생한 event가 queue에 저장된다.
수행중인 프로그램이 queue에 저장된 것을 앞에서부터 읽어와서 처리한다.

참고)

자료구조	가져오기	추가하기	삭제하기
Stack	O(n)	O(1)	O(1)

추가 개념 요약

우선 순위 Queue

dequeue를 실행하면 우선 순위가 높은 값이 먼저 dequeue된다.

예시
(조건 priority 가 높을 수록 우선 순위가 높다.)

const queue = new PriorityQueue();

queue.enqueue({ value: 'A', priority: 5 })
queue.enqueue({ value: 'B', priority: 2 })
queue.enqueue({ value: 'C', priority: 1 })
queue.enqueue({ value: 'D', priority: 4 })
queue.enqueue({ value: 'E', priority: 3 })
// dequeue 5 times...

원래대로라면 enqueue된 순서인 A-B-C-D-E 순으로 출력될텐데
우선 순위 queue에서는 우선순위가 높은 것이 먼저나온다. 늦게들어가더라도
따라서 A-D-E-B-C 순으로 출력된다.

Q. 우선 순위 QUEUE를 구현한다고 하면 우선순위를 어떻게 계산할 수 있을까?
A. 우선순위는 정렬sort할 수 있는 값으로 두어야한다.
ex) 우선순위를 숫자로 설정하고 조건문을, max를 이용해서 최대값인 것을 dequeue한다.

관련개념 "힙트리" : 최대값 최소값을 효율적으로 찾을 수 있도록 고안된 자료구조

원형 Queue

선형 queue와 원형 queue는 front와 rear를 저장하는 방식이 다르다.
원형 QUEUE는 동그랗게 생겨서 front와 rear가 붙어있는 구조.

다른 언어에서는 배열의 크기가 정해져 있는데
JavaScript의 배열/객체는 크기가 고정되어 있지 않다. 그래서 js에서는 걱정하지 않아도된다.
원형 queue의 효용이 javascript에서는 살짝 떨어지는 편.

원형queue를 쓰는 이유: 재사용

QUEUE를 배열로 구현했을 때
삽입 삭제 연산이 이루어지면서 front와 rear의 위치가 뒤로 점점 밀려나고 앞 쪽에는 데이터가 들어올 수 있는 공간이 있지만 rear가 배열 인덱스의 가장 마지막을 가리키고 있다면, enqueue했을 때 실제로 큐에 공간이 있음에도 불구하고 삽입할 수 없는 문제가 생기게 된다.
즉 삭제가 이루어졌을 때 나머지 데이터가 앞쪽으로 이동하지 않으면 공간의 낭비가 생기게 된다.
이것이 큐를 배열로 구현했을 때 생기는 문제점이며 환형배열을 통해 해결한다.