精华内容
下载资源
问答
  • 文章目录栈的定义栈的存储栈上的基本操作初始化判空操作进栈操作出栈操作读栈顶元素遍历栈销毁栈完整代码实例共享栈 栈的定义 栈(Stack)是只允许在一端进行插入或删除操作的线性表。 栈的示意图: 栈顶Top:...

    栈的定义

    栈(Stack)是只允许在一端进行插入或删除操作的线性表。

    栈的示意图:
    栈

    • 栈顶Top:线性表允许插入和删除的那一端。
    • 栈底Bottom:固定的,不允许进行插入和删除的另一端。

     假设某个栈S={a1,a2, … ,an},如上图所示,则a1为栈底元素,an为栈顶元素。由于只能在栈顶进行插入和删除操作,故进栈顺序为a1,a2, … ,an,出栈顺序为an, … ,a2,a1。故栈的操作特性是后进先出LIFO(Last In First Out),称为后进先出的线性表。

     空栈:不含任何元素的空表。

    栈的存储

     栈的存储方式有两种:顺序栈和链栈,即栈的顺序存储和链式存储。
     采用顺序存储的栈称为顺序栈,它利用一组地址连续的存储单元存放自栈底到栈顶的元素,同时附设一个指针(top)指示当前栈顶的位置。
     栈的顺序存储类型描述:

    #define MaxSize 100 //定义栈中元素的最大个数
    typedef struct SqStack{
        int data[MaxSize]; //存放栈中的元素
        int top; //栈顶指针
    }SqStack;
    

     采用链式存储的栈称为链栈,链栈便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现,并且所有操作都是在单链表的表头进行的。在本文中主要是介绍了顺序栈下的一些基本操作,关于链栈的实现与单链表类似,可以参考单链表的定义及其基本操作

     栈的链式存储类型描述:

    typedef struct LinkNode{
        int data; //数据域
        struct LinkNode *next; //指针域
    }*LiStack; //栈类型定义
    

    栈上的基本操作

     栈的基本操作包括:

    • 初始化InitStack(&S);
    • 判空Empty(S);
    • 进栈Push(&S, x);
    • 出栈Pop(&S, &x);
    • 读栈顶元素GetTop(S);
    • 遍历栈PrintStack(&S);
    • 销毁栈DestroyStack(&S);

     [注]以上操作均采用顺序栈来实现。

    初始化

    初始时设置S.top = -1。

    //初始化
    void InitStack(SqStack &S){
        S.top = -1;
    }
    

    判空操作

     栈空条件:S.top == -1; 栈满条件:S.top ==MaxSize-1。

    //判栈空
    bool Empty(SqStack S){
        if(S.top == -1){
            return true;
        }else{
            return false;
        }
    }
    

    进栈操作

     由于初始设置S.top=-1,故栈顶指针先加一,再入栈。

    入栈

    //入栈
    void Push(SqStack &S, int x){
        if(S.top == MaxSize-1){
            cout<<"栈满"<<endl;
            return;
        }
        S.data[++S.top] = x; //指针先加一,再入栈
    }
    

    出栈操作

     先出栈,指针再减一。

    出栈

    //出栈
    void Pop(SqStack &S, int &x){
        if(S.top == -1){
            cout<<"栈空"<<endl;
            return;
        }
        x = S.data[S.top--]; //先出栈,指针再减一
    }
    

    读栈顶元素

    //读栈顶元素
    int GetTop(SqStack S){
        if(S.top == -1){
            cout<<"栈空"<<endl;
            return -1;
        }else{
            return S.data[S.top];
        }
    }
    

    遍历栈

     当栈不为空时,循环输出当前栈顶元素。

    //遍历栈
    void PrintStack(SqStack S){
        while(S.top != -1){
            cout<<S.data[S.top--]<<" ";
        }
        cout<<endl;
    }
    

    销毁栈

     栈的销毁令S.top = -1即可。

    //销毁栈
    void DestroyStack(SqStack &S){
        S.top = -1;
    }
    

    完整代码及实例

     完整代码及实例:

    #include<bits/stdc++.h>
    using namespace std;
    
    #define MaxSize 100 //定义栈中元素的最大个数
    typedef struct SqStack{
        int data[MaxSize]; //存放栈中的元素
        int top; //栈顶指针
    }SqStack;
    
    //初始化
    void InitStack(SqStack &S){
        S.top = -1;
    }
    
    //判栈空
    bool Empty(SqStack S){
        if(S.top == -1){
            return true;
        }else{
            return false;
        }
    }
    
    //入栈
    void Push(SqStack &S, int x){
        if(S.top == MaxSize-1){
            cout<<"栈满"<<endl;
            return;
        }
        S.data[++S.top] = x;
    }
    
    //出栈
    void Pop(SqStack &S, int &x){
        if(S.top == -1){
            cout<<"栈空"<<endl;
            return;
        }
        x = S.data[S.top--];
    }
    
    //读栈顶元素
    int GetTop(SqStack S){
        if(S.top == -1){
            cout<<"栈空"<<endl;
            return -1;
        }else{
            return S.data[S.top];
        }
    }
    
    //遍历栈
    void PrintStack(SqStack S){
        while(S.top != -1){
            cout<<S.data[S.top--]<<" ";
        }
        cout<<endl;
    }
    
    //销毁栈
    void DestroyStack(SqStack &S){
        S.top = -1;
    }
    
    int main(){
        SqStack S;
        InitStack(S);
        Push(S,1);//入栈
        Push(S,2);
        Push(S,3);
        Push(S,4);
        cout<<"栈顶元素为:"<<GetTop(S)<<endl;
        cout<<"出栈顺序为:";
        PrintStack(S);
        int x;
        Pop(S,x);
        cout<<x<<"出栈"<<endl;
        cout<<"栈中剩余元素:";
        PrintStack(S);
        Pop(S,x);
        cout<<x<<"出栈"<<endl;
        cout<<"栈中剩余元素:";
        PrintStack(S);
        if(!Empty(S)){
            cout<<"当前栈不为空"<<endl;
        }else{
            cout<<"当前栈为空"<<endl;
        }
        return 0;
    }
    

     运行结果:
    在这里插入图片描述

    共享栈

     利用栈底位置相对不变的特性,可以让两个顺序栈共享一个一维数据空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸。如下图所示:

    共享栈
    两个栈的栈顶指针都指向栈顶元素。

    判空:top0 = -1 时0号栈为空, top1 = MaxSize-1 时1号栈为空。

    栈满:当且仅当两个栈顶指针相邻,即top1 - top0 = 1 时栈满。

    进栈:0号栈进栈时,top0先加一再赋值, 1号栈进栈时top1先减一再赋值。

    出栈:0号栈出栈时,先出栈top0再减一, 1号栈出栈时先出栈top1再加一。

    展开全文
  • 1.顺序 #define MaxSize 50 typedef struct{ Elemtype data; int top; }SqStack;...2.链栈(使用时一般不用头结点) ...以下操作均为顺序 ...3.初始化 void InitStack(SqStack &s) { s.top=-1; } 4.判空 b

    1.顺序栈

    #define MaxSize 50
    typedef struct{
    	Elemtype data;
    	int top;
    }SqStack;

    2.链栈(使用时一般不用头结点)

    typedef struct Linknode{
    	ElemType data;
    	struct Linknode *next;
    } *LinkStack;

    以下操作均为顺序栈

    3.初始化

    void InitStack(SqStack &s)
    {
        s.top=-1;
    }

    4.判空

    bool StackEmpty(SqStack S)
    {
    	if(S.top==-1)
    		return true;
    	else
    		return false;
    }

    5.进栈

    bool Push(SqStack &S,ElemType x)
    {
    	if(S.top==MaxSize-1)
    		return false;
    	S.data[++top]=x;
    	return true;
    }

    6.出栈

    bool Pop(SqStack &S,ElemType &x)
    {
    	if(S.top==-1)
    		return false;
    	x=S.data[top--];
    	return true;
    }

    7.读取栈顶元素

    bool GetTop(SqStack S,ElemType &x)
    {
    	if(S.top==-1)
    		return false;
    	x=S.data[top];
    	return true;
    }

     

    展开全文
  • 链表的定义及操作(C++)链表的定义链表的基本操作链表的基础算法 链表的定义 typedef int ElemType; typedef struct LNode{ ElemType val; LNode * next; } LinkNode; 链表的基本操作 void InitList(LinkNode *...

    顺序栈

    顺寻栈的定义

    typedef int ElemType;
    
    const int MaxSize = 50;
    
    typedef struct {
        ElemType data[MaxSize];
        int top; //栈顶指针,空栈为-1
    } SqStack;
    

    顺序栈的基本操作

    void InitStack(SqStack *&);             // 初始化栈
    void DestroyStack(SqStack *&);          // 销毁栈
    bool StackEmpty(SqStack *);             // 判断栈是否为空
    bool Push(SqStack *&, ElemType);        // 进栈
    bool Pop(SqStack *&);                   // 出栈
    ElemType Top(SqStack *);                // 返回栈顶元素
    
    void InitStack(SqStack * &s) {
        s = (SqStack *)malloc(sizeof(SqStack));
        s -> top = -1;
    }
    
    void DestroyStack(SqStack * &s) {
        free(s);
    }
    
    bool StackEmpty(SqStack * s) {
        return s -> top == -1;
    }
    
    bool Push(SqStack * &s, ElemType e) {
        if (s -> top == MaxSize - 1) return false;
        s -> top++;
        s -> data[s -> top] = e;
        return true;
    }
    
    bool Pop(SqStack * &s) {
        if (s -> top == -1) return false;
        s -> top--;
        return true;
    }
    
    ElemType Top(SqStack * s) {
        // 栈不为空
        return s -> data[s -> top];
    }
    

    顺序栈的基本算法

    bool RerverseJudge(vector<ElemType>);                   // 判断数组元素是否为回文串,通常为字符串类型
    bool Validseq(vector<ElemType>, vector<ElemType>);      // 判断出栈序列是否为原数组的合法出栈序列
    
    bool RerverseJudge(vector<ElemType> str) {
        SqStack * s;
        InitStack(s);
        for (int i = 0; i < str.size(); i++) Push(s, str[i]);
        for (int i = 0; i < str.size(); i++) {
            ElemType e = Top(s);
            Pop(s);
            if (str[i] != e) return false;
        }
        DestroyStack(s);
        return true;
    }
    
    bool Validseq(vector<ElemType> nums, vector<ElemType> target) {
        SqStack * s;
        InitStack(s);
        int j = 0;
        for (int i = 0; i < nums.size(); i++) {
            Push(s, nums[i]);
            while (j < target.size() && Top(s) == target[j]) {
                Pop(s);
                j++;
            }
        }
        bool flag = StackEmpty(s);
        DestroyStack(s);
        return flag;
    }
    

    链栈

    链栈的定义

    typedef int ElemType;
    
    typedef struct LStack {
        ElemType data;
        LStack * next;
    } LinkStack;
    
    

    链栈的基本操作

    void InitStack(LinkStack *&);             // 初始化栈
    void DestroyStack(LinkStack *&);          // 销毁栈
    bool StackEmpty(LinkStack *);             // 判断栈是否为空
    bool Push(LinkStack *&, ElemType);        // 进栈
    bool Pop(LinkStack *&);                   // 出栈
    ElemType Top(LinkStack *);                // 返回栈顶元素
    
    void InitStack(LinkStack * &s) {
        s = (LinkStack *)malloc(sizeof(LinkStack));
        s -> next = NULL;
    }
    
    void DestroyStack(LinkStack * &s) {
        LinkStack * pre = s -> next, * p;
        s -> next = NULL;
        while (pre != NULL) {
            p = pre;
            pre = pre -> next;
            free(p);
        }
        free(pre);
    }
    
    bool StackEmpty(LinkStack * s) {
        return s -> next == NULL;
    }
    
    bool Push(LinkStack * &s, ElemType e) {
        if(s == NULL) return false;
        LinkStack * p = (LinkStack *)malloc(sizeof(LinkStack));
        p -> data = e;
        p -> next = s -> next;
        s -> next = p;
        return true;
    }
    
    bool Pop(LinkStack * &s) {
        if(s == NULL || s -> next == NULL) return false;
        LinkStack * p = s -> next;
        s -> next = p -> next;
        free(p);
        return true;
    }
    
    ElemType Top(LinkStack * s) {
        // 栈不为空
        return s -> next -> data;
    }
    

    栈的经典运算

    中缀表达式 链接:栈运算之中缀表达式

    展开全文
  • #include const int MAX=5;...//定义名为stack类,其具有功能 class stack { //数据成员 float num[MAX]; //存放数据数组 int top; //指示栈顶位置变量 public: //成员函数 void i
    #include<iostream.h>
    const int MAX=5;     //假定栈中最多保存5个数据
    
    //定义名为stack的类,其具有栈功能
    class  stack {
        //数据成员
        float  num[MAX];  //存放栈数据的数组
        int  top;          //指示栈顶位置的变量
    public:
        //成员函数
        void init(void) { top=0; }    //初始化函数
        void push(float x)          //入栈函数
        {
            if (top==MAX){
                cout<<"Stack is full !"<<endl;
                return;
            };
            num[top]=x;
            top++;
        }
        float pop(void)          //出栈函数
        {
            top--;
            if (top<0){
            cout<<"Stack is underflow !"<<endl;
            return 0;
            };
            return num[top];
        }
    }
    
    //以下是main()函数,其用stack类创建栈对象,并使用了这些对象
    main(void)
    {
        //声明变量和对象
        int i;
        float x;
        stack a,b;    //声明(创建)栈对象
    
        //以下对栈对象初始化
        a.init();
        b.init();
    
        //以下利用循环和push()成员函数将2,4,6,8,10依次入a栈对象
        for (i=1; i<=MAX; i++)
            a.push(2*i);
    
        //以下利用循环和pop()成员函数依次弹出a栈中的数据并显示
        for (i=1; i<=MAX; i++)
           cout<<a.pop()<<"  ";
        cout<<endl;
    
        //以下利用循环和push()成员函数将键盘输入的数据依次入b栈
        cout<<"Please input five numbers."<<endl;
        for (i=1; i<=MAX; i++) {
             cin>>x;
             b.push(x);
        }
     
        //以下利用循环和pop()成员函数依次弹出b栈中的数据并显示
        for (i=1; i<=MAX; i++)
           cout<<b.pop()<<"  ";
    }
    


     

    文献来源:

    UNDONER(小杰博客) :http://blog.csdn.net/undoner

    LSOFT.CN(琅软中国) :http://www.lsoft.cn

     

    展开全文
  • 文章目录前言框架整体流程图类的定义初始化内存区域本章代码 前言 为什么不用C而用C++呢? 在单核的情况下,用C还比较方便些,但在多核的情况下,每个核心都需要分配有对应的一个VMX区域,VMCS区域,MsrBitmap区域和空间...
  • 数据结构之栈的定义及python实现

    千次阅读 2017-07-10 19:15:46
    栈是一个逻辑结构,通俗的讲,是一个有“纪律”的线性表,栈只允许一端进行插入和删除操作,即“先进后出”规则...同样的,栈也有初始化,判定是否为空,插入(进栈),删除(出栈)等操作。下面是关于栈的python实现。
  • 这篇主要学习链路层在内核协议栈的实现,包括初始化、注册以及接收发送,会涉及相关函数和代码所在位置。我们知道以太网不仅可以传输IP分组,还可以传输其他协议的分组,接收系统必须能够区分不同的协议类型,以便将...
  • 一次性初始化   有些事需要且只能执行一次(比如互斥量初始化)。通常当初始化应用程序时,可以比较容易地将其...然后创建一个与控制变量相关的初始化函数。 pthread_once_t once_control = PTHREAD_ONCE_INIT; vo
  • 顺序-初始化栈顶指针为01.头文件类型定义2.顺序类型定义3.函数声明4.基本操作4.1 初始化顺序4.2 判空4.3 入栈4.4 出栈4.5 读取栈顶元素4.6 main函数5.小结 1.头文件类型定义 #include<stdio.h> #...
  • 顺序-初始化栈顶指针为-11.头文件类型定义2.顺序类型定义3.函数声明4.基本操作4.1 初始化顺序4.2 判空4.3 入栈4.4 出栈4.5 读取栈顶元素4.6 main函数5.小结 1.头文件类型定义 #include<stdio.h> #...
  • Java中数组定义与C语言有些不同,初始化方式有以下三种: 1、静态初始化 2、动态初始化 3、数组默认初始化 数组是引用类型,它元素相当于类实例变量,因此数组一经分配空间,其中每个元素也被按照实例...
  • 栈的原理实现

    2020-04-21 17:11:45
    文章目录1 栈的原理2 栈的算法实现2.1 栈数据结构的定义2.2 栈的初始化2.3 入栈2.4 出栈2.5 获取栈顶元素2.6 判断空栈2.7 获取栈中元素个数2.8 销毁栈2.9 测试代码 1 栈的原理 胡同里的小汽车是排成一条直线,是...
  • 数组初始化及小结

    2021-05-20 08:50:46
    :存放基本变量类型(包含这个基本类型具体数值) 堆:存放new对象和数组 静态初始化: 创建+赋值 int[ ] a = {1,2,3,4,5,6};(大括号代表一个数组) 定义之后不可改变了,a长度就确定了,元素个数不可...
  • 栈和队列栈的相关概念顺序栈的表示实现栈的抽象数据类型的类型定义顺序栈的表示顺序表的基本操作顺序栈的初始化判断栈是否为空顺序栈的入栈顺序栈的出栈链栈的表示链栈的入栈链栈的出栈队列的基本表示操作顺序...
  • JAVA内存 堆 存放new对象数组 可以被别线程共享,不会存放别等对象引用 ... ...存放基本数据类型(会包含这个基本类型具体数值) ...引用类型变量(会存放这个引用在堆里面...初始化的三种方式 静态初始化 //
  • 实验4、顺序栈的基本操作应用 (1)实验目的 通过该实验,让学生掌握栈的相关基本概念,认识栈是插入和删除集中在一端进行的线性结构,掌握栈的“先入后出”操作特点。栈在进行各类操作时,栈底指针固定不动,掌握...
  • 1.顺序栈的存储结构定义 #define StackSize 100 //假设栈元素最多100个 typedef int DataType;//定义栈元素的数据类型,假设为int型 ...2.顺序栈的初始化 void InitStack(SeqStack * s){ s->...
  • 静态属性:随类存在而存在,是在类加载的初始化 非静态属性:随实例属性存在而存在。 局部变量: 局部变量不能加static,包括protected, private, public这些也不能加。局部变量保存在中。 局部编程必须在...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 412
精华内容 164
关键字:

栈的定义及初始化