stack and queue

Stacks

선입후출 LIFO

 
구현 예시는 웹브라우저의 뒤로가기.
뒤로가기를 누르면 우리가 마지막으로 접속했던 페이지가나오고,
마지막 전에 방문한 페이지에 가려면 뒤로가기를 2번 눌러야함.
 

보통 arraylist를 사용.

마지막에 넣고 빼고 하는것은 나머지 요소들의 인덱스를 조정할 필요가 없기때문에 0(1)
나머지 prepend, push sth back같은것들은 0(n)
 


linked list로도 구현 가능
linked list 로 stack을 구현할거면 맨밑에 노드가 null을 가리키게하는게 좋다.
왜냐면 그렇게 하는게 stack에서 선입선출을 할때 시간복잡도가 떨어지기 때문이다.

맨 위의 노드가 마지막 노드가 되게하면 맨마지막노드의 전 노드를 tail로 지정하기위해 찾아야하는데 인덱스가 따로 없어 반복문을 돌려야하기 때문에 0(n)이 되지만,

맨 위의 노드가 첫번째 노드가 되면 그저 head를 head.next로 옮기면 되기 때문에 0(1) 이기 때문.

linked list의 prepend removefirst = push, pop
head, tail = top, bottom
그런데 stack에서는 선입선출이라 위에있는 것들만 건들이기 때문에 bottom은 필요없다.

Queues

FIFO 선입선출
어레이리스트로 구현한다고 하면

처음부분에 인큐, 디큐 하는것은 0(n)
끝부분에 인큐 디큐 하는 것은 0(1)
근데 큐는 선입선출이라서 한쪽에서 인큐 디큐 둘 다 할순없음
그래서 어떻게 하든 둘 중 하나는 0(n)임
 


링크드리스트

나중에 들어오는것을 tail쪽으로 붙이고(인큐)
head를 디큐하면 인큐 디큐 둘 다 0(1)시간 복잡도로 구현할 수 있음.