데이터 구조 면접 의 4 - 대열 의 흔 한 조작
제목: 는 관련 연습 문제 가 있 지만 생각 이 상대 적 으로 뚜렷 하지 않 고 조판 에 오류 가 있 습 니 다. 저 자 는 이에 대해 관련 서적 과 자신의 관점 을 참고 하여 재 작성 하여 여러분 께 참고 하도록 하 였 습 니 다.
4. 대열 의 기본 조작
1. 배열 로 대기 열 구성
대열 은 바로 선진 적 인 선 출 을 만족 시 키 는 링크 이다.배열 로 저장 하면 대기 열 헤드 front 스 택 을 만족 시 키 고 대기 열 끝 rear 가 스 택 에 들 어가 야 합 니 다.배열 에 있어 서 rear 와 front 는 배열 의 머리 와 끝 을 대표 할 수 있다.간단하게 rear 와 front 의 크기 를 max Size 와 0 으로 고정 할 수 없습니다. 중간 요소 가 비어 있 을 수 있 기 때 문 입 니 다.따라서 배열 대기 열 에 있어 서 고리 식 저장 소 라 고 상상 할 수 있 습 니 다. 매번 가입 후 rear + 1, 매번 출전 후 front + 1 이기 때 문 입 니 다.이것 은 front 와 rear 의 크기 를 조절 해 야 합 니 다. 매번 수정 할 때마다 front = (front + 1)% maxSize, rear = (rear + 1)% maxSize 만 만족 시 키 면 요 구 를 만족 시 킬 수 있 습 니 다.
마찬가지 로 주의해 야 합 니 다. 입대 작업 전에 대기 열 이 가득 찼 는 지 여 부 를 먼저 판정 합 니 다.팀 을 나 가기 전에 대기 열 이 비어 있 는 지 여 부 를 먼저 판정 합 니 다.
template<typename Type>
class arrQueue
{
public:
arrQueue(intnSize=100);
~arrQueue();
arrQueue(constarrQueue<Type>& copyQueue);
arrQueue&operator=(const arrQueue<Type>& otherQueue);
voidinitializeQueue();
void destroyQueue();
bool isQueueEmpty();
bool isQueueFull();
void addQueue(constType& item);
void deQueue(Type&deletedItem);
private:
int maxSize;
int rear;
int front;
Type* list;
};
template<typename Type>
arrQueue<Type>::arrQueue(int nSize=100)
{
if(nSize < 0)
{
nSize = 100;
list = newType[nSize];
front = 0;
rear = 0;
maxSize = 100;
}
else
{
list = newType[nSize];
front = 0;
rear = 0;
maxSize =nSize;
}
}
template<typename Type>
arrQueue<Type>::~arrQueue()
{
if(!list)
{
delete[]list; // ， delete []list;
list = NULL;
}
}
template<typename Type>
arrQueue<Type>::arrQueue(const arrQueue<Type>©Queue)
{
maxSize =copyQueue.maxSize;
front =copyQueue.front;
rear = copyQueue.rear;
list = newType[maxSize]; // , .
for( int i = 0; i <rear; i++)
{
list[i] =copyQueue.list[i];
}
}
template<typename Type>
arrQueue<Type>& arrQueue<Type>::operator=(constarrQueue<Type>& otherQueue)
{
if(this ==&otherQueue)
{
cout <<"can't copy oneSelf!" << endl;
return *this;
}
else
{
if(maxSize !=otherQueue.maxSize)
{
cout<< "The Size of two Queue are not equal!" << endl;
return*this;
}
else
{
maxSize= otherQueue.maxSize;
front =otherQueue.front;
rear =otherQueue.rear;
for( inti = 0; i < rear; i++)
{
list[i]= otherQueue.list[i];
}//endfor
return*this;
}
}//end else
}
template<typename Type>
void arrQueue<Type>::initializeQueue()
{
destroyQueue();
}
template<typename Type>
void arrQueue<Type>::destroyQueue()
{
front = 0;
rear = 0;
}
// rear==front[ ]
template<typename Type>
bool arrQueue<Type>::isQueueEmpty()
{
return (rear ==front);
}
// 1 , !
// ：1. ;
//2. rear =front 。
template<typename Type>
bool arrQueue<Type>::isQueueFull()
{
return((rear+1)%maxSize == front);
}
template<typename Type>
void arrQueue<Type>::addQueue(const Type& item)
{
if(!isQueueFull())
{
list[rear] =item;
rear =(rear+1)%maxSize;
cout << item<< " was added to Queue!" << endl;
}
else
{
cout <<"The Queue was already Full!" << endl;
}
}
template<typename Type>
void arrQueue<Type>::deQueue(Type& deletedItem)
{
if(!isQueueEmpty())
{
deletedItem =list[front];
front =(front+1)%maxSize; // !
cout <<deletedItem << " was deleted from Queue!" << endl;
}
else
{
cout <<"The Queue was already Empty!" << endl;
}
}2. 대기 열 은 링크 체인 식 저장 구 조 를 사용한다.
주의: 1) 이때 front 와 rear 는 모두 지침 이 되 었 고 front 는 머리 결점 지침 이 되 었 으 며 rear 는 꼬리 노드 의 지침 이 되 었 습 니 다.2) 이 곳 의 front 와 rear 는 링크 작업 중의 first 와 last 와 유사 합 니 다.3) 입대 실현 은 주로 대열 의 끝부분 에서 이 루어 지 므 로 rear 지침 의 방향 을 조정 해 야 한다.팀 을 나 가 는 작업 은 주로 팀 머리 에서 이 루어 지 므 로 front 지침 의 방향 을 조정 해 야 한다.
template<typename Type>
struct nodeType
{
Type info;
nodeType* link;
};
template<typename Type>
class linkedQueue
{
public:
linkedQueue();
~linkedQueue();
linkedQueue(constlinkedQueue<Type>&);
linkedQueue&operator=(const linkedQueue<Type>&);
voidinitializeQueue();
void destroyQueue();
bool isQueueEmpty()const;
bool isQueueFull()const;
void addQueue(constType& item);
void deQueue(Type&poppedItem);
void nodeCount();
private:
nodeType<Type>*rear;
nodeType<Type>*front;
int count; //
};
template<typename Type>
linkedQueue<Type>::linkedQueue()
{
count = 0;
front = NULL;
rear = NULL;
}
template<typename Type>
linkedQueue<Type>::~linkedQueue()
{
while( front != NULL )
{
nodeType<Type>*tempNode = new nodeType<Type>;
tempNode =front;
front =front->link;
deletetempNode;
}
// rear
rear = NULL;
}
template<typename Type>
linkedQueue<Type>::linkedQueue(constlinkedQueue<Type>& copyQueue)
{
if(copyQueue.front !=NULL)
{
nodeType<Type>*current;
nodeType<Type>*first;
nodeType<Type>*newNode;
front = newnodeType<Type>;
front->info= copyQueue.front->info; // top ， ！
front->link= copyQueue.front->link;
first =front; //first ...
current =copyQueue.front->link; //current copy ...
while( current!= NULL)
{
newNode= new nodeType<Type>;
newNode->link= current->link;
newNode->info= current->info;
first->link= newNode;
first =newNode;
current= current->link;
}//end while
rear = current;
count =copyQueue.count;
}//end if
else
{
front = NULL;
rear = NULL;
count = 0;
}
}
template<typename Type>
linkedQueue<Type>& linkedQueue<Type>::operator=(constlinkedQueue<Type>& otherQueue)
{
//1
if(this ==&otherQueue)
{
cout <<"Can't copy oneself!" << endl;
return *this;
}
//2
else
{
if(front !=NULL)
{
destroyQueue();
}
if(otherQueue.front!= NULL)
{
nodeType<Type>*current;
nodeType<Type>*first;
nodeType<Type>*newNode;
front =new nodeType<Type>;
front->info= otherQueue.front->info;
front->link= otherQueue.front->link;
first =front; //first ...
current= otherQueue.front->link; //current copy ...
while(current != NULL)
{
newNode= new nodeType<Type>;
newNode->link= current->link;
newNode->info= current->info;
first->link= newNode;
first= newNode;
current= current->link;
}//endwhile
rear =current;
count =otherQueue.count;
}//end if
else
{
front =NULL;
rear =NULL;
count =0;
}
return *this;
}
}
template<typename Type>
void linkedQueue<Type>::initializeQueue()
{
destroyQueue();
}
template<typename Type>
void linkedQueue<Type>::destroyQueue()
{
count = 0;
// ： !
while(front != NULL)
{
nodeType<Type>*temp = new nodeType<Type>;
temp = front;
front =front->link;
}
rear = NULL;
}
template<typename Type>
bool linkedQueue<Type>::isQueueEmpty() const
{
return (front ==NULL);
}
template<typename Type>
bool linkedQueue<Type>::isQueueFull() const // ， !
{
return false;
}
template<typename Type>
void linkedQueue<Type>::addQueue(const Type& item)
{
if(!isQueueFull())
{
nodeType<Type>*newNode = new nodeType<Type>;
newNode->info= item;
newNode->link= NULL;
if(front ==NULL)
{
front =newNode;
rear =newNode;
}
else
{
rear->link= newNode;
rear =newNode;
}
count++;
cout <<item << " was pushed!" << endl;
}
}
template<typename Type>
void linkedQueue<Type>::deQueue(Type& deletedItem)
{
if(!isQueueEmpty())
{
nodeType<Type>*temp = new nodeType<Type>;
temp = front;
deletedItem =front->info;
front =front->link;
count--;
cout <<deletedItem << " was popped!" << endl;
delete temp;
}
}
template<typename Type>
void linkedQueue<Type>::nodeCount()
{
cout <<"nodeCount = " << count << endl;
}
3. 스 택 으로 대기 열 구현
스 택 은 선진 적 인 후에 나 오 는 것 이 고 두 개의 스 택 을 사용 합 니 다. 스 택 1 이 선진 적 인 후에 나 오고 스 택 2 는 스 택 1 을 바탕 으로 선진 적 인 선 출 을 실현 할 수 있 습 니 다.
메모: 파티 에 가입 한 addtoQueue 는 스 택 1 에 요 소 를 넣 는 것 을 보증 합 니 다.그리고 파티 deQueue 에 대해 서 는 스 택 1 의 모든 요 소 를 스 택 pop 에서 내 보 낸 다음 에 모두 스 택 2 에 들 어가 마지막 으로 스 택 2 작업 을 수행 하면 됩 니 다.
#include"linkedStack.h"
template<typename Type>
class stackedQueue
{
public:
stackedQueue();
~stackedQueue();
void addQueue(Type item);
void deQueue(Type deletedItem);
bool isQueueEmpty();
bool isQueueFull();
private:
nodeType<Type>* front;
nodeType<Type>* rear;
linkedStack<Type>* firstStack;
linkedStack<Type>* secondStack;
int nodeCnt; //
};
template<typename Type>
stackedQueue<Type>::stackedQueue()
{
front = NULL;
rear = NULL;
nodeCnt = 0;
firstStack = new linkedStack<Type>;
secondStack = new linkedStack<Type>;
}
template<typename Type>
stackedQueue<Type>::~stackedQueue()
{
while(front != NULL)
{
nodeType<Type>* temp;
temp = front;
front = front->link;
}
rear = NULL;
if(firstStack != NULL)
{
delete firstStack;
firstStack = NULL;
}
if(secondStack != NULL)
{
delete secondStack;
secondStack = NULL;
}
}
template<typename Type>
voidstackedQueue<Type>::addQueue(Type item)
{
if(!isQueueFull())
{
nodeCnt++;
firstStack->push(item); // 1
cout << item << " was added toQueue!" << endl;
}
}
template<typename Type>
voidstackedQueue<Type>::deQueue(Type deletedItem)
{
if(!isQueueEmpty())
{
while(!firstStack->isStackEmpty())
{
firstStack->pop(deletedItem); // 1
if(!firstStack->isStackFull())
{
secondStack->push(deletedItem); // 2
}
}
if(!secondStack->isStackEmpty())
{
secondStack->pop(deletedItem); // 2
}
cout << deletedItem << " was out ofQueue!" << endl;
nodeCnt--;
}
}
template<typename Type>
boolstackedQueue<Type>::isQueueEmpty()
{
return (nodeCnt == 0);
}
template<typename Type>
boolstackedQueue<Type>::isQueueFull()
{
return false;
}4 절 끝.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
