[자료구조] Stack & Queue

💡 Stack

선형 자료구조의 일종으로 Last In First Out (LIFO). 즉, 나중에 들어간 원소가 먼저 나온다. 이것은 Stack 의 가장 큰 특징이다. 차곡차곡 쌓이는 구조로 먼저 Stack 에 들어가게 된 원소는 맨 바닥에 깔리게 된다. 그렇기 때문에 늦게 들어간 녀석들은 그 위에 쌓이게 되고 호출 시 가장 위에 있는 녀석이 호출되는 구조이다.

💡 Queue

선형 자료구조의 일종으로 First In First Out (FIFO). 즉, 먼저 들어간 원소가 먼저 나온다. Stack 과는 반대로 먼저 들어간 놈이 맨 앞에서 대기하고 있다가 먼저 나오게 되는 구조이다. 참고로 Java Collection 에서 Queue 는 인터페이스이다. 이를 구현하고 있는 Priority queue등을 사용할 수 있다.

 

📌 stack 2개로 queue 만드는 법

: 스택 리스트를 두 개 만들어서 하나는 입력할 때 쓰는 스택, 하나는 queue에서 dequeue 할 때 사용하는 스택이다.

스택이든 큐든 push 할 때는 순서대로 들어가니 들어갈 때는 스택과 같다.

하지만 pop 할 때는 스택과 큐가 방식이 다르니 이중 스택을 이용해 큐와 같은 기능을 하게 한다.

 

https://velog.io/@lky9303/%EC%9D%B4%EC%A4%91-%EC%8A%A4%ED%83%9D%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-%ED%81%90