基本理論

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;
}

插入數據時指針的指向變化

運行截圖