二、队列
队列是一种先进先出的数据结构，元素只能添加到队尾，而对元素的删除，修改，检索只能在队头进行。与栈的差异是很明显的。同样队列的实现可以基于链表，也可以基于数组。和栈的基本操作差不多，但队列多了一个指针（标号）指向末尾的元素，因为需要在末尾插入元素。
1.队列的链表实现
#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头指针和尾指针指向它，之后就不断移动尾指针就可以，出列的时候，要判断数组是否为空，为空就返回，在实现当中，是以头指针是否为空来判断的。
2.队列的数组实现
#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个数的话就无法判断满和空的状态。
三、栈和队列的相互实现
1.如何用两个栈实现一个队列
用两个栈实现队列，是要实现队列的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++;
}
}
2.如何用两个队列实现一个栈
用两个队列来实现一个栈，只要也是实现栈的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++;
}
}