LeetCode 641 : 디자인 원형 데크
LeetCode의 "Design Circular Deque"에 대한 솔루션을 게시하고 있습니다. 리뷰를 원하시면 그렇게 해주세요. 감사합니다!
문제
순환 양방향 대기열 (deque)의 구현을 설계하십시오.
구현은 다음 작업을 지원해야합니다.
MyCircularDeque(k): 생성자, deque의 크기를 k로 설정합니다.insertFront(): Deque 앞에 아이템을 추가합니다. 작업이 성공하면 true를 반환합니다.insertLast(): Deque 뒤쪽에 아이템을 추가합니다. 작업이 성공하면 true를 반환합니다.deleteFront(): Deque 전면에서 항목을 삭제합니다. 작업이 성공하면 true를 반환합니다.deleteLast(): Deque 뒷면에서 항목을 삭제합니다. 작업이 성공하면 true를 반환합니다.getFront(): Deque에서 전면 항목을 가져옵니다. deque가 비어 있으면 -1을 반환합니다.getRear(): Deque에서 마지막 항목을 가져옵니다. deque가 비어 있으면 -1을 반환합니다.isEmpty(): Deque가 비어 있는지 확인합니다.isFull(): Deque가 가득 찼는 지 여부를 확인합니다.
예:
MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1); // return true
circularDeque.insertLast(2); // return true
circularDeque.insertFront(3); // return true
circularDeque.insertFront(4); // return false, the queue is full
circularDeque.getRear(); // return 2
circularDeque.isFull(); // return true
circularDeque.deleteLast(); // return true
circularDeque.insertFront(4); // return true
circularDeque.getFront(); // return 4
노트 :
- 모든 값은 [0, 1000] 범위에 있습니다.
- 작업 수는 [1, 1000] 범위입니다.
- 내장 된 Deque 라이브러리를 사용하지 마십시오.
암호:
// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
struct MyCircularDeque {
MyCircularDeque(int k): stream(k, 0), counts(0), k(k), head(k - 1), tail(0) {}
const bool insertFront(
const int value
) {
if (isFull()) {
return false;
}
stream[head] = value;
--head;
head += k;
head %= k;
++counts;
return true;
}
const bool insertLast(const int value) {
if (isFull()) {
return false;
}
stream[tail] = value;
++tail;
tail %= k;
++counts;
return true;
}
const bool deleteFront() {
if (isEmpty()) {
return false;
}
++head;
head %= k;
--counts;
return true;
}
const bool deleteLast() {
if (isEmpty()) {
return false;
}
--tail;
tail += k;
tail %= k;
--counts;
return true;
}
const int getFront() {
return isEmpty() ? -1 : stream[(head + 1) % k];
}
const int getRear() {
return isEmpty() ? -1 : stream[(tail - 1 + k) % k];
}
const bool isEmpty() {
return !counts;
}
const bool isFull() {
return counts == k;
}
private:
using ValueType = std::uint_fast16_t;
std::vector<ValueType> stream;
ValueType counts;
ValueType k;
ValueType head;
ValueType tail;
};
답변
데크 내용 과 크기 / 인덱스 (
k, count, head, tail)에 동일한 유형을 사용하는 것은 잘못된 느낌입니다. 적어도,k그리고count해야한다std::vector::size_type.당신이 양단 큐를 백업 이후
std::vector, 제작head및 외모보다 관용적.tailstd::vector::iteratork가장 설명적인 이름이 아닙니다. 고려하십시오capacity.std::vector고정 크기 데크를 백업하는 데 가장 적합한 컨테이너 인지 잘 모르겠습니다 . 결국 요점은std::vector동적 크기를 갖는 것입니다.std::array, 또는 평범한 오래된 C 스타일 배열이 더 자연스럽게 보입니다.
stream.reserve(k)생성자에서 호출 하여 벡터의 효율성을 향상시킬 수 있습니다. k요소 만 있으므로 .reserve()메모리를 미리 할당 한다는 것을 알고 있기 때문 입니다.
사용 std::size_t하는int
int k 것을 선호하는 것은std::size_t k
복사 생성 자나 복사 할당 연산자를 선언하지 않았습니다 . 이로 인해 Deque서로 할당하려는 경우 문제가 발생할 수 있습니다 .
인라인 귀하의 일부 멤버 함수 struct같은 것은 isEmpty(), getRear(), getFront() 수있는 컨테이너의 성능을 향상하지만, 공간에 대한 무역 것입니다.
챌린지를 완료하기위한 목적으로 만이 작업을 수행하는 경우 다음 부분을 무시할 수 있습니다.
템플릿
지금 deque은 std::uint_fast16_t. 하지만 내가 deque이름 을 만들고 싶다면 ? 아니면 deque다른 십진수 값? 각 데이터 유형에 대해 15 개의 클래스를 만들 수는 없습니다.
따라서 C ++에서 템플릿 을 사용하여 일반 deque .
구문은 간단합니다
template < typename T >
struct deque
{
public:
// public member functions
private:
std::vector< T > stream;
};
이제 새 데크를 만들고 싶을 때 deque<any_data_type> my_deque.
당신이 사용하는 것이 어디든지 ValueType, 당신은으로 교체 T.
C ++가하는 일은 컴파일 타임 동안 해당 데이터 유형을 취하고 any_data_type대체 한다는 것 입니다. 프로그램에이를 구현하면 C ++에서 템플릿이 작동하는 방식에 대해 많은 것을 배울 수 있으며 이는 향후 프로젝트에 도움이 될 것입니다.T
C ++의 템플릿
나는 이것이 당신의 코드에 대한 테마라고 생각합니다 : const, 당신이 그것을 넣은 곳에는 아무런 이점이 없습니다; 그리고 그것이 있어야 할 다른 곳에서 누락되었습니다. 반환 값은 스칼라이므로 표시하는 것은 말 그대로 효과가 없기 때문에 모든 단일 함수 MyCircularDeque는 const밖으로 제거 해야 const합니다. insertLast(const int value)약간 더 효과가 있지만 실제로는 중요하지 않습니다.
넣어 가장 중요한 장소 const의 CONST 다움 수정하는 것입니다 this당신을위한 get과 is방법을. 그들은 한 필요가 const추가 된 후 괄호. 이것은 메소드가 멤버를 수정하지 않는다는 약속을 등록합니다.