数据结构之链式栈的实现与简单运用

基本理论

1. 栈是一种线性数据结构，遵循先进后出的原则；
2. 存储以及数据查找时，只能在一端操作；
3. 栈的运用：作进制转换、括号匹配等；

注：数据结构系列将持续更新，欢迎交流讨论…

栈抽象结构图

代码实现

• 需要说明的是，展示代码中将栈置空的函数 Empty() 函数做的是逻辑上的清空，并不是真正的清空；
• 其中，主函数中还展示了栈作进制转换的代码；

/*
   pop
   top
   push
   size
   isEmpty
   进制转换

   先进后出
*/
#include <iostream>

using namespace std;

typedef struct DATA
{
	int data;
	DATA* next;
}*pData;

class Stack
{
public:
	Stack(int);
	pData initData();//初始化数据结点
	int push(int data);//入栈操作
	int pop();//出栈
	int top();//返回栈顶元素
	int size();//返回栈容量大小
	bool isEmpty();//判断栈是否为空
	void empty();//将栈作逻辑上的置空

private:
	int curSize;
	int Size;
	DATA* stackTop;
};

int main()
{
	Stack* pStk = new Stack(10);
	if (pStk->isEmpty())
	{
		cout << "栈为空..." << endl;
	}
	pStk->push(1);
	pStk->push(2);
	pStk->push(3);
	pStk->push(4);
	pStk->push(5);
	
	while (!pStk->isEmpty())
	{
		cout << pStk->top() << " ";
		pStk->pop();
	}
	cout << endl << "栈的容量为:" << pStk->size() << endl;
	pStk->empty();
	if (pStk->isEmpty())
	{
		cout << "栈为空..." << endl;
	}
	pStk->push(1);
	pStk->push(2);
	pStk->push(3);

	while (!pStk->isEmpty())
	{
		cout << pStk->top() << " ";
		pStk->pop();
	}
	cout << endl;
	//栈简单的运用：进制转换
	Stack* pChange = new Stack(12);
	int num = 520;
	while (num)
	{
		pChange->push(num % 2);
		num /= 2;
	}
	while (!pChange->isEmpty())
	{
		cout << pChange->top();
		pChange->pop();
	}

	return 0;
}

Stack::Stack(int maxSize):Size(maxSize)
{
	curSize = 0;
	stackTop = initData();
}

pData Stack::initData()
{
	pData newNode = new DATA;
	newNode->data = -1;
	newNode->next = nullptr;

	return newNode;
}

int Stack::push(int data)
{
	if (curSize >= Size)
	{
		return -1;
	}

	pData newNode = initData();
	newNode->data = data;

	newNode->next = stackTop;
	stackTop = newNode;

	curSize++;

	return 1;
}

int Stack::pop()
{
	if (curSize > 0)
	{
		pData nextNode = stackTop->next;
		free(stackTop);
		stackTop = nextNode;
		curSize--;
		return 1;
	}

	return -1;
}

int Stack::top()
{
	if (curSize > 0)
	{
		return stackTop->data;
	}

	return INT_MAX;
}

int Stack::size()
{
	return this->Size;
}

bool Stack::isEmpty()
{
	return this->curSize == 0;
}

void Stack::empty()
{
	this->curSize = 0;
}

插入数据时指针的指向变化

运行截图