스택/큐(배준호 대리님)

[자료구조 목차]

 

스택의 개념

- 선형 리스트 구조의 특별한 형태로 데이터의 삽입과 삭제가 한쪽 끝(TOP)에서만 일어나는 선형 구조

- 푸쉬(PUSH)와 팝(POP)을 통해 가장 최근에 보관한 자료가 나오는 LIFO(Last In First Out) 구조

 

스택 동작방식

- 마지막에 삽입(Last-In)한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제(First-Out)되는 구조

 

스택 연산

연산	설명
top()	스택의 맨 위에 있는 데이터 값을 반환함
push()	스택에 데이터를 삽입함
pop()	스택에서 데이터를 삭제함
isempty()	스택에 원소가 없으면 'true', 있으면 'false' 값을 반환함
isfull()	스택에 원소가 없으면 'false', 있으면 'true' 값을 반환함

 

큐의 개념

- 데이터가 들어오는 위치는 가장 뒤(Rear 또는 Back)에 있고, 데이터가 나가는 위치는 가장 앞(Front)에 있어서, 먼저 들어오는 데이터가 먼저 나가게 되는 선입선출(First In First Out, FIFO)의 자료구조

 

큐의 동작방식

- Front는 데이터를 get 할 수 있는 위치를, Rear는 데이터를 put 할 수 있는 위치를 의미

 

큐의 유형

구현방안	개념도	설명
선형 큐		- 배열을 선형으로 사용하여 큐를 구현 - 삽입을 계속하기 위해서는 요소들을 이동시켜야 했으나 실제로 데이터를 옮기는 대신 전단과 후단의 위치만 관리 - 데이터의 삽입/제거가 몇 번 수행되고 나면 전단과 후단이 모두 뒤로 후퇴해서 더이상 사용할 수 없게 됨.
순환 큐 (환형 큐)		- 배열의 시작과 끝 구분이 없음 - 고성능이나, 구현은 링크드 큐에 비해 복잡
링크드 큐		- 용량에 구애받지 않고, 포인터로 연결하기 때문에 큐가 가득 차 있는지, 큐가 비어있는지 신경 쓸 필요가 없음 - 구현이 간단하나, 노드의 생성/삭제 연산 필요