[자료구조] 스택(Stack)/큐(Queue) 자바스크립트 구현(배열, 연결 리스트)

스택

스택은 데이터를 일시적으로 쌓아 놓는 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 후입선출(LIFO, Last In First Out) 구조이다. 푸시와 팝이 이루어지는 쪽은 꼭대기(top)라 하고, 스택의 가장 아랫부분을 바닥(bottom)이라 한다.

주요 연산

• push(v): 요소를 스택의 맨 위에 추가
• pop(): 스택의 맨 위 요소를 제거하고 반환
• peek(): 스택의 맨 위 요소를 확인
• isEmpty(): 스택이 비어있는지 확인
• size(): 스택에 있는 요소의 개수를 반환

구현하기

배열 활용

class Stack {
  // 빈 배열을 생성하여 스택 초기화
  constructor() {
    this.items = [];
  }

  // 요소 추가
  push(element) {
    this.items.push(element);
  }

  // 마지막 요소 제거 및 반환. 비어 있는 경우 메시지 반환
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  // 마지막 요소 확인
  peek() {
    return this.isEmpty() ? "Stack is empty" : this.items[this.items.length - 1];
  }

  // 비어 있는지 검사
  isEmpty() {
    return this.items.length === 0;
  }

  // 요소 개수 반환
  size() {
    return this.items.length;
  }
}

const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop()); // 20
console.log(stack.size()); // 1
console.log(stack.isEmpty()); // false

연결 리스트(Linked List) 활용

배열 기반 스택은 간단하지만 요소가 많아질수록 메모리 재할당 비용이 발생할 수 있다. 이를 해결하기 위해 연결 리스트 기반의 스택을 구현할 수 있다.

// 새로운 노드 생성
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
    this.count++;
  }

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const poppedValue = this.top.value;
    this.top = this.top.next;
    this.count--;
    return poppedValue;
  }

  peek() {
    return this.isEmpty() ? "Stack is empty" : this.top.value;
  }

  isEmpty() {
    return this.count === 0;
  }

  size() {
    return this.count;
  }
}

const linkedStack = new Stack();
linkedStack.push(10);
linkedStack.push(20);
console.log(linkedStack.peek()); // 20
console.log(linkedStack.pop()); // 20
console.log(linkedStack.size()); // 1
console.log(linkedStack.isEmpty()); // false

728x90

큐

큐 또한 데이터를 일시적으로 쌓아 놓는 자료구조이다. 하지만 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out) 구조이다. 데이터가 나오는 쪽을 프론트(Front)라 하고, 데이터를 넣는 쪽을 리어(rear)라 한다.

주요 연산

• enqueue() : 큐의 끝에 새로운 요소를 추가
• dequeue() : 큐의 앞에서 요소를 제거하고 반환
• front() : 큐의 맨 앞 요소를 확인
• isEmpty() : 큐가 비어 있는지 확인
• size() : 큐의 요소 개수를 반환

구현하기

배열 활용

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    // 배열의 shift() 메서드를 활용해 앞의 요소를 제거하고 반환
    return this.items.shift();
  }

  front() {
    return this.isEmpty() ? "Queue is empty" : this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.front()); // 1
console.log(queue.dequeue()); // 1
console.log(queue.size()); // 1
console.log(queue.isEmpty()); // false

연결 리스트(Linked List) 활용

배열을 이용한 큐는 shift() 연산이 발생할 때마다 요소들이 이동하는 비용이 발생한다. 이를 개선하기 위해 연결 리스트 기반의 큐를 구현할 수 있다.

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

class Queue {
  constructor() {
    this.frontNode = null;
    this.rearNode = null;
    this.count = 0;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (this.isEmpty()) {
      this.frontNode = this.rearNode = newNode;
    } else {
      this.rearNode.next = newNode;
      this.rearNode = newNode;
    }
    this.count++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const dequeuedValue = this.frontNode.value;
    this.frontNode = this.frontNode.next;
    if (!this.frontNode) {
      this.rearNode = null;
    }
    this.count--;
    return dequeuedValue;
  }

  front() {
    return this.isEmpty() ? "Queue is empty" : this.frontNode.value;
  }

  isEmpty() {
    return this.count === 0;
  }

  size() {
    return this.count;
  }
}

const linkedQueue = new Queue();
linkedQueue.enqueue(5);
linkedQueue.enqueue(10);
console.log(linkedQueue.front()); // 5
console.log(linkedQueue.dequeue()); // 5
console.log(linkedQueue.size()); // 1
console.log(linkedQueue.isEmpty()); // false