스택(Stack)과 큐(Queue)
스택과 큐는 배열, 리스트와 달리 인덱스를 통해 데이터에 접근 할 수 없음.
원소의 삽입과 삭제를 자주 반복해야 할 경우 리스트보다 스택과 큐를 사용하는 것이 메모리 측면에서 훨씬 좋다.
길찾기 문제에서 이동할 수 있는 다음 노드를 큐에 저장할 경우 BFS, 스택에 저장할 경우 DFS
1. 스택 (Stack<T>) : LIFO (Last In First Out)
: 후입선출. 데이터를 추가할 때 탑을 쌓듯이 차곡차곡 데이터가 쌓이게 됨.
데이터를 꺼내고자 하면 가장 최근에 쌓았던 데이터를 반환 받음.
1) 삽입
: Stack.Push();
- 가장 마지막에 데이터를 추가하기 때문에 O(1)의 시간 복잡도를 가짐
- 단, 내부 배열 최대 크기에 도달했다면 두배 크기로 재할당하기 때문에 O(n)의 시간 복잡도를 가짐
2) 삭제
: Stack.Pop();
- 가장 마지막에 추가된 데이터를 반환 및 스택에서 제거
- 가장 마지막의 데이터를 제거하기 때문에 O(1)의 시간 복잡도를 가짐
- 스택에 데이터가 하나도 추가되어 있지 않은 경우 에러 발생
3) 읽기
: Stack.Peek();
- 가장 마지막에 추가된 데이터를 반환
- 가장 마지막의 데이터를 읽기 때문에 O(1)의 시간 복잡도를 가짐
- 스택에 데이터가 하나도 추가되어 있지 않은 경우 에러 발생
4) 사용 메서드
| 메서드 | 설명 |
| Push(); | 스택에 원소를 추가하는 함수 |
| Peek(); | 마지막에 추가된 데이터를 반환하는 함수 |
| Pop(); | 마지막에 추가된 데이터를 반환하고 스택에서 삭제하는 함수 |
| TryPeek(); | Peek과 같은 작업을 수행하지만 작업 성공 여부를 bool 값으로 반환 out 키워드로 받을 수 있음 |
| TryPop(); | Pop과 같은 작업을 수행하지만 작업 성공 여부를 bool 값으로 반환 out 키워드로 받을 수 있음 |
| Contains(); | 매개변수로 전달한 값이 스택에 존재하는지 여부를 bool 값으로 반환 |
| ToArray(); | 스택을 배열로 변환 |
2. 큐 (Queue<T>) : FIFO (First In First Out)
: 선입선출. 일반적인 줄서기 처럼 먼저 대기했던 데이터가 먼저 반환되는 선형자료구조
1) 삽입
: Queue.Enqueue();
- O(1)의 시간 복잡도를 가짐
- 만약 내부 배열의 크기에 도달했다면 재할당. O(n)의 시간 복잡도를 가짐
2) 삭제
: Queue.Dequeue();
- 가장 처음 추가된 데이터를 반환하고 큐에서 삭제. O(1)의 시간 복잡도를 가짐
3) 읽기
: Queue.Peek();
- 가장 처음 추가된 데이터를 반환. O(1)의 시간 복잡도를 가짐
4) 사용 메서드
| 메서드 | 설명 |
| Enqueue(); | 큐에 원소를 추가하는 함수 |
| Peek(); | 큐의 맨 앞 데이터를 반환하는 함수 |
| Dequeue(); | 큐의 맨 앞 데이터를 반환하고 큐에서 삭제하는 함수 |
| TryPeek(); | Peek과 같은 작업을 수행하지만 작업 성공 여부를 bool 값으로 반환 out 키워드로 받을 수 있음 |
| TryDequeue(); | Dequeue와 같은 작업을 수행하지만 작업 성공 여부를 bool 값으로 반환 out 키워드로 받을 수 있음 |
| Contains(); | 매개변수로 전달한 값이 큐에 존재하는지 여부를 bool 값으로 반환 |
| ToArray(); | 큐를 배열로 변환 |
** 틀린 정보가 있다면 댓글로 알려주세요 **