Data Structures(Stack, Queue, Linked List)

_Stack

push와 pop만 동작하는 배열과 같다고 보면된다.

마지막들어온게 먼저 나가는 'Last In, First Out' 

/pesudo code/

나중에 들어온것 부터 나가게 하기위한 count 변수사용

count가 높은 순으로 부터 출력

출력할때는 count변수 -1

 

_Queue

unshift, pop이 동작하는 배열(순서가 반대일경우 push와 shift)

들어온 순서대로 나가는 'First In, First Out' 

/pesudo code/

enqueue('push')
마지막부터 들어가게 하기 위해 end 변수사용
storage[end]로 추가하면서 end값 ++

dequeue('pop')
처음부터 출력하기 위해 front 변수 사용
리턴값에 value 저장후
front부터 삭제하면서 front 증가

 

_Linked List

링크드리스트는 순차적인 순서로 데이터를 저장

인덱스 대신 포인터

포인터만 바꿔주면 되기 때문에 삽입과 삭제에 있어서 'constant-time' 을 갖는다

첫번째 노드 : head / 마지막 노드 : tail

middleware 로직에 사용

/pesudo code/

첫번째 노드 : head / 마지막 노드 : tail

 

단일 링크드 리스트이면 각노드는 다음 노드를 가르키는 하나의 포인터와 값을 갖고있다

이중 링크드 리스트이면 이전의 노드와 다음의 노드를 가르키는 포인터와 값을 갖고있다