一、前言本篇为数据结构第四讲栈、顺序栈、链栈。文中代码实现均以 C 为例。前三期我们介绍了线性结构合集本篇内容与前文关联紧密。还未学习线性结构的读者建议先阅读前三篇《【计算机408】数据结构》以打好基础。二、栈特点遵循后进先出是线性数据结构。组成部分栈顶top允许插入和删除的一端。栈底bottom固定不变、不允许操作的一端。操作入栈push在栈顶插入新元素。出栈pop从栈顶删除元素。注意仅允许在栈顶进行插入与删除操作。三、顺序栈1. 定义用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。2. 存储结构借助数组实现栈顶指针 top 指向栈顶元素的下一个位置。3. 基本操作1初始化代码实现seqStack(int initSize 100) { // initSize 顺序栈数组初始大小 if(initSize 0) throw badSize(); data new T[initSize]; maxSize initSize; top -1; }2判空代码实现template class T bool seqStackT::empty() const { return top -1; // 栈顶指针为 -1 时表示栈为空 }3入栈在栈顶插入元素图示代码实现//入栈操作,在栈顶插入元素value。 template class T void seqStackT::push(const T value) { if(top maxSize - 1) resize(); // 若栈已满需要进行扩容 data[top] value; // 栈顶指针上移将新元素放入栈顶位置 }4出栈图示代码实现template class T T seqStackT::pop(){ if(empty()) { throw outOfRange(); //栈为空时无法退栈,抛出异常outOfRange() } return data[top--]; }5取栈顶元素代码实现template class T T seqStackT::getTop() const{ if(empty()) throw outOfRange(); // 若空栈则无栈顶抛出异常outOfRange() return data[top]; }四、链栈1. 定义链栈是采用链式存储结构的栈利用带头结点的单链表实现。2. 存储结构每个结点包含数据域 data 和指针域 next栈顶指针 top 指向栈顶元素所在结点栈底元素的指针域为空。3. 基本操作1初始化代码实现template class T linkStackT::linkStack() { top nullptr; // 初始化空链栈栈顶指针置空 }2判空代码实现template class T bool linkStackT::empty() const { return top nullptr; // 栈顶指针为空时表示栈为空 }3入栈在栈顶插入元素代码实现template class T void linkStackT::push(const T value) { Node *p new Node(value,top); // 入栈操作将值为value的元素推入栈中 top p; }4出栈代码实现template class T T linkStackT::pop() { if(empty()) { //若为空栈则无法出栈元素则抛出异常outOfRange() throw outOfRange(); } Node *p top; T value p-data; top top-next; delete p; // 出栈操作将栈顶元素出栈 return value; // 返回元素值 }5取栈顶元素代码实现template class T T linkStackT::getTop() const { if(empty()) throw outOfRange(); //若为空栈则无法返回栈顶元素则抛出异常outOfRange() return top-data; }五、总结本文介绍了栈这种线性数据结构重点梳理了栈的定义、特点、组成部分和基本操作并分别给出了顺序栈与链栈的存储结构和代码实现。栈遵循后进先出原则在实际开发中应用广泛。