算法导论第10章的东西，感觉用双链表真心简单，就是有点浪费空间，但是时间复杂度O（1）：
#include <stdio.h> struct LinkNode
{
LinkNode(): m_Value(-)
, m_pPreNode(NULL)
, m_pNextNode(NULL)
{ }
int m_Value;
LinkNode* m_pPreNode;
LinkNode* m_pNextNode;
};
class Queue
{
public:
void Init()
{
m_pHeadNode = new LinkNode();
m_pHeadNode->m_pNextNode = m_pHeadNode;
m_pHeadNode->m_pPreNode = m_pHeadNode;
}
void DeEqueue()
{
if (m_pHeadNode->m_pPreNode == m_pHeadNode)
{
return ;
} LinkNode* lpNode = m_pHeadNode->m_pNextNode;
m_pHeadNode->m_pNextNode = lpNode->m_pNextNode;
lpNode->m_pNextNode->m_pPreNode = m_pHeadNode; delete lpNode;
lpNode = NULL;
}
int Tail()
{
LinkNode* lpTail = m_pHeadNode->m_pPreNode;
if (lpTail != m_pHeadNode)
{
int lTop = lpTail->m_Value;
printf("tail:%d\n",lTop);
return lTop;
}
return -;
} int Head()
{
LinkNode* lpHead = m_pHeadNode->m_pNextNode;
if (lpHead != m_pHeadNode)
{
printf("Head:%d\n",lpHead->m_Value);
return lpHead->m_Value;
}
return -;
}
void EnQueue(int aValue)
{
LinkNode* lpNewNode = new LinkNode();
lpNewNode->m_Value = aValue; LinkNode* lpNode = m_pHeadNode->m_pPreNode;
if (NULL == lpNode)
{
m_pHeadNode->m_pPreNode = lpNewNode;
lpNewNode->m_pNextNode = m_pHeadNode;
lpNewNode->m_pPreNode = m_pHeadNode;
m_pHeadNode->m_pNextNode = lpNewNode;
}
else
{
m_pHeadNode->m_pPreNode = lpNewNode;
lpNewNode->m_pNextNode = m_pHeadNode;
lpNewNode->m_pPreNode = lpNode;
lpNode->m_pNextNode = lpNewNode;
}
}
void Print()
{
LinkNode* lpNode = m_pHeadNode->m_pNextNode;
while(lpNode)
{
if (lpNode == m_pHeadNode)
{
break;
} printf("%d ",lpNode->m_Value);
lpNode = lpNode->m_pNextNode;
}
}
private:
LinkNode* m_pHeadNode;
};
int main()
{
Queue lQueue;
lQueue.Init();
lQueue.EnQueue();
lQueue.Head();
lQueue.Tail();
lQueue.EnQueue();
lQueue.Head();
lQueue.Tail();
lQueue.EnQueue();
lQueue.Head();
lQueue.Tail();
lQueue.DeEqueue();
lQueue.Head();
lQueue.Tail();
lQueue.Print();
}