队列是一种先进先出的数据结构,元素只能添加到队尾,而对元素的删除,修改,检索只能在队头进行。与栈的差异是很明显的。同样队列的实现可以基于链表,也可以基于数组。和栈的基本操作差不多,但队列多了一个指针(标号)指向末尾的元素,因为需要在末尾插入元素。
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
template <class T> class queue
{
public:
queue();
~queue();
bool enqueue(const T &element);
T dequeue();
T peer();
int getsize();
bool isempty();
struct node
{
T data;
node * next;
};
private:
int sizes;
node * head;
node * tail;
};
template <class T> queue<T>::queue()
{
head=tail=NULL;
sizes=0;
}
template <class T> queue<T>::~queue()
{
node *temp;
while (head!=NULL)
{
temp=head;
head=head->next;
delete temp;
}
sizes=0;
}
template <class T> bool queue<T>::enqueue(const T &element)
{
node *te=new node;
te->data=element;
te->next=NULL;
if (head==NULL)
{
head=te;
tail=te;
}
else
{
tail->next=te;
tail=te;
}
sizes++;
return true;
}
template<class T> T queue<T>::dequeue()
{
T element;
node *temp=new node;
if(head==NULL)
return -1;
else
{
temp=head;
element=temp->data;
head=head->next;
delete temp;
return element;
sizes--;
}
}
template <class T> T queue<T>::peer()
{
return head->data;
}
template <class T> int queue<T>::getsize()
{
return sizes;
}
template <class T> bool queue<T>::isempty()
{
return head==NULL;
}
#endif
#include "queue.h"
using namespace std;
const int size=10;
void main()
{
queue<int> q;
q.enqueue(5);
q.enqueue(9);
q.enqueue(100);
q.enqueue(6);
q.enqueue(8);
while(!q.isempty())
{
std::cout<<q.peer()<<std::endl;
q.dequeue();
}
}
当队列为空的时候,头尾指针指向NULL;插入第一个元素的时候,要把head头指针和尾指针指向它,之后就不断移动尾指针就可以,出列的时候,要判断数组是否为空,为空就返回,在实现当中,是以头指针是否为空来判断的。
#ifndef ARRAY_QUEUE_H
#define ARRAY_QUEUE_H
#include <iostream>
template <class T> class queue
{
public:
queue();
queue(int size);
~queue();
bool enqueue(const T &element);
T dequeue();
T peer();
bool isempty();
bool isfull();
int getsize();
private:
int sizes;
int head;
int tail;
T *value;
int count;
};
template <class T> queue<T>::queue()
{
head=tail=0;
sizes=10;
value=new T[sizes];
count=0;
}
template <class T> queue<T>::queue(int size)
{
head=tail=0;
sizes=size;
value=new T[sizes];
count=0;
}
template <class T> queue<T>::~queue()
{
delete [] value;
}
template <class T> bool queue<T>::enqueue(const T &element)
{
if (isfull())
{
std::cout<<"dequeue is full"<<endl;
return false;
}
else
{
value[tail]=element;
tail++;
tail%=sizes;
count++;
return true;
}
}
template<class T> T queue<T>::dequeue()
{
T element;
if (head!=tail)
{
element=value[head];
head++;
head%=sizes;
count--;
return element;
}
else
return -1;
}
template <class T> T queue<T>::peer()
{
return value[head];
}
template <class T> bool queue<T>::isempty()
{
return head==tail;
}
template <class T> bool queue<T>::isfull()
{
return head==(tail+1)%sizes;
}
template <class T> int queue<T>::getsize()
{
return count;
}
#endif
主函数
#include "array_queue.h"
using namespace std;
const int size=4;
void main()
{
queue<int> q(size);
q.enqueue(5);
q.enqueue(9);
q.enqueue(100);
q.enqueue(6);
q.dequeue();
q.enqueue(8);
while(!q.isempty())
{
std::cout<<q.peer()<<std::endl;
q.dequeue();
//std::cout<<q.getsize()<<std::endl;
}
}
数组实现时,采用的是循环数组,head指向第一个元素,而tail指向最后一个元素的下一个位置。所以一个N长的数组,最多只能存储n-1个数,如果存储N个数的话就无法判断满和空的状态。
用两个栈实现队列,是要实现队列的enqueue,dequeue。首先是 enqueue,两个栈都是空的,先入栈s1,要出队列了怎么办,栈添加元素是不断向上增长的,最先进的元素在最底下,而队列要求最先进的先出,所以只能出栈元素,并放入另一个栈s2中,这时顺序又恢复了,底下的变成上面的了,出栈第一个元素即可(或者在放入是不放入最后一个,直接返回元素),第一次这样,第二次呢?就直接从这个s2出栈。于是往一个栈中入队元素,另一个出队,直到为空后,在从入队的那个栈中取元素。
#include "stack.h"
stack<int> s1;
stack<int> s2;
void enqueue(int q)
{
s1.push(q);
}
int dequeue()
{
if (s2.isempty())
{
int s1size=s1.getsize();
for (int i=0;i<(s1size-1);i++)
{
s2.push(s1.pop());
}
return s1.pop();
}
else
return s2.pop();
}
int main()
{
enqueue(5);
enqueue(9);
enqueue(10);
dequeue();
enqueue(6);
enqueue(8);
int i=0;
while(i<4)
{
std::cout<<dequeue()<<std::endl;
i++;
}
}
用两个队列来实现一个栈,只要也是实现栈的push和pop操作,先push,不管怎样,往一个队列里面入队元素,要出栈了怎么办,在队列里是不断往队尾加元素,出是从队头出,幸好这里有两个队列,让之前那个队列的元素不断出队,到最后一个元素时输出,刚好实现了最后来的最先出。这样入队时总是往非空的队列里入,输出时,把非空的倒腾到空,输出最后一个。
#include "array_queue.h"
using namespace std;
const int size=10;
queue<int> q1(size);
queue<int> q2(size);
void push(int s)
{
if (!q1.isempty())//输入到非空队列,空队列用于出栈时用
q1.enqueue(s);
else
q2.enqueue(s);
}
int pop()
{
if (q1.isempty())
{
int q2size=q2.getsize();//出栈时,先把非空入队到空的,除了最后一个返回外。这里不能写成i<(q2.getsize()-1),因为每次循环后q2的size都变化的for (int i=0;i<(q2size-1);i++)
{
q1.enqueue(q2.dequeue());
}
return q2.dequeue();
}
else
{
int q1size=q1.getsize();
for (int i=0;i<(q1size-1);i++)
{
q2.enqueue(q1.dequeue());
}
return q1.dequeue();
}
}
void main()
{
push(5);
push(9);
push(10);
push(6);
push(8);
int i=0;
while(i<6)
{
std::cout<<pop()<<std::endl;
i++;
}
}
基本数据结构-队列的实现及其运用,布布扣,bubuko.com
原文:http://www.cnblogs.com/dawnminghuang/p/3905721.html