STACK&QUEUE

스택

입력과 출력이 한 곳(방향)으로 제한

LIFO ( Last In First Out, 후입선출): 나중에 들어온게 먼저 나감.

함수의 콜스택(Stack Trace라는 단어를 디버깅중 봤을 수도 있다. 봤다면 그게 이거다.) , 문자열 역순 출력, 연산자 후위표시법 등등에 쓰인다.

스택은 Array로 구현하는 방법과 LinkedList로 구현하는 방법 2가지가 존재한다.

Array로 구현할시 최대 사이즈가 존재하며, 가득 차면 크기를 늘리든가 해야한다.

자바,코틀린에서의 stack

코틀린에서는 Stack이라는 클래스가 존재하나, Vector을 상속받아서 구현한 클래스로, arrayList으로 구현한것과 동일하다. 따라서 Stack 클래스의 경우 메모리가 가득찰 경우 가변적으로 용량을 늘려준다. 메모리 효율을 위해서는 linkedList을 이용하는것을 추천한다.

또한 linkedList을 이용하지 않더라도, 라이브러리에서도 Deque을 이용하는 것을 권장한다고 한다.

링크드 리스트로 하는 경우, 위의 사진처럼 스택 함수와 동일하게, push pop을 진행하면 된다.

 

위의 사진처럼 push, pop, isEmpty을 동일하게 진행하고, top() 대신에 first을 사용하면 된다.

구현 코드를 까보니 둘다 Array로 구현 되어있어서 정확한 이유는 모르겠지만, DequeArray가 더 최신버젼이니 사용을 권장한다고 한다.

큐

입력과 출력을 한 쪽 끝(front, rear)으로 제한

FIFO 선입선출: 가장 먼저 들어온 것이 가장 먼저 나옴.

버퍼, 마구 입력된 것을 처리하지 못하고 있는 상황(이게 큐 아닌가?), BFS

큐는 크게 3가지 방법으로 구현이 된다.

배열 큐, 원형 큐(배열), 연결리스트 큐

일반 큐의 단점으로 빈 메모리가 남아 있어도 꽉 차있는 걸로 판단할 수도 있었고, 이를 개선한 것이 원형 큐였다.

메모리 공간은 잘 활용하나 큐의 크기가 제한되어 있고, 여전히 사용하지 않는 메모리가 존재.

이를 개선한 것이 연결리스트 큐로 삽입, 제거 모두 O(1)로 가능하다.