[자료구조] Stack, Queue

스택(Stack)과 큐(Queue)는 둘 다 데이터 구조의 일종이다. 

 

스택(Stack)

스택은 LIFO(Last in, First Out) 구조디아, 즉 가장 늦게 추가된 요소가 가장 먼저 제거되는 구조이다.

 

 

기본 연산:

1. push: 스택의 맨 위에 요소를 추가하는 연산
2. pop: 스택의 맨 위에 있는 요소를 제거하고 반환하는 연산
3. peek 또는 top: 스택의 맨 위에 있는 요소를 제거하지 않고 반환하는 연산
4. isEmpty: 스택이 비어있는지 확인하는 연산

 

사용 사례:

• 브라우저 뒤로가기 : 가장 마지막에 열린 페이지부터 다시 보여준다.
• 함수 호출 스택: 재귀 호출에서 함수가 호출될 때마다 스택에 쌓였다가 반환될 때마다 스택에서 제거된다.
• 실행 취소 기능: 최근 작업들을 스택에 저장해 두었다가 실행 취소할 때 스택에서 제거한다.

 

스택 코드

class Stack<T> {
  private items: T[] = [];

  push(item: T): void {
    this.items.push(item);
  }

  pop(): T | undefined {
    return this.items.pop();
  }

  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

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

 

 

---

 

큐(Queue)

큐는 FIFO(First In, First Out) 구조로, 가장 먼저 추가된 요소가 가장 먼저 제거된다.

 

기본 연산:

 

1. enqueue: 큐의 맨 뒤에 요소를 추가하는 연산
2. dequeue: 큐의 맨 앞에 있는 요소를 제거하고 반환하는 연산
3. front 또는 peek: 큐의 맨 앞에 있는 요소를 제거하지 않고 반환하는 연산
4. isEmpty: 큐가 비어있는지 확인하는 연산

 

사용 사례:

• 작업 스케줄링: 프로세스나 작업을 순서대로 처리할 때 사용된다.
• 프린터 대기열: 인쇄 작업을 순서대로 인쇄한다.
• 너비 우선 탐색(BFS): 그래프 탐색에서 사용.

 

 

큐 코드

class Queue<T> {
  private items: T[] = [];

  enqueue(item: T): void {
    this.items.push(item);
  }

  dequeue(): void {
    this.items.shift();
  }

  peek(): T | undefined {
    return this.items[0];
  }

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