队列

栈：先进先出
在队尾增加元素，在队头读取或删除元素（只支持在队尾的元素增加，和对队头元素的删、查）。

代码

下述代码实现了队列及其接口
包括增、删、查以及查看队列的大小

用顺序表实现队列

#include <iostream>
using namespace std;template<typename T>
class Queue{
private:T *data;int front;//队首int rear;//队尾后一个位置int size;int capacity;void resize();public:Queue(): data(new T[capacity]),front(0),rear(0),capacity(10){}~Queue();void enqueue(T element);T dequeue();T getFront() const;int getSize() const;};template <typename T>
void Queue<T>::resize(){int newCapacity = 2*capacity;T *newData = new T[newCapacity];for(int i = 0; i < rear; i++){newData[i] = data[i];}delete[] data;data = newData;capacity = newCapacity;
}template <typename T>
Queue<T>::~Queue(){delete[] data;
}template <typename T>
void Queue<T>::enqueue(T element){if(rear == capacity){resize();}data[rear++] = element;
}template <typename T>
T Queue<T>::dequeue(){if(front == rear){throw std::underflow_error("Queue is empty");    }return data[front++];
}template <typename T>
T Queue<T>::getFront() const{if(front == rear){throw std::underflow_error("Queue is empty");    }return data[front];
}
template <typename T>
int Queue<T>::getSize() const{return rear - front;
}int main()
{Queue<int> q;q.enqueue(10);q.enqueue(20);q.enqueue(30);q.enqueue(40);cout << q.getSize() << endl;cout << q.getFront() << endl;q.dequeue();cout << q.getSize() << endl;cout << q.getFront() << endl;return 0;}

用链表实现队列

#include <iostream>
using namespace std;template<typename T>class Queue{
private:struct Node{T data;Node *next;Node(T d):data(d),next(NULL){}};Node *front;//队首Node *rear;//队尾int size;public:Queue(): front(NULL),rear(NULL),size(0){}~Queue();void enqueue(T element);T dequeue();T getFront() const;int getSize() const;};template <typename T>
Queue<T>::~Queue(){while(front){Node *temp = front;front = front->next;delete temp;}
}template <typename T>
void Queue<T>::enqueue(T element){if(rear == NULL){rear = new Node(element);front = rear;}else{rear->next = new Node(element);rear = rear->next;}size++;
}template <typename T>
T Queue<T>::dequeue(){if(front == NULL){throw std::underflow_error("Queue is empty");    }T element = front->data;Node *temp = front;front = front->next;delete temp;size--;return element;
}template <typename T>
T Queue<T>::getFront() const{if(front == NULL){throw std::underflow_error("Queue is empty");    }T element = front->data;return element;
}
template <typename T>
int Queue<T>::getSize() const{return size;
}int main()
{Queue<int> q;q.enqueue(10);q.enqueue(20);q.enqueue(30);q.enqueue(40);cout << q.getSize() << endl;cout << q.getFront() << endl;q.dequeue();cout << q.getSize() << endl;cout << q.getFront() << endl;return 0;}

于 2024-01-28 第一次整理编写

学习时整理，不当之处烦请指正
码字不易，留个赞再走吧