1. Linear

• Stack과 Queue는 Linear한 성질을 지닌 자료구조이다.

• Linear하다는 것은 다음의 특성을 가진다.

  	1. 유한하면서(finite collection)
  	2. 각 객체가 predecessor를 가지고
  	3. successor도 가지는 경우

• 자료구조에 적용한다면, 유한한 수의 선행객체와 후행객체를 가지는 객체의 모음이라고 볼 수 있다.

2. Stack

• Stack은 Last In, First Out의 특징을 가진 Linear ADT으로, 기본적으로 다음의 동작을 지원한다.

  	1. push: Stack에 데이터를 저장한다.
  	2. pop: Stack에 마지막으로 저장된 데이터를 뽑아온다(동시에 Stack에서는 제거한다).
  	3. peek/top: Stack에 마지막으로 저장된 데이터를 확인한다(제거하지 않는다).
  	4. isEmpty: Stack이 비어있는지 확인한다.
  	5. clear: Stack의 모든 데이터를 제거한다.

• 단, 탐색, index 접근, 임의의 자리에 추가 및 삭제는 지원하지 않아야 한다.

• LinkedList를 이용하여 구현하는 경우, addFront와 removeFront 동작이 항상 O(1)이기에, tail 인스턴스 없이 구현하는 것이 가장 효과적이다.

• Array를 기반으로도 구현하는 것이 가능하다. 하지만, 이 경우 Array가 가득 차면 resize를 해야하는데, 이 경우는 항상 O(n)의 시간이 소요된다.

• 결론적으로, Stack은 LinkedList를 통해 구현하는 것이 항상 O(1)을 보장하기 때문에 효과적이다.

3. Queue

• Queue는 First In, First Out의 특징을 지닌 Linear ADT이고, 다음의 동작을 지원한다.

  	1. enqueue: Queue에 데이터를 저장한다.
  	2. dequeue: Queue에 먼저 저장된 데이터를 뽑아온다(동시에 Queue에서는 제거한다).
  	3. peek/top: Queue에 먼저 저장된 데이터를 확인한다(제거하지 않는다).
  	4. isEmpty: Queueu 비어있는지 확인한다.
  	5. clear: Queue의 모든 데이터를 제거한다.

• Stack과 마찬가지로, Queue 또한 탐색, index 접근, 임의의 자리에 추가 및 삭제는 지원하지 않는다.

• LinkedList를 이용하여 구현한다면, tail에 enqueue하고, head에서 dequeue하는 것을 통해 최대의 시간 효율을 낼 수 있다. 즉, Stack과는 다르게 tail을 저장하는 LinkedList로 구현한다.

• Array를 기반으로 하는 경우, front 인스턴스와 back인스턴스를 저장하고, dequeue시 front를 바꿔주고, back은 array의 앞이 비어있다면 그곳으로 순환하는 것을 통해, resize를 하지 않는다는 가정 하에 LinkedList와 동일한 효율을 낼 수 있다.

4. 변형: Priority Queue&Dequeue

• Priority Queue는 자료구조 내부의 데이터 가운데, 가장 우선순위가 높은 데이터를 먼저 뽑아내는 자료구조이다. 즉, 내부에 저장될 데이터 객체들은 우선순위를 판별할 수 있는 방법이 있어야 한다. 구현은 LinkedList, Array 둘 중 어떤 것을 이용해도 상관없다.

• Dequeue는 Double-Ended Queue로, 자료구조의 처음과 마지막 모두에 데이터를 더하고 뺄 수 있는 자료구조이다. Array, LinkedList 모두 구현이 가능하고, LinkedList의 경우 DoublyLinkedList로 구현하면 시간 효율이 가장 좋다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xI+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.