Stack 과 Queue 에 대해서 배우거든

Stack 이랑 Queue 는 전부, 자료를 어떻게 담아두고, 꺼낼까에 대한 내용이라,

기본적으로, 내가 원하는 데이터를 "넣는다" 와

해당 구조에서 데이터를 "빼낸다" 가 있어야 함.

이제 넣고 나서, 이 데이터가 어떻게 나오는지가 Stack 과 Queue 의 차이인데

Stack 은 먼저 넣은 데이터가 나중에 나옴.

우리가 흔히 스택 쌓는다고 하잖아

그거 그대로임

그래서 아래쪽부터 차근차근 쌓아나간다고 생각하면 됨

반대로 Queue 는 큐 잡는다 라는 말을 쓰잖아

이건 먼저 잡으려고 했던 사람이 먼저 잡혀야겠지?

그래서 먼저 들어온게 먼저 나감

그림으로 표현하면 이 정도쯤 됨.

원본

그래서 Queue 에 자료를 넣는다 는 "enqueue"

자료를 뺀다는 "dequeue"

Stack 에 자료를 넣는건 "push"

빼는건 "pop"

스택은 마지막 원소를 빼는 것이기 때문에

python list 의 함수중에 원소를 삭제하는 함수의 이름이 pop 이고

아무런 파라미터를 넣지 않는다면 pop 은 마지막 원소를 지우는건 여기서 유래된 것! 

이 간단한 이야기를 하려고 이 글을 썼냐?

그렇긴 한데,

Stack 과 Queue 는 자료가 빠지는 위치가 다름

Stack 은 마지막에서 빼면 되고

Queue 는 처음에서 빼야함

그렇기 때문에 Stack 은 list 를 사용해서 구현해도 큰 문제는 없음

기껏해야 데이터가 꽉 차면 list의 크기를 확장해서 값을 전부 복사해야하는 문제가 있을 뿐이고. （물론 이거도 좀 클 수 있어서 사실 linked list 로 구현하는게 속도면에서 유리할 수 있음）

하지만 Queue 는 이렇게 구현하면 자료를 빼고나서 모든 자료를 옮기는 과정이 필요하거나,

아니면 시작하는 인덱스를 옮겨서 시간복잡도는 줄일 수 있지만

안 쓰는 공간이 늘어나는 형태로 구현해야 해서 굉장히 낭비가 심해짐

그래서 list 로 구현하는 경우보단 linked list 형태로 구현하게 됨.

linked list 형태로 구현하면 random access 가 안된다와, 검색이 오래 걸린다는 단점이 있지만 그건 queue 의 사용 목적과는 맞지 않아서 무시 해도 괜찮음.

여기서 조금 더 나가면, 쟤네들을 어떻게 더 빠르게 / 효율적으로 구현 할 수 있을까와,

Queue 와 Stack 양쪽 모두의 형태로 사용 할 수 있는 일반화된 자료구조에 대한 이야기도 할 수 있을텐데

그건 다음 시간에 （안 할수도 있음）