两个队实现栈

  我们知道队的特点是先进先出，元素只能从队的尾部进入，只能从队的尾部出来；栈的特点是先进先出，先进栈的元素被压入栈底，后进入的元素覆在栈顶，出栈时也只能从栈的顶部出来。所以我们要借用两个队来实现栈的功能，先不用栈自身的属性却可以实现栈的属性。（队用链表来实现）

  现有两个队，我们将他们分别记为Qin，Qout，开始是将元素插入到Qin中，然后将将除了队尾的元素全部保存到Qout中，保存的过程中依次将这些元素Pop掉，最后Qin中就只剩下开始时队尾的那个元素，现在又将Qout中的元素取出来存到Qin中，这是Qin中的元素顺序就改变了，开始的队尾元素变成了队头元素其它的顺序暂时不变，将Qin队头元素再将其Pop掉就可以了，一次类推就可以实现了栈的后进先出的功能。

（Queue.h）

class Node

{

public:

Node(const T& data) :_next(NULL), _data(data)

{}

Node<T>* _next;

T _data;

};

template <typename T>

class Queue

{

public:

Queue(Node<T>* head=NULL) :_head(head), _tail(NULL)

{

}

~Queue()

{

if (Empty())

{

Node<T>* cur = _head;

while (cur)

{

Node<T>* del;

del = cur;

cur = cur->_next;

delete del;

del = NULL;

}

_head = NULL;

_tail = NULL;

}

}

Queue(const Queue<T>& q)

{

Node<T>* cur = q._head;

while (cur)

{

Push(cur->_data);

cur = cur->_next;

}

}

Queue<T>& operator=(const Queue<T>& q)

{

if (this != &q)

{

delete _head;

_head = NULL;

Node<T>* cur = q._head;

while (cur)

{

Push(cur->_data);

cur = cur->_next;

}

}

return *this;

}

void Push(const T& d)

{

Node<T>* newNode = new Node<T> (d);

if (_head == NULL)

{

_head = newNode;

_tail = newNode;

}

else//实际是尾插

{

_tail->_next=newNode;

_tail = newNode;

}

}

void Pop()//头部删除

{

if (Empty())

{

if (_head == _tail)//一个节点

{

delete _head;

_head = NULL;

_tail = NULL;

}

else//多个节点

{

Node<T>* del = _head;

_head = _head->_next;

delete del;

del = NULL;

}

}

}

T& Back()

{

if (Empty())

{

return _tail->_data;

}

}

T& Front()

{

if (Empty())

{

return _head->_data;

}

}

bool Empty()

{

return _head != NULL;

}

size_t Size()

{

Node<T>* cur = _head;

size_t count = 0;

while (cur)

{

cur = cur->_next;

count++;

}

return count;

}

private:

Node<T>* _head;

Node<T>* _tail;

};

/*******************************************/

（Stack.h）

class Stack

{

public:

Stack()

{

}

~Stack()

{

}

Stack(const Stack<T>& s)

{

}

void Push(T d)

{

Qin.Push(d);

}

bool Empty()

{

return Qin.Empty();

}

void Pop()

{

if (Empty())

{

Qin.Pop();

}

}

T& Top()

{

if (Empty())

{

Swap();

T ret = Qin.Front();

return ret;

}

}

void Swap()//对两个队进行改变

{

while (Qin.Size() > 1)

{

Qout.Push(Qin.Front());

Qin.Pop();

}

while (Qout.Empty())

{

Qin.Push(Qout.Front());

Qout.Pop();

}

}

private:

Queue<T> Qin;//最开始将元素放在Qin中

Queue<T> Qout;//桥梁作用，用于改变Qin保存元素的工具

};

/************************************/

void test()//输出检验

{

Stack<int> s1;

s1.Push(1);

s1.Push(3);

s1.Push(5);

s1.Push(7);

cout << s1.Top() << endl;

s1.Pop();

cout << s1.Top() << endl;

s1.Pop(); 

cout << s1.Top() << endl;

s1.Pop(); 

cout << s1.Top() << endl;

s1.Pop();

}