Stack과 Queue 구현

Stack 구현

1) 배열
2) 연결리스트

배열

push pop 사용

연결리스트

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
    this.len = 0;
  }

  push(value) {
    const node = new Node(value);
    node.next = this.top;
    this.top = node;
    this.len += 1;
  }

  pop() {
    const value = this.top.value;
    this.top = this.top.next;
    this.len -= 1;
    return value;
  }

  size() {
    return this.len;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.size());
console.log(stack.pop());
console.log(stack.size());

1. Node 클래스 : value와 next 속성값을 지닌다.
2. Stack 클래스 : 기존의 this.top을 연결받으면서 다음을 위해 this.top을 자신 노드로 설정한다.

ex) 1이 push 되면 this.top은 null이므로 연결이 없고 1이라는 node가 this.top이 된다. (Node { value: 1, next: null })
2가 push되면 this.top은 1이라는 node가 next로 연결되고 this.top은 next로 연결된 것을 포함한 내용이된다. (Node { value: 2, next: Node { value: 1, next: null } })
pop의 경우 현재 가장 높은 this.top부분의 next인 다음것이 this.top이 되도록 한다. (즉, 위에를 제거하는 것이다. )

---

그림 예시

ex) stack.push(5) , stack.push(6) 실행시

Queue 구현

1. 배열
2. 연결리스트

배열

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }

  peek() {
    return this.queue[this.front];
  }

  size() {
    return this.rear - this.front;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.dequeue());
queue.enqueue(8);
console.log(queue.size());
console.log(queue.peek());

front와 rear를 기준으로 늘어날때마다 rear를 높이고 줄어들 때마다 front를 늘려준다.

연결리스트

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null; //0에서 null로수정
    this.tail = null;
    this.len = 0;
  }

  enqueue(newValue) {
    const newNode = new Node(newValue);

   if (this.head === null) {
      this.tail = newNode;
      this.head = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.len += 1;
  }

  dequeue() {
    const value = this.head.value;
    this.head = this.head.next;
    this.len -= 1;
    return value;
  }

  size() {
    return this.tail.value - this.head.value + 1;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
console.log(queue.dequeue());		//1
console.log(queue.size());		//4
console.log(queue.dequeue());		//2
console.log(queue.size());		//3

stack과 마찬가지로 Node클래스 생성
Queue에는 기본적으로 시작과 끝을 나타내는 head와 tail설정

상황설명

1) this.tail.next = newNode;
2) this.tail = newNode;

1) 아래에 console.log(this)를 추가할 경우

2) 아래에 console.log(this)를 추가할 경우

Queue {
  head: Node { value: 1, next: Node { value: 2, next: null } },
  tail: Node { value: 1, next: Node { value: 2, next: null } },
  len: 1
}		//1)
Queue {
  head: Node { value: 1, next: Node { value: 2, next: null } },
  tail: Node { value: 2, next: null },
  len: 1
}		//2)
Queue {
  head: Node { value: 1, next: Node { value: 2, next: [Node] } },
  tail: Node { value: 2, next: Node { value: 3, next: null } },
  len: 2
}		//3)
Queue {
  head: Node { value: 1, next: Node { value: 2, next: [Node] } },
  tail: Node { value: 3, next: null },
  len: 2
}		//4)
Queue {
  head: Node { value: 1, next: Node { value: 2, next: [Node] } },
  tail: Node { value: 3, next: Node { value: 4, next: null } },
  len: 3
}		//5)
Queue {
  head: Node { value: 1, next: Node { value: 2, next: [Node] } },
  tail: Node { value: 4, next: null },
  len: 3
}		//6)

1)에서는 같다가 2)에서 head.next가 tail과 같은것으로 인식되고
3)에서 head.next가 tail과 같은 것으로 인식되다가
this.tail = newNode;에 의해 tail만 4)처럼 바뀌게 된다.

• 즉, 같은메모리를 쳐대보므로 head에서는 next를 통해 계속 생성되는 것이고 마지막에 tail은 같은 메모리를 쳐다보는 next의 다음을 head와 tail에 적용후 현재 node를 추가하는 것으로 끝이난다.

• 사진의 위에는 head 아래는 tail이다.