[자료구조] 스택과 큐 | LIFO, FIFO, push & pop, shift

나윤빈·2023년 11월 29일

자료구조

자료구조와 알고리즘

목록 보기

2/11

1. 스택(Stack)

스택은 후입선출(Last In, First Out: LIFO) 원칙에 따라 데이터를 저장하는 자료구조이다.
이는 가장 최근에 추가된 항목이 가장 먼저 제거되는 구조를 의미한다.
스택은 데이터의 삽입과 삭제가 한쪽 끝(top)에서만 이루어지는 선형 자료구조이다.

주요 연산

Push(삽입): 스택의 맨 위에 새로운 데이터를 추가한다.
Pop(삭제): 스택의 맨 위에서 데이터를 제거한다.
Peek(참조): 스택의 맨 위에 있는 데이터를 조회하되, 제거는 하지 않는다.
isEmpty(비어있는지 확인): 스택이 비어있는지 여부를 확인한다.
size(크기 확인): 스택에 포함된 요소의 수를 반환한다.

자바스크립트 구현

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

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

  pop() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.pop();
  }

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

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

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

  clear() {
    this.items = [];
  }
}

let stack = new Stack();

stack.push(1);
stack.push(2);
stack.push(3);

console.log("Top element: ", stack.peek()); // 3

console.log("Stack size: ", stack.size()); // 3

console.log("Popped element: ", stack.pop()); // 3

console.log("Stack after pop: ", stack.items); // [1, 2]

시간복잡도 Big O

삽입 : O(1)
삭제 : O(1)
탐색 : O(N)

스택 자료구조의 기본 연산인 삽입과 삭제의 시간복잡도는 O(1)이다. 새로운 요소를 스택에 추가하는 연산은 배열의 맨 끝에 요소로 추가하면 되고, 제거하는 연산도 배열의 맨 끝에서 직접 제거할 수 있다. 하지만 특정 데이터를 탐색할 때에는 찾을 때까지 수행 해야하므로 O(n)의 시간복잡도를 가진다.

2. 큐(Queue)

큐는 선입후출(First In, First Out: FIFO) 원칙에 따라 데이터를 저장하는 자료구조이다.
이는 가장 먼저 삽입된 데이터가 가장 먼저 제거되는 원리를 의미한다.
큐는 데이터가 입력되는 곳과 출력되는 곳이 각각 다른 위치에 있는 구조이다.

주요 연산

Enqueue(인큐): 큐에 데이터를 추가하는 작업이다. 데이터는 큐의 뒤(rear)에 추가된다.
Dequeue(디큐): 큐에서 데이터를 제거하는 작업이다. 데이터는 큐의 앞(front)에서 제거된다.
Peek(피크): 큐의 가장 앞에 있는 데이터를 조회하지만, 제거는 하지 않는다
isEmpty(비어있는지 확인): 큐가 비어있는지 여부를 확인한다.
size(크기 확인): 큐에 현재 저장된 데이터의 개수를 반환한다.

자바스크립트 구현

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

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

  dequeue() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.shift();
  }

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

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

  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items[0];
  }

  clear() {
    this.items = [];
  }
}

let queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log("Front element: ", queue.peek()); // 1

console.log("Queue size: ", queue.size()); // 3

console.log("Dequeued element: ", queue.dequeue()); // 1

console.log("Queue after dequeue: ", queue.items); // [2, 3]