KingsamChen的废墟堆

栈（stack）和队列（queue）是最常见的线性表数据结构之一，用途十分广泛。而且可以使用数组或者链表作为其存储容器

1.栈

栈是一种先进后出（First-In-Last-Out FILO）的数据结构。数据进入栈的操作称为“压栈（Push）”，而出栈的操作称为“出栈（Pop）”。

FILO线性表的特点是：存取元素的操作只在一段进行。即：先压栈的元素必定后出栈。

就好象常见的桶装饼干，最底层的饼干一定是最先装进去的，而我们先拿出来吃的饼干，则是最后装入的。

栈的最顶部称为栈顶，压栈和出栈都在这里进行。而底部由于没有什么大用途，所以也没有赋予特定的名称

如图，是一个栈的简单示意图

栈的应用包括函数的调用以及回文识别等等。

2.栈的实现

为了方便使用，在C++中，我们设计一个CStack类，通过这个类来操作堆栈。如你所见，这个类是模板类

关于模板函数和模板类，请参见模板函数和模板类

类信息如下

template<typename T>
class CStack
{
	public:
		CStack(int nSize = 50);
		~CStack();
		void Push(const T &item);
		T Pop();
		T Peek();
		void StackClear();
		bool IsStackEmpty();

	private:
		void Expand();

	private:
		int m_nSize;
		int m_nTop;
		T *m_pList;
};

其中的Expand用于自动扩充数组空间

鉴于某些原因，只给出Push和Pop的代码示例，详细请参见SRC

//=========================================
// 输  入: item(const T&) - [in]压栈的元素
// 输  出: -
// 功  能: 将元素压入栈中
//=========================================
template<typename T>
void CStack<T>::Push(const T &item)
{
	// 扩充数组
	if ((m_nSize - 1) == m_nTop)
	{
		Expand();
	}

	m_pList[++m_nTop] = item;
}

//=========================================
// 输  入: -
// 输  出: T - 弹出的元素
// 功  能: 将元素弹出栈
//=========================================
template<typename T>
T CStack<T>::Pop()
{
	T temp;

	if (IsStackEmpty())
	{
		_terr<<_T("Cannot pop from a empty stack! And the operation was aborted")<<endl;
		return 0;
	}

	// 出栈
	temp = m_pList[m_nTop];
	--m_nTop;

	return temp;
}

3.队列

和栈不同，队列是一种FIFO（First-In-First-Out）的线性表数据结构。元素进入队列称为“入队（Enqueue）”，离开队列称为“出队（Dequeue）”

FIFO线性表的特点在于，入队在队列尾部完成，出队在队列头部完成。即：最先入队的元素必定最先出队

就像平常的排队，先来先得，后来的只能排到队伍后边，而且你不用担心插队情况的发生

如图是一个队列的简要示意图

但是直接这样的Enq和Deq操作会产生一个存储空间的问题

经过几次Deq操作，队首开始往后偏移，而Enq操作只能在队尾进行，这就使得前部分多出来的空间被浪费了

曾经有人提议，可以在每次Deq操作之后，将元素“拨回”原来的位置。

这个方法听上去不错，但是每次拨乱反正，都需要对元素逐一拷贝，操作时间是O(n)，这显然是无法接受的。

后来，scientists为了不至于导致内牛满面的结果，很天才的想到了一个方法：在思维中把这张表卷起来，首尾相接，形成一个循环队列

这样，问题就得到解决了

4.队列实现

由于我们使用了循环队列，使得Enq和Deq操作需要做一些小小的改动

队列头尾位置的计算公式如下

rear = (rear + 1) % size
front = (front +1) % size

考虑到%操作比较耗时间，如果你希望提高这点效率的话，可以使用下面的代码

	if (++m_nRear == m_nSize)
	{
		m_nRear = 0;
	}

	if (m_nFront + 1 == m_nSize)
	{
		m_nFront = 0;
	}
	else
	{
		++m_nFront;
	}

第一种写法比较无聊

同栈类一样，我们设计一个CQueue模板类，用以实现对队列的操作

类信息如下：

template<typename T>
class CQueue
{
	public:
		CQueue(int nSize = 50);
		~CQueue();
		void Enqueue(const T &item);
		T Dequeue();
		T QFront();
		bool IsQEmpty();
		void QClear();

