대열 의 연속 과 체인 식 실현
6573 단어 대열
대기 열: 표 의 전단 에서 만 삭제 (pop) 작업 을 할 수 있 고 표 의 백 엔 드 에 삽입 (push) 작업 을 할 수 있 습 니 다. 사람들 이 줄 을 서 는 것 과 같 습 니 다.
연속 대기 열 (배열):
#include <iostream>
using namespace std;
const int queueSize = 10000;
template <class Queue_entry>
class Queue{ // Contiguous Queue
public:
Queue();
void pop(); /*pre: make sure the Queue is not empty */
Queue_entry front() const;/*pre: make sure the Queue is not empty */
Queue_entry back() const; /*pre: make sure the Queue is not empty */
bool push(const Queue_entry&);
bool empty() const;
int size() const;
private:
Queue_entry entry[queueSize];
int count;
int head;
int tail;
};
template <class Queue_entry>
Queue<Queue_entry> :: Queue(){
count = 0;
head = 0;
tail = 0;
}
template <class Queue_entry>
void Queue<Queue_entry> :: pop(){
if(count > 0){
count--;
if(count) // if queue has only one entry, then head = tail when pop a entry
head = (head-1+queueSize)%queueSize;
}
/*else underflow*/
return;
}
template <class Queue_entry>
Queue_entry Queue<Queue_entry> :: front() const{
if(count > 0){
return entry[head];
}
/* return underflow */
}
template <class Queue_entry>
Queue_entry Queue<Queue_entry> :: back() const{
if(count > 0){
return entry[tail];
}
/* return underflow */
}
template <class Queue_entry>
bool Queue<Queue_entry> :: push(const Queue_entry& newEntry){
if(count < queueSize){
if(count)// if queue is empty, then head = tail when push a entry
tail = (tail-1+queueSize)%queueSize;
++count;
entry[tail] = newEntry;
return true;
}
return false/*overflow*/;
}
template <class Queue_entry>
bool Queue<Queue_entry> :: empty() const{
return count == 0;
}
template <class Queue_entry>
int Queue<Queue_entry> :: size() const{
return count;
}
int main()
{
Queue<int> s;
for(int i = 0; i < 10; i++){s.push(10-i);}
while(!s.empty()){
cout << "size: " << s.size() << endl;
cout << "front: " << s.front() << endl;
cout << "back: " << s.back() << endl;
cout << endl;
s.pop();
}
return 0;
}
체인 대기 열 (링크):
#include <iostream>
using namespace std;
template <typename Node_entry>
struct Node{
Node_entry entry;
Node* next;
Node(){
next = NULL;
}
Node(const Node_entry& newEntry, Node* add_on = NULL){
entry = newEntry;
next = add_on;
}
};
template <class Queue_entry>
class Queue{ // Linked Queue
public:
Queue();
Queue(const Queue& original);
~Queue();
void pop(); /*pre: make sure the Queue is not empty */
Queue_entry front() const;/*pre: make sure the Queue is not empty */
Queue_entry back() const; /*pre: make sure the Queue is not empty */
void push(const Queue_entry&);
bool empty() const;
int size() const;
//
Queue& operator=(const Queue& original);
//
private:
Node<Queue_entry>* head;
Node<Queue_entry>* tail;
int count;
};
template <class Queue_entry>
Queue<Queue_entry> :: Queue(){
head = NULL;
tail = NULL;
count = 0;
}
template <class Queue_entry>
Queue<Queue_entry> :: Queue(const Queue& original){
count = original.count;
Node<Queue_entry> *new_copy, *original_head = original.head;
if(original_head == NULL) head = tail = NULL;
else{
head = new_copy = new Node<Queue_entry>(original_head->entry);
while(original_head->next != NULL){
original_head = original_head->next;
new_copy->next = new Node<Queue_entry>(original_head->entry);
new_copy = new_copy->next;
}
}
}
template <class Queue_entry>
Queue<Queue_entry> :: ~Queue(){
count = 0;
Node<Queue_entry>* old_node;
tail = NULL;
//cout << "test ~Queue" << endl;
while(head != NULL){
old_node = head;
// cout << old_node->entry << endl;
head = head -> next;
delete old_node;
}
}
template <class Queue_entry>
void Queue<Queue_entry> :: pop(){
if(head != NULL){
--count;
Node<Queue_entry>* old_node = head;
if(head == tail) tail = NULL; // queue only has one entry
head = head->next;
delete old_node;
}
/*else underflow*/
return;
}
template <class Queue_entry>
Queue_entry Queue<Queue_entry> :: front() const{
if(head != NULL){
return head->entry;
}
/* return underflow */
}
template <class Queue_entry>
Queue_entry Queue<Queue_entry> :: back() const{
if(tail != NULL){
return tail->entry;
}
/* return underflow */
}
template <class Queue_entry>
void Queue<Queue_entry> :: push(const Queue_entry& newEntry){
Node<Queue_entry>* new_tail = new Node<Queue_entry>(newEntry);
//if(new_head == NULL) return/*overflow*/; // the dynamic memory is exhausted
++count;
if(tail == NULL){ // queue is empty
head = tail = new_tail;
return;
}
tail->next = new_tail;
tail = new_tail;
return;
}
template <class Queue_entry>
bool Queue<Queue_entry> :: empty() const{
return count == 0;
}
template <class Queue_entry>
int Queue<Queue_entry> :: size() const{
return count;
}
template <class Queue_entry>
Queue<Queue_entry>& Queue<Queue_entry> :: operator=(const Queue<Queue_entry>& original){
count = original.count;
while(head != NULL) pop();
Node<Queue_entry> *new_copy, *original_head = original.head;
if(original_head == NULL) head = tail = NULL;
else{
head = new_copy = new Node<Queue_entry>(original_head->entry);
while(original_head->next != NULL){
original_head = original_head->next;
new_copy->next = new Node<Queue_entry>(original_head->entry);
new_copy = new_copy->next;
}
}
return *this;
}
int main()
{
{ // test ~Queue
Queue<int> s;
for(int i = 0; i < 10; i++){s.push(10-i);}
}
Queue<int> s;
for(int i = 0; i < 10; i++){s.push(10-i);}
while(!s.empty()){
cout << "size: " << s.size() << endl;
cout << "front: " << s.front() << endl;
cout << "back: " << s.back() << endl;
cout << endl;
s.pop();
}
return 0;
}