[Data Structures] Stack & Queue

Stack

Features

• 선형 자료구조이다.
• LIFO(Last In First Out) 원칙을 따른다. 즉, 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 구조이다.
• 마지막 element를 가리키는 top 포인터가 있다.

Element Access

peek 연산을 통해 top이 가리키는 element를 반환한다. 따라서 $O(1)$이 소요된다.

Insertion & Deletion

삽입 연산인 push와 삭제 연산인 pop은 $O(1)$이 소요된다.

Queue

Features

• 선형 자료구조이다.
• FIFO(First In First Out) 원칙을 따른다. 즉, 한 쪽 끝에서는 삽입을 다른 한 쪽 끝에서는 삭제를 하는 구조이다.
• front 포인터로 가장 앞의 element를 rear 포인터로 가장 뒤의 element를 가리킨다.
• 큐가 꽉 차서 더 이상 element를 넣을 수 없는 경우를 overflow, 큐가 비어 있어 element를 꺼낼 수 없는 경우를 underflow라고 한다.

Element Access

peek 연산을 통해 front가 가리키는 element를 반환한다. 따라서 $O(1)$이 소요된다.

Insertion & Deletion

삽입 연산인 enqueue와 삭제 연산인 dequeue $O(1)$이 소요된다.

Type

Linear Queue

배열과 링크드 리스트로 구현이 가능하며 배열로 구현 시 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 element를 한 칸씩 옮겨야 한다는 단점이 있다.

Circular Queue

배열로 선형 큐를 구현할 시 큐의 삭제와 생성이 계속 일어났을 때, 배열의 마지막에 도달 후 실제로는 데이터 공간이 남아있지만 overflow가 발생하는 문제점을 보완한 것이 환형 큐이다. 모듈러 연산을 통하여front가 배열의 끝에 닿으면 다시 큐의 맨 앞부터 element를 삽입하여 원형으로 연결하는 방식이다.

Double-Ended Queue(Deque)

To be posted..

Priority Queue

힙과 함께 포스팅할 예정이다.