선형 구조 - 스택, 큐

스택(Stack)

선형 구조중 하나로 Last In First Out(LIFO)의 특징을 갖음.

입력(push)과 출력(pop)이 한쪽(top)에서만 일어남

Top 포인터 : 가장 위에 있는 자료를 가르키는 포인터, 삽입&삭제시 이용

 

스택이 꽉차면 더이상 삽입할 수 없음 -> OverFlow

스택이 비게되면 더이상 삭제할 수 없음 -> UnderFlow

 

검색시 : O(n)

삽입, 삭제시 : O(1)

큐(Queue)

선형 구조중 하나로 First In First Out(FIFO)의 특징을 갖음.

한쪽[rear]에서는 입력(enqueue), 한쪽[front]에서는 출력(dequeue)이 일어남

Front 포인터 : 가장 먼저 삽입된 자료를 가리키는 포인터, 삭제시 이용

Rear 포인터 : 가장 마지막에 삽입된 자료를 가리키는 포인터, 삽입시 이용

 

검색시 : O(n)

삽입, 삭제시 : O(1)