스택(Stack) 과 큐(Queue)

 

이번에는 스택과 큐를 정리해본다.

 

두가지 다 많이 사용되는 자료구조로 차이점이 있다면

 

스택은 LIFO(Last In First Out) 구조로 후입선출. 즉 마지막에 들어온 것이 제일 먼저 나가게된다. like 프링글스

 

그러다보니 Javacript 배열의 push()와 pop() 메소드만 사용한다 생각하면 된다. push와 pop 메소드도 스택에서

나온 이름이라고 한다. 그리고 또 하나 스택의 마지막 요소가 뭔지 알려주는 stackTop 메소드가 있다. top라고

부르기도 한다.

 

주로 사용하는곳은 브라우저 히스토리

 

뒤로가기시 맨 처음 페이지가 아닌 맨 마지막 페이지(최근)로 이동하게된다.

 

자바스크립트로 만들어보면

 

class Stack {
  arr = [];

  push(value) {
    this.arr.push(value);
  }
  pop() {
    this.arr.pop();
  }
  top() {
    return this.arr.at(-1);
  }
  get length() {
    return this.arr.length;
  }
}
const stack = new Stack();

이런 구조가 나올수 있다.

 

 

조금 변환해서 저번에 업로드한 연결리스트로 스택을 만들어 본다면?

 

class Stack {
  length = 0;
  head = null;

  push(value) {
    const newNode = new Node(value);
    if (!this.head) { //this.head가 null일경우엔 newNode를 넣어주기
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) { //맨 마지막node의 next에 newNode를 추가해주기 위해 while로 순회
        current = current.next;
      }
      current.next = newNode;
    }
    this.length++;
  }

  pop() {
    if (!this.head) return null; // this.head가 null 일경우 종료

    if (this.length === 1) { // length가 1일 경우 head값에 null, length 0
      const value = this.head.value;
      this.head = null;
      this.length--;
      return value;
    }

    let current = this.head;
    while (current.next.next) { //마찬가지로 맨 끝의 값을 없애기 위해 순회 마지막 current.next에 null
      current = current.next;
    }
    const value = current.next.value;
    current.next = null;
    this.length--;
    return value;
  }

  top() {
    if (!this.head) return null;

    let current = this.head;
    while (current.next) { //동일하게 맨 뒤의 노드를 찾아 순회 마지막 노드의 value를 리턴.
      current = current.next;
    }

    return current.value;
  }
}

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

const stack = new Stack();

 

 

 

이번엔 큐(Queue)

 

큐는 FIFO(First In First Out)구조로 선입선출. 첫번째로 들어온 것이 제일 먼저 나가게된다. like  대기열

 

스택과의 또 다른 차이점은 뒤에 추가되고(enqueue) 앞에서 빠지는(dequeue)구조이다. 자바스크립트 배열 메소드로는 push(enqueue)와  shift(dequeue) 메소드만 있다고 생각하면 된다. 추가로 제일 앞의 데이터를 알 수 있는 front 메서드가 있다.

 

class Queue {
  arr = [];

  enqueue(value) {
    this.arr.push(value);
  }

  dequeue() {
    this.arr.shift();
  }

  peek() { // queue는 top이 아닌 peek라고 부름. 위 아래 개념이 아니기 때문에
    return this.arr[0]; 
  }

  get length() {
    return this.arr.length;
  }
}

const queue = new Queue();

 

이걸 연결리스트로 구현해본다면?

 

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

class Queue {
  length = 0;
  head = null;

  enqueue(value) {
    const newNode = new Node(value); //새로운 노드 생성
    if (!this.head) this.head = newNode; // 기존 head가 null일 경우 새 노드를 할당
    else {
      let current = this.head;
      while (current.next) { // stack과 마찬가지로 next가 null일때까지(마지막노드)를 찾아 순회
        current = current.next;
      }
      current.next = newNode; // 마지막 노드의 next에 새 노드를 할당
    }
    this.length++;
    return this.length;
  }

  dequeue() {
    if (!this.head) return null;
    else { //첫번째 요소를 제거하기 위해 첫번째 요소의 next를 첫번째 요소로 할당
      const current = this.head;
      this.head = current.next;
      this.length--;
      return current.value;
    }
  }

  peek() { //멘 첫번째 노드를 가져오기위해 head의 value 리턴
    return this.head?.value;
  }
}

 

스택에는 제일 위를 가르키는 top이 있었다면, 큐에는 맨 앞(head)와 맨 끝(rear)가 있다.

 

큐에는 다른 종류로 맨 앞(head)와 맨 끝(rear)가 연결되어 있는 순환큐와 enqueue 할 때 우선순위 순서를 따져서 데이터를 넣는 우선순위 큐가 있다. 우선순위 큐는 주로 힙이라는 자료구조를 사용해서 구현하는데 이건 다른 포스트로 정리 할 예정이다.