자료구조 3

Stack

Stack 나중에 들어간 데이터가 제일 먼저 나오는 LIFO(Last In First Out) 구조 특정 위치(한쪽 끝)에서만 데이터를 넣거나 뺼 수 있다. Stack 연산의 시간복잡도 데이터를 추가(push) -> O(1) 데이터를 제거(pop) -> O(1) 제일 꼭대기의 데이터를 확인(top) -> O(1) Stack 응용 사례 수식의 괄호 쌍 후위 표기법 DFS Stack 구현 template class Stack { private: int* stack; int size, top; public: Stack(int size) : size(size), top(-1) { stack = new T[size]; } ~Stack() { delete stack; } // 데이터 삽입 bool Push(T da..

스택으로 큐 구현하기 / 큐로 스택 구현하기

스택과 큐의 상호 구현 면접 보면서 정말 많이 받은 질문 중 하나이다. 처음 질문받았을 때 어버버 하면서 아무것도 대답 못했던 기억이 있고 두 번째 받았을 땐 자신 있게 작성하다 틀린 기억이 있는 부끄러운 기억이 있다. 스택으로 큐 구현하기 이론은 간단하다. 2개의 스택을 이용해서 구현하면 된다. Enqueue(삽입) 그냥 첫 번째 스택인 a에 추가만 하면 된다. Dequeue(제거) 두 번째 스택인 b가 비어있지 않다면 b에 있는 값을 제거(반환) 하면 된다. 두 번째 스택인 b가 비었다면 첫 번째 스택인 a가 빌 때까지 a를 pop(제거)하면서 두 번째 스택인 b에 push(추가) 한다. class StackQueue { public: stack a; stack b; void Enqueue(int d..

Queue | 큐

Queue 먼저 들어간 데이터가 제일 먼저 나오는 FIFO(First In First Out)구조 한쪽 끝에서 데이터를 넣고 반대쪽 끝에서 원소를 제거할 수 있는 자료구조 Queue 연산의 시간복잡도 데이터를 추가(push) -> O(1) 데이터를 제거(pop) - O(1) 맨 앞 데이터를 조회(front) -> O(1) 맨 뒤 데이터를 조회(rear) -> O(1) Queue 응용 사례 대기열(영화관, 공항 ...) BFS Flood Fill Queue 구현 template class Queue { private: int* queue; int size; int head, tail; public: Queue(int qSize) : size(qSize + 1), head(0), tail(0) { queue..