[Data Structure] ADT(추상적 자료형): 큐와 스택

추상적 자료형(Abstract Data Type, ADT)은 컴퓨터 과학에서 자료들과 그 자료들에 대한 연산들을 명기한 것이다.

즉, 어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 말한다.

추상적 자료형의 예로는 복소수, 리스트, 스택, 큐, 맵, 우선순위 큐, 집합 등이 있는데,

이 중, 대표적으로 큐와 스택에 대해 알아보겠다.

 

1. 큐 (Queue)

• 데이터를 집어넣을 수 있는 선형(linear) 자료형
• FIFO(First In First Out) - 먼저 집어넣은 데이터가 먼저 나옴
• 데이터를 집어 넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있음큐는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로 많이 사용됨

큐 용어

• Enqueue: 큐 맨 뒤에 데이터 추가
• Dequeue: 큐 맨 앞의 데이터 삭제
• front: 큐의 맨 앞, 데이터가 나가는 곳
• rear: 큐의 맨 뒤, 데이터가 들어오는 곳
• getfront: 큐의 맨 앞을 알려주는 것 (스택의 peek)
• empty/full: 스택이 비었는지 가득 찼는지 검사한다.
• size(level): 스택의 크기를 리턴한다.

class Queue {
  constructor() {
    this._arr = [];
  }
  enqueue(item) {
    this._arr.push(item);
  }
  dequeue() {
    return this._arr.shift();
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue(); // 1

큐의 시간 복잡도 Big O

• 삽입: Insertion O(1)
• 삭제: Deletion O(1)(dequeue)
• 검색: Search O(n)

※ 큐의 삽입은 맨 앞에서만 일어나고 삭제는 항상 맨 뒤에서만 일어나기 때문에 항상 O(1)의 시간복잡도를 가진다.

 

2. 스택 (Stack)

• 데이터를 집어넣을 수 있는 선형(linear) 자료형
• LIFO(Last In First Out) - 나중에 집어넣은 데이터가 먼저 나옴
• 데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek 등의 작업을 할 수 있음
• 스택은 서로 관계가 있는 여러 작업을 연달아 수행하면서, 이전의 작업 내용을 저장해 둘 필요가 있을 때 사용함

스택 용어

• 삽입(Push): push는 스택의 구조상 최상위에 데이터가 저장된다.
• 삭제(Pop): push와 반대로 데이터를 삭제하는 것을 pop이라고 하고, pop도 push와 마찬가지로 최상위 데이터 위치에서 삭제된다.
• 읽기(Peek): 마지막 위치(top)에 해당하는 데이터를 읽고, 이 때 top의 변화는 없다.
• empty/full: 스택이 비었는지 가득 찼는지 검사한다.
• size(level): 스택의 크기를 리턴한다.

class Stack {
  constructor() {
    this._arr = [];
  }
  push(item) {
    this._arr.push(item);
  }
  pop() {
    return this._arr.pop();
  }
  peek() {
    return this._arr[this._arr.length - 1];
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop(); // 3

스택의 시간 복잡도 Big O

• 삽입: Insertion O(1)
• 삭제: Deletion O(1)(pop)
• 검색: Search O(n)

※ 스택의 삽입과 삭제 연산은 항상 맨 위에서만 일어나기 때문에 늘 O(1)의 시간 복잡도를 가진다.

※ 하지만, 특정 데이터를 찾을 때는 그 데이터를 찾을 때까지 수행해야하기 때문에 O(n)의 시간 복잡도를 가진다.

 

+)

시간 복잡도가 이해가 안간다면? 아래 글 참고!!

https://suzzeong.tistory.com/104

시간 복잡도와 공간 복잡도

---

참고

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

https://ko.wikipedia.org/wiki/%EC%B6%94%EC%83%81_%EC%9E%90%EB%A3%8C%ED%98%95

https://coding-factory.tistory.com/602

https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90

https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90

https://bigsong.tistory.com/32

https://algoroot.tistory.com/55

https://algoroot.tistory.com/54