[자료구조] Stack과 Queue의 비교 (인터뷰 대비)

 

💡 1. Stack(스택)이란?

 

https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Stack-Queue

 

1. 스택 : Stack은 먼저 들어간 요소가 가장 나중에 나오게 되는 선입후출(LIFO, Last In First Out)의 구조를 가진 선형 자료구조이다.

 

2. 구현 : Stack을 구현할 때는, 원소를 제거해야 하는 ArrayList보다는 index를 조정하고, 초기화 하는 방식과 함께 Array를 사용하는 것이 유리하다.

 

3. 주요 연산 : 

1. push(삽입) : Stack에 새로운 item을 추가한다.
2. pop(삭제) : 가장 위에 있는 요소를 return하고, Stack에서 해당 요소를 제거한다.
3. peek(최상단 아이템 반환) : 가장 위에 있는 요소를 return 한다. pop과는 다르게 스택에서 해당 요소를 제거하지 않는다.
+ top : 가장 위에 있는 item의 인덱스를 나타낸 Stack Class의 멤버 변수이다. isEmpty(), isFull(), peek() 등을 구현할 때 사용한다.

 

4. 스택의 사용 용도 : DFS(깊이 우선 탐색) 알고리즘, 문자열 뒤집기 등을 구현할 때 Stack 자료구조를 사용할 수 있다.

 

5. 스택이 실제로 사용된 곳 : 브라우저의 '뒤로가기', ctrl + z 되돌리기 연산, Stack 메모리 등

 

💡 2. Queue(큐)란?

 

https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Stack-Queue

 

1. 큐 : Queue는 먼저 들어간 요소가 가장 나중에 나오게 되는 선입선출(FIFO, First In First Out)의 구조를 가진 선형 자료구조이다.

 

2. 구현 : Queue를 구현할 때는, item이 삭제된 후 앞으로 모든 원소를 앞당겨야 하는 Array보다는, 단순히 연결을 끊어 객체 1개만 제거하면 되는 ArrayList로 구현하는 것이 더 좋다. 

 

3. 주요 연산 : 

1. enqueue (삽입) : Queue에 새로운 item을 삽입한다.
2. dequeue (삭제) : Queue의 가장 앞에 있는 item을 큐에서 삭제하고 return한다.

 

4. 큐의 사용 용도 : BFS(너비 우선 탐색) 알고리즘 등

 

5. 큐가 실제로 사용된 곳 : 버퍼, 프린터 큐, CPU 스케줄링 Ready 큐 등

 

 

😎 출처

[링크] https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Stack-Queue ([자료구조] Stack & Queue)