	private:
		void QExpend();

	private:
		T *m_pList;
		int m_nSize;
		int m_nCount;
		int m_nFront;
		int m_nRear;
};

Enq和Deq的代码如下：

//=========================================
// 输  入: item(T) - [in]入队的元素
// 输  出: -
// 功  能: 将元素入队
//=========================================
template<typename T>
void CQueue<T>::Enqueue(const T &item)
{
	// 队列已满,自动扩充
	if (m_nCount == m_nSize)
	{
		QExpend();
	}

	// 元素入队,队尾指针下移
	m_pList[m_nRear] = item;
	//m_nRear = (m_nRear + 1) % m_nSize;

	if (m_nRear + 1 == m_nSize)
	{
		m_nRear = 0;
	}
	else
	{
		++m_nRear;
	}

	// 长度增加
	++m_nCount;
}

//=========================================
// 输  入: -
// 输  出: T - 出队的元素
// 功  能: 将元素出队
//=========================================
template<typename T>
T CQueue<T>::Dequeue()
{
	if (IsQEmpty())
	{
		_terr<<_T("Cannot dequeue from a empty queue And the operation was aborted")<<endl;
		getch();
		exit(1);
	}

	// 出队
	T temp = m_pList[m_nFront];
	//m_nFront = (m_nFront + 1) % m_nSize;

	if (m_nFront + 1 == m_nSize)
	{
		m_nFront = 0;
	}
	else
	{
		++m_nFront;
	}

	--m_nCount;

	return temp;
}

5.一些有趣的问题

关于栈和队列，我们来考虑一些额外的有趣的问题

Q1：如何用一个数组A[n]来实现两个栈，使得栈中元素总和小于n时不发生溢出，且Push和Pop操作的时间为O(1)

我们可以将一个数组划分成两部分，头部和尾部均作为栈底，如下图所示

左端的stack的操作和右端相反

Push(x)
if nTop + n – 1 – nTop’ = n – 1
return ERROR_FREE_SPACE_NOT_VALIUABLE
end if
A[nTop] <- x
nTop <- nTop + 1

Push’(x)类似～

Q2：如何利用两个栈实现一个队列

队列是FIFO，而栈是FILO。因此我们可以将一个栈作为辅助栈

如下图所示

所以入队操作可以用如下的伪代码表示

Procedure Enqueue(x)
StackA.Push(StackB.Pop(all))
StackA.Push(x)

Procedure Dequeue(x)
StackB.Push(StackA.Pop(all))
StackB.Pop

粗劣等版本，可以优化，但是总体操作时间仍然需要O(n)

Q3：如何利用两个队列实现一个栈

模拟方法类似Q2

Q4：设计一个双端队列。双端队列指的是，可以在队列的首端和尾端进行入队和出队的操作

双端队列的操作也大同小异，这里只给出Push和Pop的代码，其他自己翻SRC

template<typename T>
void CDQueue<T>::PushInFront(const T& item)
{
	if (m_nCount == m_nSize)
	{
		wcout<<L"no more free space"<<endl;
		return;
	}

	if (0 == m_nFront)
	{
		m_nFront = m_nSize - 1;
	}
	else
	{
		--m_nFront;
	}

	m_pQueue[m_nFront] = item;

	++m_nCount;
}

template<typename T>
void CDQueue<T>::PushInRear(const T& item)
{
	if (m_nCount == m_nSize)
	{
		wcout<<L"no more free space"<<endl;
		return;
	}

	if (++m_nRear == m_nSize)
	{
		m_nRear = 0;
	}

	m_pQueue[m_nRear] = item;

	++m_nCount;
}

template<typename T>
T CDQueue<T>::PopInFront()
{
	T tmp = m_pQueue[m_nFront];

	m_nFront = (m_nFront + 1) % m_nSize;
	--m_nCount;

	return tmp;
}

template<typename T>
T CDQueue<T>::PopInRear()
{
	T tmp = m_pQueue[m_nRear];

	if (0 == m_nRear)
	{
		m_nRear = m_nSize - 1;
	}
	else
	{
		--m_nRear;
	}

	--m_nCount;

	return tmp;
}

ps：双端队列是临时写的（其他都是高二时写的），为了方便，没有自动扩增～

Download：Stack_Queue_Src