스택 & 큐

[fjiyt]

스택과 큐에 대한 설명

• 스택 : 후입선출(가장 먼저 들어간게 가장 먼저 나감)
• 큐 : 선입선출

[summeree22]

일반큐가 있고 원형큐가 있는데, 원형 큐가 왜 나오게 됐는지?

• 배열로큐를 구현했을 때 예시인걸로 알고 있는데, 프론트 변수와 레어의 변수를 선언하고 삽입과 삭제할 때 프론트는 1씩 증가, 레어는 1씩 감소하는 과정을 진행하게 되면 그둘이 같아지는 시점이 있는데 비워졌있음에도 불구하고 채워지지 않을 때가 있음 -> 이걸 개선하기 위해 나온 것으로 알고 있다

[summeree22]

동적 배열 스택

• MAZ_SIZE에 구애받지 않은 = 최대 크기가 없는 스택
• 스택이 가득찼을 때 자동으로 배열의 길이를 현재보다 2배로 확장되는 스택

[fjiyt]

스택과 큐를 구현할 수 있는 방법

• 스택 : 맨뒤를 가리키는 포인터를 이용해서 만들 수 있다.
• 큐 : rear, front 포인터를 이용해서 만들 수 있다.

이때 시간복잡도는?

• 스택 : 배열 삽입삭제여서 O(n)
• 큐 : 배열 삽입삭제여서 O(n)

기존 스택,큐의 시간복잡도를 유지하면서 배열로 스택,큐를 구현할수있을까요?

• 큐는 rear, front 포인터를 이용해서
• 스택도 front 포인터를 이용해서

스택 2개로 큐를 만드는 방법

• 하나의 스택은 삽입을 하고 두번째 스택은 pop을 할때 사용해서 구현할 수 있다.

이렇게 만든 큐의 시간복잡도는?

• 삽입 : O(1) -> 하나의 스택에 삽입하면 돼서
• 삭제 : O(n) -> 첫번째 스택에서 두번째 스택으로 옮기는 작업이 필요하기 때문이다

[summeree22]

피드백

• 모르는 거 나와도 당황하시지 않고 문제를 포기하지 않으려는 모습이 보임
• 원래 알고있던 지식을 활용하여 답변 하시는게 문제 풀이 능력이 좋아 보여요 !!