c++之数据结构——栈(stack)

关于栈的基本概念以及基本操作的c++实现

栈的定义栈的基本理论栈的图解栈的基本操作栈的两种形式及其c++实现(以整型为例)-顺序栈-链栈 (发表日期：2020/7/4)

栈的定义

栈是一种最基础的数据结构，是只允许在一端进行插入和删除的一种特殊的线性表。

栈的基本理论

栈中允许插入和删除的一端叫栈顶(top)，另一端则是栈底(bottom)。栈的插入称为入栈(push)，删除称为出栈(pop)。栈的特性是：后进先出，所以栈也叫后进先出表，简称LIFO表(Last In First Out)。

栈的图解

每次入栈时，将元素放入栈，栈顶上移对应当前元素每次出栈时，将栈顶元素移出栈，栈顶下移

---

当前栈：

---

入栈： 栈顶上移

---

出栈： 栈顶下移

栈的基本操作

初始化栈(stack)：将栈初始化，长度为0，栈顶为空出栈(pop)：将栈顶元素弹出入栈(push)：将目标元素放入栈，成为新的栈顶判空(isEmpty)：判断栈是否为空判满(isFull)<仅对顺序栈>：判断栈是否已满取栈顶元素(getTop)：返回栈顶元素获得栈中元素个数(getLength)：返回元素个数栈的析构(~stack)<仅对链栈>：释放栈中所有元素的内存空间

栈的两种形式及其c++实现(以整型为例)

-顺序栈

以顺序表(数组)作为栈的储存结构： c++代码实现：

#include<iostream> using namespace std; const int MAXSIZE=1000; class stack //栈 { public: stack(){ //初始化 top=-1; } bool isFull(){ //判满 if(top==MAXSIZE-1){ return true; } return false; } bool isEmpty(){ //判空 if(top==0){ cout<<"stack is empty.\n"; return true; } return false; } bool push(int num){ //入栈 if(isFull()){ return false; } top++; data[top]=num; return true; } bool pop(){ //出栈 if(isEmpty()){ return false; } top--; return true; } int getTop(){ //取栈顶元素 if(!isEmpty()){ return data[top]; } } int getLength(){ //得到栈中元素个数 return top+1; } private: int top; //栈顶 int data[MAXSIZE]; //顺序表 };

-链栈

以结构体链表作为栈的储存结构： c++代码实现：

#include<iostream> using namespace std; struct node{ //栈的元素结点 int data; node *next; }; class stack //栈 { public: stack(){ //初始化栈 top=NULL; count=0; } ~stack(){ //析构栈 while(!isEmpty()){ pop(); } } bool isEmpty(){ //判空 if(top==NULL){ cout<<"stack is empty.\n"; return true; } return false; } void push(int num){ //入栈 if(isEmpty()){ node *newNode=new node; newNode->data=num; newNode->next=NULL; top=newNode; count++; return; } node *newNode=new node; newNode->data=num; newNode->next=top; top=newNode; count++; } bool pop(){ //出栈 if(isEmpty()){ return false; } node *n=top; top=top->next; count--; delete n; return true; } int getTop(){ //取栈顶元素 if(!isEmpty()){ return top->data; } } int getLength(){ //返回栈中元素个数 return count; } private: node *top; //栈顶 int count; //用来记录栈中元素个数 };