- 栈是一种线性数据结构,遵循先进后出的原则;
- 存储以及数据查找时,只能在一端操作;
- 栈的运用:作进制转换、括号匹配等;
注:数据结构系列将持续更新,欢迎交流讨论…
栈抽象结构图 代码实现- 需要说明的是,展示代码中将栈置空的函数 Empty() 函数做的是逻辑上的清空,并不是真正的清空;
- 其中,主函数中还展示了栈作进制转换的代码;
#include插入数据时指针的指向变化 运行截图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; }