자료구조, 스택과 큐에 대하여.

   [스택과 큐]

1.     스택 : 스택은 탑 모양으로 생각하면 좋을 것이다. 스택은 후입선출(LIFO – Last In First Out)으로 진행된다. 즉, 데이터가 들어오면 아래부터 쌓이게 되고, 데이터가 나갈 때는 가장 최근에 들어온 데이터부터 나가게 된다.

    A.     스택의 연산

                         i.         Push : 스택에 데이터를 넣는 연산

                        ii.         Pop : 스택에서 데이터를 꺼내는 연산

                       iii.         Top : 스택의 가장 꼭대기를 가리키는 포인터

                       iv.         isEmpty : 스택이 공백인지 아닌지 확인하는 연산

                        v.         peek : Top이 가리키는 데이터를 반환

 

A, B, C가 들어있는 스택에 데이터 D 추가

데이터가 들어온 순서 : A -> B -> C -> D

 

데이터가 A -> B -> C -> D 이 순서대로 들어있는 스택이라고 할 때,

4번 Pop을 하게 되면 D -> C -> B -> A 이런 순서대로 데이터가 출력된다.

 

2.     큐(Queue) : 우리가 일반적으로 음식점에서 주문을 하기 위해 줄을 서고 있다고 가정할 때, 먼저 온 사람부터 주문 진행이 되는데 이처럼 큐는 선입선출(FIFO – First In First Out)으로 진행된다. 즉, 데이터가 들어오는 순서대로 데이터가 그대로 나가는 자료구조이다.

    A.     큐의 연산

                         i.         Enqueue : 큐에 데이터를 넣는 연산

                        ii.         Dequeue : 큐에 데이터를 꺼내는 연산

                       iii.         isEmpty : 큐가 공백인지 아닌지 확인하는 연산

                       iv.         Front : 데이터들 중 가장 먼저 들어온 데이터

                        v.         Rear : 데이터들 중 가장 마지막에 들어온 데이터

    B.      큐의 종류

종류	선형 큐	순환(원형) 큐	링크드 큐
형태	선형	원형(논리적)	노드로 연결
장점	단순 형태 구현 용이	순환형태로 지속적 사용이 가능하다	공백 혹은 포화 상태 관리가 불필요하다
단점	- 공간을 비효율적으로 사용한다. - 삽입, 삭제를 몇 번 수행 후 Rear이 후퇴되기 때문에 사용불가 되는 상황이 온다.	- Front, Rear 구분위한 방안이 필요하다	- 순환 큐에 비해 성능이 떨어진다.

 

[선형 큐 예시]

A, B, C가 들어있는 큐에 데이터 D 추가

데이터가 A -> B -> C -> D 총 4개가 들어 있는 큐에,

4번 Dequeue를 하면 A -> B -> C -> D 이 순서대로 데이터가 출력된다.