마찬가지로 둘 다 선형 자료구조
Stack이란?
후입선출의 개념을 가진 선형 자료구조. (나중에 들어간 요소가 먼저 나옴)
차곡차곡 쌓이는 구조로 먼저 Stack에 들어가게 된 원소는 맨 바닥에 깔리게됨
Push,Pop의 기능을 가지며 맨 위 원소를 TOP이라고 부룸
스택 자료구조를 이용하는 가장 대표적인 것은 스택 메모리임. 스택 메모리는 함수가 호출되며 생성되는 지역 변수, 매개 변수가 저장되는 메모리 영역
(함수 실행 -> 스택 메모리에 매개변수, 지역변수, 변환 주소 값 PUSH -> 함수가 종료 -> 스택 메모리에서 POP 수행)
배열과 연결 리스트로 표현 가능
Queue란?
선입선출의 개념을 가진 선형 자료구조. (먼저 들어간 요소가 먼저 나옴)
큐의 맨 앞을 Front, 맨 뒤를 Rear라고 부르며 값을 추가하는 것을 enqueue, 빼는 것을 dequeue라고 부름
종류: 선형큐, 환형큐
배열과 연결리스트로 구현 가능하지만, shift때문에 연결 리스트로 구현하는 것이 효율적
스택과 큐의 차이점은 무엇인가요?
스택은 세로로 된 바구니와 같은 구조로 먼저 넣게 되는 자료가 마지막에 나오는 구조임. List로 구현하면 객체를 제거하는 작업이 필요하지만 Array로 구현하면 index를 줄이고 초기화만 하면 되므로, Array로 구현하는 게 좋음 DFS나 재귀에 사용됨
큐는 먼저 들어간 자료가 먼저 나오는 자료구조임. 배열로 구현하면 shift할 때 고려해야돼서 연결리스트로 구현하는 것이 좋음. 데이터가 입력시간 순서대로 처리되어야 하는 경우에 사용됨. BFS,캐시
PriorityQueue의 동작 원리가 어떻게 되나요?
우선순위큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안한 자료구조. 우선순위 큐를 구현하기 위해서 일반적으로 힙을 사용함. 힙은 완전이진트리를 통해서 구현되었기 때문에 우선순위 큐의 시간복잡도는 O(logn)임
우선순위큐는 힙이라는 자료구조를 가지고 구현함. 힙으로 구현된 이진 트리는 모든 정점이 자신의 자식 요소보다 우선순위가 높다는 성질을 가짐.
스택과 큐의 실사용 예를 들어 간단히 설명해주세요.
스택은 자바의 Stack 메모리 영역에 사용됨. 지역변수와 매개변수 데이터 값이 저장되는 공간이며, 메소드 호출 시 메모리에 push하고 종료되면 pop해서 삭제한다.
큐는 자원의 할당과 회수를 하는 스케쥴러 역할을 하는 OS의 스케줄러에서 쓰임
Prefix, Infix, Postfix 에 대해 설명하고, 이를 스택을 활용해서 계산하는 방법에 대해 설명해 주세요.
각각 순서대로 전위표기법, 중위표기법, 후위표기법임. 전위표기법은 연산자를 먼저 표기하고, 중위표기법은 두 피연산자 사이에 연산자를 표기하고, 후위표기법은 연산자를 나중에 표기하는 방법임.
중위표기법을 일반적으로 많이 사용하고 후위표기법은 컴파일러가 사용하는 것으로 스택을 사용하는 예에 가장 빈번히 등장함.
숫자를 만나면 전부 스택에 집어넣음-> 연산자가 나오면 스택에서 두수를 꺼내 계산하고 다시 스택에 집어넣음
🫠
출처: https://alreadyusedadress.tistory.com/326
https://sohyeonnn.tistory.com/19
https://dev-coco.tistory.com/159
