两个队实现栈
我们知道队的特点是先进先出，元素只能从队的尾部进入，只能从队的尾部出来；栈的特点是先进先出，先进栈的元素被压入栈底，后进入的元素覆在栈顶，出栈时也只能从栈的顶部出来。所以我们要借用两个队来实现栈的功能，先不用栈自身的属性却可以实现栈的属性。（队用链表来实现）
创新互联建站从2013年成立，是专业互联网技术服务公司，拥有项目网站设计、网站建设网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元马尾做网站,已为上家服务,为马尾各地企业和个人服务,联系电话:18982081108
现有两个队，我们将他们分别记为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 _data;
};
template
class Queue
{
public:
Queue(Node
{
}
~Queue()
{
if (Empty())
{
Node
while (cur)
{
Node
del = cur;
cur = cur->_next;
delete del;
del = NULL;
}
_head = NULL;
_tail = NULL;
}
}
Queue(const Queue
{
Node
while (cur)
{
Push(cur->_data);
cur = cur->_next;
}
}
Queue
{
if (this != &q)
{
delete _head;
_head = NULL;
Node
while (cur)
{
Push(cur->_data);
cur = cur->_next;
}
}
return *this;
}
void Push(const T& d)
{
Node
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
_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
size_t count = 0;
while (cur)
{
cur = cur->_next;
count++;
}
return count;
}
private:
Node
Node
};
/*******************************************/
（Stack.h）
class Stack
{
public:
Stack()
{
}
~Stack()
{
}
Stack(const Stack
{
}
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
Queue
};
/************************************/
void test()//输出检验
{
Stack
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();
}
分享名称：两个队实现栈
网站路径：http://cdiso.cn/article/jgopde.html
