数据结构之栈的定义与实现

发表于 | 分类于

栈基础知识

栈(stack)是一种限制插入和删除只能在一端进行的线性表，允许插入删除的一端称为栈顶，另一端称为栈底。栈的基本操作有进栈(push)和出栈(pop)。当栈中不存在任何元素时称为空栈，此时进行出栈操作或者读取栈顶元素是一种错误。栈的实现既可以通过顺序表，也可以使用链表来实现。使用顺序表实现的栈称为顺序栈，使用链表实现的称为链式栈。由于栈的插入删除特性，因此栈具有“后进先出(LIFO)”的特点。考虑到栈在实际中的应用情况，栈一般需要实现以下操作：

  • 进栈操作：Push
  • 出栈操作：Pop
  • 判断是否为空：IsEmpty
  • 清空栈：MakeEmpty
  • 读取栈顶元素：Top

栈的链表实现

根据分析，栈在使用链表实现时，为了方便可以使用头插法并从头部弹出的结构实现。在STL的实现中，既可以采用deque作为底层容器，也可以采用list作为底层容器。

仿照《数据结构与算法分析-C语言描述》的定义，基本定义如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template <typename DataType>
class Node
{
public:
	Node(DataType inData, Node<DataType> *inNext):data(inData),next(inNext) {}
public:
	DataType data;
	Node<DataType> *next; /*下一个节点*/
};


template <typename DataType>
class Stack
{
public:
	Stack():dummyNode(-1,nullptr), stackSize(0) {}
	~Stack(); //析构函数，负责清空栈
	void Push(DataType inData); //压栈
	void Pop(); //出栈
	bool isEmpty(); //判断栈是否为空
	void MakeEmpty(); //清空栈
	DataType Top(); //返回栈顶元素，如果出错则抛出异常
	int StackSize(); //返回栈大小
private:
	Node<DataType> dummyNode; //哑节点
	int stackSize; //栈大小
};

如上所示，栈的主要数据成员为栈大小和一个辅助哑节点，如下依次实现栈的各函数

  • 压栈，采用头插法
1
2
3
4
5
6
template <typename DataType>
void Stack<DataType>::Push(DataType inData)
{
	dummyNode.next = new Node<DataType>(inData, dummyNode.next);
	++stackSize;
}
  • 出栈，如果栈为空则抛出异常
1
2
3
4
5
6
7
8
9
10
template <typename DataType>
void Stack<DataType>::Pop()
{
	if (stackSize <= 0 || dummyNode.next == nullptr) {
		throw "Stack is empty!";
	}
	Node<DataType> *tmp = dummyNode.next; /*暂存*/
	dummyNode.next = dummyNode.next->next;
	delete tmp; --stackSize;
}
  • 判断栈是否为空
1
2
3
4
5
template <typename DataType>
bool Stack<DataType>::isEmpty()
{
	return stackSize == 0 || dummyNode.next == nullptr;
}
  • 清空栈
1
2
3
4
5
6
7
8
9
10
template <typename DataType>
void Stack<DataType>::MakeEmpty()
{
	Node<DataType> *tmp = dummyNode.next; /*遍历*/
	while (tmp != nullptr) {
		dummyNode.next = tmp->next;
		delete tmp; --stackSize;
		tmp = dummyNode.next;
	}
}
  • 返回栈顶元素，如果出错则抛出异常
1
2
3
4
5
6
7
8
template <typename DataType>
DataType Stack<DataType>::Top()
{
	if (stackSize <= 0 || dummyNode.next == nullptr) {
		throw "Stack is empty!";
	}
	return dummyNode.next->data;
}
  • 返回栈大小
1
2
3
4
5
template <typename DataType>
int Stack<DataType>::StackSize()
{
	return stackSize;
}
  • 析构函数，清空栈
1
2
3
4
5
template <typename DataType>
Stack<DataType>::~Stack()
{
	MakeEmpty();
}

栈的数组实现

栈的数组实现可以直接使用STL的vector作为底层容器，这样数组大小可以动态调整，但是为了方便，这里使用固定数组大小的方式实现，因此会出现栈满的情况。使用数组实现的的栈定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename DataType>
class Stack
{
public:
	Stack(int inStackCapacity);
	~Stack(); //析构函数，负责清空栈
	void Push(DataType inData); //压栈
	void Pop(); //出栈
	bool isEmpty(); //判断栈是否为空
	void MakeEmpty(); //清空栈
	DataType Top(); //返回栈顶元素，如果出错则抛出异常
	int StackSize(); //返回栈大小
private:
	int stackCapacity;
	int stackSize;
	DataType *stackPtr; /*动态申请*/
};

如上所示，数组实现的栈只保存栈容量、栈大小以及指向栈存储位置的指针，以下依次实现各函数：

  • 构造函数
1
2
3
4
5
template <typename DataType>
Stack<DataType>::Stack(int inStackCapacity):stackCapacity(inStackCapacity),stackSize(0)
{
	stackPtr = new DataType[inStackCapacity];
}
  • 压栈，如果栈满则抛出异常
1
2
3
4
5
6
7
8
template <typename DataType>
void Stack<DataType>::Push(DataType inData)
{
	if (stackSize >= stackCapacity) {
		throw "Stack is full!";
	}
	stackPtr[stackSize++] = inData;
}
  • 出栈，如果栈为空则抛出异常
1
2
3
4
5
6
7
8
template <typename DataType>
void Stack<DataType>::Pop()
{
	if (stackSize <= 0) {
		throw "Stack is empty!";
	}
	--stackSize;
}
  • 判断栈是否为空
1
2
3
4
5
template <typename DataType>
bool Stack<DataType>::isEmpty()
{
	return stackSize <= 0;
}
  • 清空栈
1
2
3
4
5
template <typename DataType>
void Stack<DataType>::MakeEmpty()
{
	stackSize = 0;
}
  • 返回栈顶元素，如果出错则抛出异常
1
2
3
4
5
6
7
8
template <typename DataType>
DataType Stack<DataType>::Top()
{
	if (stackSize <= 0) {
		throw "Stack is empty!";
	}
	return stackPtr[stackSize-1];
}
  • 返回栈大小
1
2
3
4
5
template <typename DataType>
int Stack<DataType>::StackSize()
{
	return stackSize;
}
  • 析构函数，清空栈
1
2
3
4
5
6
template <typename DataType>
Stack<DataType>::~Stack()
{
	MakeEmpty();
	delete [] stackPtr;
}

代码测试

基本的算法测试和异常捕捉代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

int main()
{
	try {
		Stack<char> TestStack; /*不同实现*/
		for (int i = 0; i < 26; i++) {
			TestStack.Push('A'+i);
		}
		for (int i = 0; i < 26; i++) {
			cout << TestStack.Top() << ";";
			TestStack.Po0p();
		}
		cout << endl;

	}
	catch(const char *msg) {
		cout << msg << endl;
		return -1;
	}
	return 0;
}

参考资料

数据结构与算法分析