Stack

Stack이란?

스택은 한쪽 끝에서만 데이터의 탐색, 삽입, 삭제가 발생하는 LIFO 구조를 가진 자료구조입니다. 이를 위해 스택은 마지막으로 들어간 데이터를 가리키는 Top 변수를 갖고 있습니다. 스택은 웹 브라우저 방문 기록, Undo 기능 등을 구현하는데 사용됩니다.

LIFO 방식

• Last In First Out
• 마지막으로 들어간 데이터가 가장 먼저 나오는 구조

Stack Operation

스택의 탐색 연산은 스택의 Top, 즉 마지막으로 들어간 데이터를 반환하는 연산이며 Top 변수를 유지하고 있기 때문에 O(1) 시간복잡도를 갖습니다. 스택은 마지막으로 들어간 데이터에만 접근하도록 설계된 자료구조이므로 Random Access를 지원하지 않습니다.

스택의 삽입 연산은 스택의 Top 위에 데이터를 넣는 연산이며 Top 변수를 유지하고 있기 때문에 O(1) 시간복잡도를 갖습니다.

스택의 삭제 연산은 스택의 Top에 위치한 데이터를 삭제하는 연산이며 Top 변수를 유지하고 있기 때문에 O(1) 시간복잡도를 갖습니다.

Queue

Queue란?

큐는 한쪽 끝에서는 탐색과 삭제가, 다른 한쪽 끝에서는 삽입이 발생하는 FIFO 구조를 가진 자료구조입니다. 이를 위해 큐는 가장 먼저 들어간 데이터를 가리키는 Front 변수와 마지막으로 들어간 데이터를 가리키는 Rear (= Back )변수를 갖고 있습니다.

FIFO

• First In First Out
• 가장 먼저 들어간 데이터가 가장 먼저 나오는 구조

Queue Operation

큐의 탐색 연산은 큐의 Front, 즉 가장 먼저 들어간 데이터를 반환하는 연산이며 Front 변수를 유지하고 있기 때문에 O(1) 의 시간복잡도를 갖습니다. 큐도 스택과 마찬가지로 Random Access를 지원하지 않습니다.

큐의 삽입 연산은 큐의 Rear 뒤에 데이터를 넣는 연산이며 Rear 변수를 유지하고 있기 때문에 O(1) 의 시간복잡도를 갖습니다.

큐의 삭제 연산은 큐의 Front에 위치한 데이터를 삭제하는 연산이며 Front 변수를 유지하고 있기 때문에 O(1) 의 시간복잡도를 갖습니다.

Deque

Deque이란?

덱은 양쪽 끝에서 탐색, 삽입, 삭제 모두 발생하는 Double-Ended Queue입니다. 이를 위해 덱은 가장 먼저 들어간 데이터를 가리키는 Front 변수와 마지막으로 들어간 데이터를 가리키는 Rear (= Back )변수를 갖고 있습니다.

Deque Operation

덱의 탐색 연산은 덱의 Front와 Rear의 데이터를 반환하는 연산이며 Front 변수와 Rear 변수를 유지하고 있기 때문에 O(1) 의 시간복잡도를 갖습니다.

덱의 삽입 연산은 덱의 Front 앞 혹은 Rear 뒤에 데이터를 넣는 연산이며 Front 변수와 Rear 변수를 유지하고 있기 때문에 O(1) 의 시간복잡도를 갖습니다.

덱의 삭제 연산은 덱의 Front 혹은 Rear에 위치한 데이터를 삭제하는 연산이며 Front 변수와 Rear 변수를 유지하고 있기 때문에 O(1) 의 시간복잡도를 갖습니다.