数据结构代码整理_队列Queue(C++)

所谓队列，就是先进先出规则的实现。

基于链表实现

main.cpp

#include<iostream>
#include"Queue.h"
using namespace std;
int main()
{
	Queue q;
	q.append(1);
	q.append(2);
	Queue_entry a;
	q.retrieve(a);
	cout << a << "  " <<q.empty();
	return 0;
}

Node.h

#pragma once
typedef int Node_entry;
struct Node {
    //  data members
    Node_entry entry;
    Node* next;
    //  constructors
    Node();
    Node(Node_entry item, Node* add_on = nullptr);
};
Node::Node()
{
    next = nullptr;
}


Node::Node(Node_entry item, Node* add_on)
{
    entry = item;
    next = add_on;
}

Queue.h

#pragma once
#include"Node.h"
enum Error_code {
    success, fail, range_error, underflow,
    overflow, fatal, not_present, duplicate_error,
    entry_inserted, entry_found, internal_error
};
typedef int Queue_entry;
class Queue {
public:
    //  standard Queue methods
    Queue();
    bool empty() const { return front == nullptr; };
    Error_code append(const Queue_entry& item);
    Error_code serve();
    Error_code retrieve(Queue_entry& item) const;
    //  safety features for linked structures
    ~Queue() {};
    Queue(const Queue& original) {};
    void operator =(const Queue& original) {};
protected:
    Node* front, * rear;
};

Queue::Queue()
/*
Post: The Queue is initialized to be empty.
*/
{
    front = rear = nullptr;
}


Error_code Queue::append(const Queue_entry& item)
/*
Post: Add item to the rear of the Queue and return a code of success
      or return a code of overflow if dynamic memory is exhausted.
*/
{
    Node* new_rear = new Node(item);
    if (new_rear == nullptr)
        return overflow;
    if (rear == nullptr)
        front = rear = new_rear;
    else {
        rear->next = new_rear;
        rear = new_rear;
    }
    return success;
}
Error_code Queue::serve()//删除队头
/*
Post: The front of the Queue is removed.  If the Queue
      is empty, return an Error_code of underflow.
*/
{
    if (front == nullptr)
        return underflow;
    Node* old_front = front;
    front = old_front->next;
    if (front == nullptr)
        rear = nullptr;
    delete old_front;
    return success;
}
Error_code Queue::retrieve(Queue_entry& item) const {
    if (front)
    {
        item = front->entry;
        return success;
    }
    else
        return underflow;

}

基于数组实现

main.cpp

#include<iostream>
using namespace std;
#include"Queue.h"
int main()
{
	Queue q;
	q.append('a');
	q.serve();//删队头
	q.append('b');
	q.serve();
	q.append('c');
	q.append('d');
	q.serve();
	char temp;
	q.retrieve(temp);
	cout << temp;
	return 0;
}

Queue.h

#pragma once
enum Error_code {
    success, fail, range_error, underflow, overflow, fatal,
    not_present, duplicate_error, entry_inserted, entry_found,
    internal_error
};
const int maxqueue = 10; //  small value for testing
typedef char Queue_entry; // The program will use stacks with float entries. 
class Queue {
public:
    Queue();
    bool empty() const;
    Error_code serve();
    Error_code append(const Queue_entry& item);
    Error_code retrieve(Queue_entry& item) const;

protected:
    int count;
    int front, rear;
    Queue_entry entry[maxqueue];
};
class Extended_queue : public Queue {
public:
    bool full() const;
    int size() const;
    void clear();
    Error_code serve_and_retrieve(Queue_entry& item);
};

Queue::Queue()
/*
Post: The Queue is initialized to be empty.
*/
{
    count = 0;
    rear = maxqueue - 1;
    front = 0;
}


bool Queue::empty() const
/*
Post: Return true if the Queue is empty, otherwise return false.
*/
{
    return count == 0;
}


Error_code Queue::append(const Queue_entry& item)//尾插
/*
Post: item is added to the rear of the Queue. If the Queue is full
return an Error_code of overflow and leave the Queue unchanged.
*/

{
    if (count >= maxqueue) return overflow;
    count++;
    rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1);
    entry[rear] = item;
    return success;
}


Error_code Queue::serve()//删掉队头
/*
Post: The front of the Queue is removed. If the Queue
is empty return an Error_code of underflow.
*/

{
    if (count <= 0) return underflow;
    count--;
    front = ((front + 1) == maxqueue) ? 0 : (front + 1);
    return success;
}


Error_code Queue::retrieve(Queue_entry& item) const//返回队头
/*
Post: The front of the Queue retrieved to the output
      parameter item. If the Queue is empty return an Error_code of underflow.
*/

{
    if (count <= 0) return underflow;
    item = entry[front];
    return success;
}


int Extended_queue::size() const
/*
Post:   Return the number of entries in the Extended_queue.
*/
{
    return count;
}