锐客网

  1. 首页 > it技术 > >

数据结构与算法|数据结构与性质(2)栈(stack)基础板子

数据结构c++容器STL

一.栈的定义
抛开算法，栈在字典中解释为"储存货物或供旅客住宿的房屋",可引申为仓库、中转站，例如我们现在生活中的酒店，在古时候叫客栈，供旅客休息的地方，旅客可以边客栈休息.,休息完毕就离开客栈。
数据结构与算法|数据结构与性质(2)栈(stack)基础板子
文章图片

我们把生活中的栈类比到计算机中，可以猜想栈是供数据休息(即存储数据)的地方。事实上这么说也是正确的，数据既可以进栈，也可以出栈。栈是一种先进后出(FILO)的数据结构，是一种只能在一端进行加入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数封在栈顶，需要读数据的时候从栈顶开始（最后一个数被第一个读出来) 。
实际上，栈某种意义上讲，它像是一个开口的盒子，先放进去的东西总是会被后放进去的东西压在下面，那么如果想拿出被压住的东西，必须要先取出顶部的东西，也就是后放进去的东西。换个说法就是先入后出。

数据结构与算法|数据结构与性质(2)栈(stack)基础板子
文章图片


我们称数据进入栈的操作叫压栈，数据从栈中出去的操作叫弹栈。如果有n个元素进栈，出栈元素排序的方法为 数据结构与算法|数据结构与性质(2)栈(stack)基础板子
文章图片
种，以上公式称为卡特兰数(Catalan number , 1838年)，会用就可以了。
二.栈的顺序存储实现:(数据结构版)(代码很长，注释很仔细)(不知道自己咋肝出来的）

#include #include #define MAXSIZE 10// 顺序栈的最大长度。typedef int ElemType; // 自定义顺序栈的数据元素为整数。typedef struct { ElemType data[MAXSIZE]; // 用数组存储顺序栈中的元素。 int top; // 栈顶指针，从0到MAXSIZE-1，-1表示空栈。 // 也可以从1到MAXSIZE，0表示空栈。 }SeqStack,*PSeqStack; // 顺序栈SS的初始化操作。 void InitStack(PSeqStack SS); // 销毁顺序栈SS。 void DestroyStack(PSeqStack SS); // 元素入栈，返回值：0-失败；1-成功。 int Push(PSeqStack SS, ElemType *ee); // 元素出栈，返回值：0-失败；1-成功。 int Pop(PSeqStack SS, ElemType *ee); // 求顺序栈的长度，返回值：栈SS中元素的个数。 int Length(PSeqStack SS); // 清空顺序栈。 void Clear(PSeqStack SS); // 判断顺序栈是否为空，返回值：1-空，0-非空或失败。 int IsEmpty(PSeqStack SS); // 判断顺序栈是否已满，返回值：1-已满，0-未满或失败。 int IsFull(PSeqStack SS); // 打印顺序栈中全部的元素。 void PrintStack(PSeqStack SS); // 获取栈顶元素，返回值：0-失败；1-成功。 // 只查看栈顶元素的值，元素不出栈。 int GetTop(PSeqStack SS, ElemType *ee); int main() { SeqStack SS; // 创建顺序栈。InitStack(&SS); // 初始化顺序栈。printf("栈的长度是%d\n",Length(&SS)); ElemType ee; // 创建一个数据元素。printf("元素（1、2、3、4、5、6、7、8、9、10）入栈。\n"); ee=1; Push(&SS, &ee); ee=2; Push(&SS, &ee); ee=3; Push(&SS, &ee); ee=4; Push(&SS, &ee); ee=5; Push(&SS, &ee); ee=6; Push(&SS, &ee); ee=7; Push(&SS, &ee); ee=8; Push(&SS, &ee); ee=9; Push(&SS, &ee); ee=10; Push(&SS, &ee); printf("栈的长度是%d\n",Length(&SS)); // 只查看栈顶元素的值，元素不出栈。 if (GetTop(&SS,&ee)==1)printf("栈顶的元素值为%d\n",ee); PrintStack(&SS); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); if (Pop(&SS,&ee)==1)printf("出栈的元素值为%d\n",ee); return 0; }// 初始化顺序栈 void InitStack(PSeqStack SS) { Clear(SS); // 清空顺序栈。 }// 清空顺序栈。 void Clear(PSeqStack SS) { if (SS == NULL) return; // 检查空指针。SS->top=-1; // 栈顶指针置为-1。 memset(SS->data,0,sizeof(ElemType)*MAXSIZE); // 数组元素清零。 }// 求顺序栈的长度，返回值：栈SS中元素的个数。 int Length(PSeqStack SS) { if (SS == NULL) return 0; // 检查空指针。return SS->top+1; }// 销毁顺序栈SS。 void DestroyStack(PSeqStack SS) { // 静态顺序栈无需释放内存，不需要销毁操作。Clear(SS); // 清空顺序栈。return; }// 判断顺序栈是否为空，返回值：1-空，0-非空或失败。 int IsEmpty(PSeqStack SS) { if (SS == NULL) return 0; // 检查空指针。if (SS->top == -1) return 1; return 0; }// 判断顺序栈是否已满，返回值：1-已满，0-未满或失败。 int IsFull(PSeqStack SS) { if (SS == NULL) return 0; // 检查空指针。if (SS->top >= MAXSIZE-1) return 1; return 0; }// 元素入栈，返回值：0-失败；1-成功。 int Push(PSeqStack SS, ElemType *ee) { if ( (SS == NULL) || (ee == NULL) ) return 0; // 检查空指针。if (IsFull(SS) == 1) { printf("顺序栈已满，不能插入。\n"); return 0; }SS->top++; // 栈指针先加1。memcpy(&SS->data[SS->top],ee,sizeof(ElemType)); // 用数组的下标访问。 // memcpy(SS->data+SS->top,ee,sizeof(ElemType)); // 采用指针运算也可以。return 1; }// 打印顺序栈中全部的元素。 void PrintStack(PSeqStack SS) { if (SS == NULL) return; // 检查空指针。if (SS->top == -1) { printf("栈为空。\n"); return; }int kk; for (kk = 0; kk <= SS->top; kk++) { printf("SS[%d],value=https://www.it610.com/article/%d/n",kk,SS->data[kk]); // 用数组的下标访问。 // printf("SS[%d],value=https://www.it610.com/article/%d/n",kk,*(SS->data+kk)); // 采用指针运算也可以。 } }// 元素出栈，返回值：0-失败；1-成功。 int Pop(PSeqStack SS, ElemType *ee) { if ( (SS == NULL) || (ee == NULL) ) return 0; // 检查空指针。if (SS->top == -1) { printf("栈为空。\n"); return 0; }memcpy(ee,&SS->data[SS->top],sizeof(ElemType)); // 用数组的下标访问。 // memcpy(ee,SS->data+SS->top,sizeof(ElemType)); // 采用指针运算也可以。SS->top--; // 栈指针减1。return 1; }// 获取栈顶元素，返回值：0-失败；1-成功。 // 只查看栈顶元素的值，元素不出栈。 int GetTop(PSeqStack SS, ElemType *ee) { if ( (SS == NULL) || (ee == NULL) ) return 0; // 检查空指针。if (IsEmpty(SS) == 1) { printf("栈为空。\n"); return 0; }memcpy(ee,&SS->data[SS->top],sizeof(ElemType)); // 用数组的下标访问。 // memcpy(ee,SS->data+SS->top,sizeof(ElemType)); // 采用指针运算也可以。return 1; }

最终结果:数据结构与算法|数据结构与性质(2)栈(stack)基础板子
文章图片


三.栈的常用接口(C++中STL的使用):
构造函数:
stack stk; //stack采用模板类实现, stack对象的默认构造形式 stack(const stack &stk); //拷贝构造函数

赋值操作:
stack& operator=( const stack &stk) ; //重载等号操作符

数据存取:
push(elem); //向栈顶添加元素 pop(); //从栈顶移除第一个元素 top(); //返回栈顶元素

大小操作:
empty(); //判断堆栈是否为空 size(); //返回栈的大小

操作案例:
#include #include using namespace std; //栈stack容器 void test12() { //特点:符合先进后出数据结构 stacks; //入栈 s.push(10); s.push(20); s.push(30); s.push(40); cout<<"栈的大小: "<

数据结构与算法|数据结构与性质(2)栈(stack)基础板子
文章图片









【数据结构与算法|数据结构与性质(2)栈(stack)基础板子】

    推荐阅读


    上一篇：leetcode|Leetcode二分查找4:69. x 的平方根

    下一篇：哈希|Leetcode二分查找11:1346. 检查整数及其两倍数是否存在