数据结构-顺序栈C++示例

栈(stack)是限定仅在表尾进行插入或删除操作的线性表。

对栈来说，表尾端称为栈顶(top)， 表头端称为栈底(bottom)，不含元素的空表称为空栈。

假设栈$S=(a_1,a_2,a_3,\cdots ,a_n)$ , 则称$a_1$为栈底元素，$a_n$为栈顶元素，插入元素到栈顶(即表尾)的操作称为入栈， 从栈顶(即表尾)删除最后一个元素的操作称为出栈。栈元素的修改是按后进先出的原则进行的，因此栈又称为后进先出(Last In First Out, LIFO)的线性表。

由于栈固有的后进先出特性，使得栈称为程序设计中的有用工具，另外，如果问题求解的过程具有“后进先出”的天然特性的话，则求解的算法中也需要利用“栈”， 如：

• 数制转换
• 表达式求值
• 括号匹配的检验
• 八皇后问题
• 行编辑程序
• 函数调用
• 迷宫求解
• 递归调用的实现

抽象数据类型定义

ADT Stack{

​ 数据对象: D = { a i ∣ a i ∈ E l e m S e t , i = 1 , 2 , 3 , ⋯ , n , n ≥ 0 } D=\{{a_i}| a_i \in ElemSet, i=1,2,3,\cdots,n, n \geq 0\} D={ai​∣ai​∈ElemSet,i=1,2,3,⋯,n,n≥0}

​ 数据关系: R = { < a i − 1 , a i > ∣ a i − 1 , a i ∈ D , i = 1 , 2 , 3 , ⋯ , n } R=\{<a_{i-1}, a_i> | a_{i-1},a_i \in D, i = 1,2,3,\cdots,n\} R={<ai−1​,ai​>∣ai−1​,ai​∈D,i=1,2,3,⋯,n}

​ 约定$a_n$ 端为栈顶，$a_1$ 端为栈底。

​ 基本操作：

​ InitStack(&S)

​ 操作结果：构造一个空栈$S$

​ DestroyStack(&S)

​ 初始条件：栈$S$已经存在

​ 操作结果：栈$S$被销毁

​ ClearStack(&S)

​ 初始条件：栈$S$已经存在

​ 操作结果：将栈$S$ 清空

​ StackEmpty(&S)

​ 初始条件：栈$S$已经存在

​ 操作结果：若栈$S$ 为空栈，则返回true， 否则返回false

​ StackLength(&S)

​ 初始条件：栈$S$已经存在

​ 操作结果：返回栈$S$ 的元素个数，即栈的长度

​ GetTop(&S)

​ 初始条件：栈$S$已经存在且非空

​ 操作结果：返回栈$S$ 的栈顶元素

​ Push(&S,e)

​ 初始条件：栈$S$已经存在

​ 操作结果：插入元素e为新的栈顶元素

​ Pop(&S,e)

​ 初始条件：栈$S$已经存在且非空

​ 操作结果：删除S的栈顶元素，并且用e 返回其值

​ StackTraverse(&S,e)

​ 初始条件：栈$S$已经存在且非空

​ 操作结果：从栈底到栈顶一次对S的每个数据元素进行访问

}ADT Stack

顺序栈

顺序栈是指利用顺序存储结构实现的栈。

初始化

bool InitStack(SqStack &S)
{S.base = new SElemType[MaxSize];if (!S.base){std::cerr << "内存分配失败" << std::endl;return false;}S.front = S.base;S.stacksize = MaxSize;return true;
}

销毁

bool DestroyStack(SqStack &S)
{if (S.base){delete[] S.base;S.stacksize = 0;S.base = S.front = nullptr;return true;}return false;
}

清空

bool ClearStack(SqStack &S)
{if (S.base){S.front = S.base;return true;}return false;
}

是否为空栈

bool StackEmpty(const SqStack &S)
{return S.base == S.front;
}

栈长度

int StackLength(const SqStack &S)
{return S.front - S.base;
}

入栈

bool Push(SqStack &S, const SElemType &e)
{if (S.front - S.base == S.stacksize){std::cerr << "顺序栈已满，无法插入新元素" << std::endl;return false;}*(S.front) = e;S.front++;return true;
}

出栈

bool Pop(SqStack &S, SElemType &e)
{if (StackEmpty(S)){std::cerr << "空栈无法取值" << std::endl;return false;}S.front--;e = *(S.front);return true;
}

获取栈顶元素

SElemType GetTop(const SqStack &S)
{if (StackEmpty(S)){std::cerr << "空栈无法取值" << std::endl;return false;}return *(S.front - 1);
}

遍历栈元素

void StackTraverse(const SqStack &S)
{for (int i = 0; i < S.front - S.base; i++){std::cout << "第 " << i + 1 << " 个元素为: " << S.base[i] << std::endl;}
}

头文件

#pragma once
#include <iostream>const int MaxSize = 100;
typedef int SElemType;
typedef struct _SqStack
{SElemType *base;  // 栈底SElemType *front; // 栈顶int stacksize;    // 栈可用的最大容量
} SqStack;bool InitStack(SqStack &S);
bool DestroyStack(SqStack &S);
bool ClearStack(SqStack &S);
bool StackEmpty(const SqStack &S);
int StackLength(const SqStack &S);
bool Push(SqStack &S, const SElemType &e);
bool Pop(SqStack &S, SElemType &e);
void StackTraverse(const SqStack &S);
SElemType GetTop(const SqStack &S);

测试文件

#include "include/stack.h"int main()
{SqStack S;InitStack(S);Push(S, 1);Push(S, 2);Push(S, 3);Push(S, 4);StackTraverse(S);SElemType top = GetTop(S);std::cout << "栈顶元素为: " << top << std::endl;int stack_len = StackLength(S);std::cout << "栈长度: " << stack_len << std::endl;Pop(S, top);StackTraverse(S);std::cout << "++++++++++++++" << std::endl;ClearStack(S);StackTraverse(S);DestroyStack(S);return 0;
}

链栈

链栈是指采用链式存储结构实现的栈。通常使用单链表来表示，由于栈的主要操作是在栈顶插入和删除，为了方便，这里将链表的头结点作为栈顶，且不需要头结点。

初始化

bool InitStack(LinkStack &S)
{S = nullptr;return true;
}

销毁

bool DestroyStack(LinkStack &S)
{while (S){StackNode *tmp = S->next;S = S->next;delete tmp;}return true;
}

清空

bool ClearStack(LinkStack &S)
{DestroyStack(S->next);S = nullptr;return true;
}

是否为空栈

bool StackEmpty(const LinkStack &S)
{return !S;
}

栈长度

int StackLength(const LinkStack &S)
{int len = 0;StackNode *tmp = S;while (tmp){len++;tmp = tmp->next;}return len;
}

入栈

bool Push(LinkStack &S, const ElemType &e)
{StackNode *p = new StackNode;p->data = e;p->next = S;S = p;return true;
}

出栈

bool Pop(LinkStack &S, ElemType &e)
{if (S){e = S->data;StackNode *tmp = S;S = S->next;delete tmp;return true;}return false;
}

获取栈顶元素

ElemType GetTop(const LinkStack &S)
{if (S)return S->data;else{return 0;}
}

遍历栈元素

void StackTraverse(const LinkStack &S)
{StackNode *tmp = S;int i = 0;while (tmp){i++;std::cout << "第 " << i << " 个元素为: " << tmp->data << std::endl;tmp = tmp->next;}
}

文章参考 严蔚敏老师《数据结构 C语言版 第2版》和青岛大学王卓数据结构视频课