Queue vs Stack
Queue는 어떤 자료구조인가요?
먼저 삽입된 요소가 먼저 삭제되는 자료구조
[꼬꼬무1] Array-Base와 List-Base의 경우 어떤 차이가 있나요?
배열로 이루어진 큐에서는 삽입 삭제를 반복하면서 front, rear에 해당하는 위치가 배열의 크기를 넘어갈 수 없어, front 이전 공간이 남아있어도 더 이상 삽입을 할 수 없습니다.
그러나 연결리스트 기반의 큐 같은 경우 계속 동적으로 연결할 수 있기 때문에 크기 제한이 없습니다.
Stack은 어떤 자료구조인가요?
먼저 삽입된 요소가 나중에 삭제되는 자료구조
Stack 두 개를 이용하여 Queue를 구현해 보세요
1. 삽입 연산이 일어나면 stack1에 계속 삽입
2-1. 삭제 연산이 일어날때 stack2가 비어있다면 stack1요소를 전부 stack2에 삽입 후 stack2.pop()
2-2. stack2가 empty가 아니라면 stack2.pop()
[꼬꼬무1] 시간복잡도는 어떻게 되는지 설명해 주세요
stack 두 개를 사용했을 때, 삽입 연산의 시간 복잡도는 똑같지만 삭제 연산 같은 경우 stack2의 상태에 따라 stack1의 요소들을 전부 이동하는 연산이 추가적으로 필요하므로 큐에 비해 더 복잡합니다.
Queue 두 개를 이용하여 Stack를 구현해 보세요
1. 삽입 연산이 일어나면 Queue1에 삽입
2. 삭제 연산이 일어나면 Queue1의 요소가 한개 남을 때까지, Queue2에 삽입하고 Queue1에 남은 것을 삭제
[꼬꼬무1] 시간복잡도는 어떻게 되는지 설명해 주세요
Queue 두 개를 사용했을 때, 삽입 연산의 시간 복잡도는 똑같지만 삭제 연산 같은 경우 n-1개의 이동이 필요하기 때문에 stack에 비해 더 복잡합니다.
Queue vs Priority Queue를 비교하여 설명해 주세요
먼저 삽입된 요소가 먼저 삭제되는 Queue와 다르게 Priority Queue는 우선순위가 가장 높은 것을 먼저 삭제합니다. 주로 heap을 통해 구현하며 삽입, 삭제 시간복잡도가 O(log n)이라는 특징이 있습니다.
- Prefix, Infix, Postfix 에 대해 설명하고, 이를 스택을 활용해서 계산/하는 방법에 대해 설명해 주세요.
Infix (중위 표기법): 일반적으로 우리가 흔히 사용하는 수식 표기 방법입니다. 연산자가 피연산자 사이에 위치하는 형태입니다. 예를 들면 "2 + 3 * 4"와 같은 형태가 있습니다.
Prefix (전위 표기법): 연산자가 피연산자 앞에 위치하는 표기 방법입니다. 예를 들면 "+ 2 * 3 4"와 같은 형태가 있습니다.
Postfix (후위 표기법): 연산자가 피연산자 뒤에 위치하는 표기 방법입니다. 예를 들면 "2 3 4 * +"와 같은 형태가 있습니다.
1. 피연산자를 만나면 스택에 저장합니다.
2. 연산자를 만나면 스택에서 필요한 개수의 피연산자를 꺼내 연산을 수행한 후, 결과를 다시 스택에 저장합니다.
- Deque는 어떻게 구현할 수 있을까요?
Deque(double-ended queue)는 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조입니다
연결 리스트를 사용하여 Deque를 구현할 수 있습니다. 연결 리스트의 각 노드는 데이터와 다음 노드, 이전 노드를 가리키는 포인터로 구성됩니다. 노드를 생성한 뒤 요청에 맞게 리스트를 연결하여 Deque를 구현합니다.