精华内容
下载资源
问答
  • 前言栈是一种应用广泛的数据结构,例如函数的调用就需要使用栈,其实我们在介绍《快速排序优化详解》的时候也使用到了栈结构。...入栈(PUSH),将一个元素压入栈中,访问栈顶元素(TOP),判断栈是否为空等。栈的实现栈...

    前言

    栈是一种应用广泛的数据结构,例如函数的调用就需要使用栈,其实我们在介绍《快速排序优化详解》的时候也使用到了栈结构。栈最鲜明的特点就是后进先出,一碟盘子就是类似这样的结构,最晚放上去的,可以最先拿出来。本文将介绍的是如何自己实现一个栈结构。

    栈的操作

    栈的常见操作有出栈(POP),从栈中弹出一个元素;入栈(PUSH),将一个元素压入栈中,访问栈顶元素(TOP),判断栈是否为空等。

    栈的实现

    栈是较容易实现的抽象数据结构之一。我们可以选择数组或者链表来实现,它们各有特点,前者容量有限且固定,但操作简单,而后者容量理论上不受限,但是操作并不如数组方便,每次入栈要进行内存申请,出栈要释放内存,稍有不慎便造成内存泄露。本文对两种实现都做介绍。

    数组实现栈

    用数组实现栈是比较容易的。这个时候的栈其实更像是访问受限的数组,数组可以通过下标访问,查找,插入等,但是栈只能从栈顶,或者说数组的末尾进行操作。我们只需要一个指针记录栈顶即可。有人可能问了,既然这里栈是访问受限的数组,为什么不直接使用数组呢?所谓能力越大,责任越大,而你暴露的越多,风险也越大就是如此。

    我们来看一下数组实现栈的时候,栈的操作都是怎么实现的呢?

    定义栈

    用数组实现栈时是很容易定义的,只要定一个固定长度的数组即可,然后使用一个指针或者数组下标标记栈顶(topOfStack),栈为空时,它是-1:

    #define STACK_SIZE 64 /*栈大小*/
    #define TOP_OF_STACK -1 /*栈顶位置*/
    typedef int ElementType /*栈元素类型*/
    typedef struct StackInfo
    {

        int topOfStack; /*记录栈顶位置*/
        ElementType stack[STACK_SIZE]; /*栈数组,也可以使用动态数组实现*/
    }StackInfo_st;

    /*创建栈*/
    StackInfo_st stack;
    stack.topOfStack = TOP_OF_STACK;

    入栈

    入栈操作也很简单,只需要先将topOfStack加1,然后将元素放入数组即可。当然特别要注意检查此时栈是否已满。
    topOfStack = -1

    将1入栈,此时topOfStack = 0,

    topOfStack
    1

    代码实现:

    #define SUCCESS 0
    #define FAILURE -1
    /*入栈,0表示成功,非0表示出错*/
    int stack_push(StackInfo_st *s, ElementType value){
        if(stack_is_full(s))
            return FAILURE;
        /*先增加topOfStack,再赋值*/
        s->topOfStack++;
        s->stack[s->topOfStack] = value;
        return SUCCESS;
    }

    出栈或访问栈顶元素

    与入栈相反,先访问元素,然后将topOfStack减1,但是此时要注意检查栈是否已空。访问栈顶元素可直接使用下标访问,而不用将topOfStack减1。

    /*出栈*/
    int stack_pop(StackInfo_st *s,ElementType *value){
        /*首先判断栈是否为空*/
        if(stack_is_empty(s))
            return FAILURE;
        *value = s->stack[s->topOfStack];
        s->topOfStack--;
        return SUCCESS;
    }
    /*访问栈顶元素*/
    int stack_top(StackInfo_st *s,ElementType *value);
    {
        /*首先判断栈是否为空*/
        if(stack_is_empty(s))
            return FAILURE;
        *value = s->stack[s->topOfStack];
        return SUCCESS;
    }

    判断栈是否满

    只要判断topOfStack与数组大小-1的大小即可。

    /*判断栈是否已满,满返回1,未满返回0*/
    int stack_is_full(StackInfo_st *s){
        return s->topOfStack == STACK_SIZE - 1;
    }

    判断栈是否为空

    只需要判断topOfStack是否小于等于-1即可。

    /*判断栈是否为空,空返回1,非空返回0*/
    int stack_is_empty(StackInfo_st *s){
        return s->topOfStack ==  - 1;
    }

    完整可运行代码

    代码较长,可点击阅读原文查看或访问:
    https://www.yanbinghu.com/2019/03/16/31765.html

    链表实现栈

    与数组实现栈不一样的地方是,链式栈可以动态扩容,基本没有长度限制(受限于内存)。另外,它在入栈以及出栈的时候需要申请或者释放内存。

    创建栈

    创建栈很容易,只需要声明一个头指针即可,它的next指针指向栈顶,初始时为空:

    /*定义栈结构*/
    typedef struct StackInfo
    {

        ElementType value; /*记录栈顶位置*/
        struct StackInfo *next; /*指向栈的下一个元素*/
    }StackInfo_st;

    /*创建栈,外部释放内存*/
    StackInfo_st *createStack(void){
        StackInfo_st *stack = malloc(sizeof(StackInfo_st));
        if(NULL == stack)
        {
            printf("malloc failed\n");
            return NULL;
        } 
            /*stack-next为栈顶指针*/
        stack->next = NULL;
        return stack;
    }

    入栈

    入栈只需要为新的元素申请内存空间,并将栈顶指针指向新的节点即可。

    53dfa233d39408b5b26c0d78da6171d0.png
    入栈操作
    /*入栈,0表示成功,非0表示出错*/
    int stack_push(StackInfo_st *s,ElementType value){
        StackInfo_st *temp = malloc(sizeof(StackInfo_st));
        if(NULL == temp)
        {
            printf("malloc failed\n");
            return FAILURE;
        }
        /*将新的节点添加s->next前,使得s->next永远指向栈顶*/
        temp->value = value;
          temp->next = s->next;
        s->next = temp;
        return SUCCESS;
    }

    出栈或访问栈顶元素

    出栈时,将栈顶指针指向下下个节点,返回元素值,并释放栈顶指针下个节点的内存。而访问栈顶元素只需要返回栈顶指针指向节点的元素值即可。

    fa4acaa0ef433b6b734ce37551992012.png
    出栈
    /*出栈*/
    int stack_pop(StackInfo_st *s,ElementType *value){
        /*首先判断栈是否为空*/
        if(stack_is_empty(s))
            return FAILURE;

        /*找出栈顶元素*/
        *value = s->next->value;
        StackInfo_st *temp = s->next;
        s->next = s->next->next;

        /*释放栈顶节点内存*/
        free(temp);
        temp = NULL;

        return SUCCESS;
    }
    /*访问栈顶元素*/
    int stack_top(StackInfo_st *s,ElementType *value){
        /*首先判断栈是否为空*/
        if(stack_is_empty(s))
            return FAILURE;
        *value = s->next->value;
        return SUCCESS;
    }

    判断栈是否为空

    判断栈空也很简单,只需要判断栈顶指针是否为空即可。

    /*判断栈是否为空,空返回1,未空返回0*/
    int stack_is_empty(StackInfo_st *s){
        /*栈顶指针为空,则栈为空*/
        return s->next == NULL;
    }

    完整可运行代码

    代码较长,可点击阅读原文查看或访问:
    https://www.yanbinghu.com/2019/03/16/31765.html

    总结

    本文介绍了栈的基本操作以及栈的基本实现。后面将会介绍一些栈的具体应用。

    思考

    还记得如何使用GDB查看链表内容吗?参考《GDB调试指南-变量查看》。

    关注公众号【编程珠玑】,获取更多Linux/C/C++/Python/Go/算法/工具等原创技术文章。

    c1dc522d5b894637d31bced622fadc37.png

    展开全文
  • 栈与队列--判断栈/队列为空/满

    万次阅读 2016-06-28 10:24:15
    完成int IsEmpty(Stack S)函数,该函数判断栈是否,如果返回1,否则返回0。 完成int IsFull(Stack S)函数,该函数判断栈是否已满,如果满返回1,否则返回0。typedef int ElemType; struct StackRecord; ...

    数组栈
    完成int IsEmpty(Stack S)函数,该函数判断栈是否已空,如果空返回1,否则返回0。
    完成int IsFull(Stack S)函数,该函数判断栈是否已满,如果满返回1,否则返回0。

    typedef int ElemType;
    struct StackRecord;
    typedef struct StackRecord *Stack;
    struct StackRecord
    {
        int Capacity; //栈容量
        int Top; //栈顶,初始为1
        ElemType *Array;
    };
    
    int IsEmpty(Stack S)
    {
        if(S‐>Top==‐1)
        {
            return 1;
        } 
        else
        {
            return 0;
        }
    }
    int IsFull(Stack S)
    {
        if(S‐>Top==S‐>Capacity‐1)
        {
            return 1;
        } 
        else
        {
            return 0;
        }
    }

    链栈
    完成int IsEmpty(Stack S);函数,该函数判断栈S是否为空,空栈返回1,否则返回0,已知S是带头结点的链栈。

    typedef int ElemType;
    struct Node;
    typedef struct Node * PtrToNode;
    typedef PtrToNode Stack;
    struct Node
    {
        ElemType data;
        PtrToNode next;
    };
    
    int IsEmpty(Stack S)
    {
        return S‐>next==NULL?1:0;
    }

    数组队列
    完成int IsEmpty(Queue Q);函数,该函数判断队列Q是否已空,如果已空返回1,否则返回0,其中Q是基于数组的非循环队列。
    完成int IsFull(Queue Q)函数,该函数判断队列Q是否已满,如果已满返回1,否则返回0,其中Q是基于数组的非循环队列。

    typedef int ElemType;
    struct QueueRecord;
    typedef struct QueueRecord * Queue;
    struct QueueRecord
    {
        int Capacity; //队列总容量
        int Front; //队首 初始值为0
        int Rear; //队尾,初始值为1
        int Size; //队列中数据数,初始值为0
        ElemType *Array;
    };
    
    int IsEmpty(Queue Q)
    {
        return Q‐>Size==0;
    }
    int IsFull(Queue Q)
    {
        return Q‐>Rear==Q‐>Capacity‐1?1:0;
    }

    链队列
    完成int IsEmpty(Queue q)函数,该函数判定基于链表的队列q是否为空,空队列返回1,非空队列返回0,其中q是不带头节点的链表队列。

    typedef int ElemType;
    struct node;
    typedef struct node Node;
    struct queue;
    typedef struct queue * Queue;
    struct node
    {
        ElemType data;
        Node * next;
    };
    struct queue
    {
        Node * front; //队首
        Node * rear; //队尾
        int size; //队列中数据数int IsEmpty(Queue q)
    {
        return q‐>size==0?1:0;
    }
    展开全文
  • 函数递归调用中的地址和参数值的保存,文本编辑器中序列的保存,在编译软件设计中的括号匹配及表达式求值,网页访问历史的记录保存下面通过讨论及格式结构的具体应用来说明在解决实际问题中的运用:(一)判断分隔...

    栈是软件系统应用最广泛的数据结构之一,只要涉及先进后出的处理特征都可以使用栈结构。

    例如:函数递归调用中的地址和参数值的保存,文本编辑器中序列的保存,在编译软件设计中的括号匹配及表达式求值,网页访问历史的记录保存

    下面通过讨论及格栈式结构的具体应用来说明栈在解决实际问题中的运用:

    (一)判断分隔符是否合理

    算法如下:

    从左到右扫描java语句,不断读出java字符,若读出为左字符,则将其写入栈中,若读出为右字符,则将栈中左字符pop出并匹配,若不匹配或者没有左字符与右字符匹配,

    则程序报错

    把java语句读完后,若栈仍不为空,(没有右字符与栈中左字符匹配),则程序报错;若栈为空,则表示程序正常

    import java.util.Scanner;

    import java.util.Stack;

    //判断分隔符匹配问题

    public class Example3_1 {

    private final int LEFT=0;

    private final int RIGHT=1;

    private final int OTHER=2;

    //判断分隔符类型,有左,右,不合法三红类型

    public int verifyFlag(String str){

    if("(".equals(str)||"[".equals(str)||"{".equals(str)||"/*".equals(str))

    {return LEFT;}

    else if(")".equals(str)||"]".equals(str)||"}".equals(str)||"*/".equals(str)){

    return RIGHT;

    }

    else

    return OTHER;

    }

    //判断左右分隔符是否匹配

    public boolean match(String str1,String str2){

    if("(".equals(str1)&&")".equals(str2)||"[".equals(str1)&&"]".equals(str2)||

    "{".equals(str1)&&"}".equals(str2)||"/*".equals(str1)&&"*/".equals(str2)){

    return true;

    }

    else

    return false;

    }

    //判断左右分隔符是否匹配

    public boolean isLegal(String str) throws Exception{

    if(!"".equals(str)&&str!=null){

    //新建最大储存空间为100的顺序栈

    Stack stack=new Stack<>();

    int length=str.length();

    //判断是否为/* 或者*/,如果是将其放入t中

    for(int i=0;i

    char c=str.charAt(i);//将索引到的元素转换为char类型

    String t=String.valueOf(c);//将char类型转换为String类型

    if(i!=length){

    if(('/'==c&&'*'==str.charAt(i+1))||'*'==c&&'/'==str.charAt(i+1)){

    t=t.concat(String.valueOf(str.charAt(i+1)));//将其连接成String类型

    ++i;

    }

    }

    if(LEFT==verifyFlag(t)){

    stack.push(t); //如果为左分隔符,则放入栈中

    }

    else if(RIGHT==verifyFlag(t)){

    //如果为右分隔符

    if(stack.isEmpty()||!match(stack.pop(), t)){

    throw new Exception("错误,java语句不合法");

    }

    }

    }if(!stack.isEmpty()){

    throw new Exception("错误,java语句不合法");

    }

    return true;

    }

    else throw new Exception("错误,java语句为空");

    }

    public static void main(String[] args) throws Exception {

    // TODO Auto-generated method stub

    Example3_1 e=new Example3_1();

    System.out.println("请输入java语句");

    Scanner sc=new Scanner(System.in);

    if(e.isLegal(sc.nextLine())){

    System.out.println("java语句合法");

    }else

    System.out.println("java语句不合法");

    }

    }运行结果如下:

    请输入java语句

    a=(a+c(d*e)*f+sa;

    Exception in thread "main" java.lang.Exception: 错误,java语句不合法

    at stack.Example3_1.isLegal(Example3_1.java:59)

    at stack.Example3_1.main(Example3_1.java:74)

    请输入java语句

    a+(c+d)*d

    java语句合法

    展开全文
  • 顺序栈,遵循先进后出后进先出原则。我在写的时候,宏定义的 firstsize 为创建一个栈时这个栈的初始大小,这里为100。...栈是否为空,print函数用来出栈。 //以下为全部代码 #include "stdio.h" #include "mall...

    顺序栈,遵循先进后出后进先出原则。我在写的时候,宏定义的
    firstsize 为创建一个栈时这个栈的初始大小,这里为100。addsize
    为当栈满时,再想入栈的话每次栈大小的增量,这里用10来代替。
    create函数为创建栈函数。push为入栈函数。empty函数用来判断
    栈是否为空,print函数用来出栈。
    //以下为全部代码

    #include "stdio.h"
    #include "malloc.h"
    #define firstsize 100
    #define addsize 10
    typedef struct{
     int *base;
     int *top;
     int size;
    }Sq;
    
    void create(Sq &s)
    {
     s.base=(int*)malloc(firstsize*sizeof(int));
     if(s.base)printf("create OK!\n");
     s.top=s.base;
     s.size=firstsize;
    }
    
    void push(Sq &s,int e)
    {
     if(s.top-s.base>=s.size)
     {
     s.base=(int*)realloc(s.base,(s.size+addsize)*sizeof(int));
     printf("栈内空间分配成功\n");
     }
     *s.top=e;
     s.top++;
     printf("元素[%d]已入栈!\n",e);
    }
    
    void print(Sq &s)
    {
     if(empty(s))printf("抱歉,栈已满,无法出栈\n");
     else
     {
       s.top--;
       printf("出栈:[%d]\n",*s.top);
      }
    }
    
    int empty(Sq &s)
    {
     if(s.top==s.base||s.top<s.base)
     { printf("栈空\n");
     return 1;}
     else {printf("栈未空\n");
     return 0;}
    }
    
    void main()
    {
    int i; Sq s;
    do
    {
    printf("\n----------------\n1-");
    printf("创建一个栈\n2-判断栈是否为空\n3-入栈\n4-出栈\n0-退出");
    printf("\n----------------\n\n");
    scanf("%d",&i);
    switch(i)
    {
     case 1:create(s);break;
     case 2:empty(s);break;
     case 3:
     {
     int e;
     printf("输入入栈元素:\n");
     scanf("%d",&e);
     push(s,e);
     }break;
     case 4:print(s);break;
     case 0:break;
     default:
     {printf("输入错误,请重新输入\n");
     }continue;
     }
     }while(i!=0);
     printf("程序已退出\n");
    }
    
    
    

    运行结果:sxz

    展开全文
  • C++中与队列的函数

    2020-12-22 20:17:59
    判断栈是否为空;为布尔型、输出为零或一;  q.top(); 取出栈顶元素;例如j=q.top();  q.size(); 栈中元素的个数;  队列的应用:  头文件include  定义队列  queue<type>q;  比较常用的函数:  ...
  • 前言栈是一种应用广泛的数据结构,例如函数的调用就需要使用栈,其实我们在介绍《快速排序优化详解》的时候也使用到...入栈(PUSH),将一个元素压入栈中,访问栈顶元素(TOP),判断栈是否为空等。栈的实现栈是较容易实...
  • 前言栈是一种应用广泛的数据结构,例如函数的调用就需要使用栈,其实我们在介绍《快速排序优化详解》的时候也使用到...入栈(PUSH),将一个元素压入栈中,访问栈顶元素(TOP),判断栈是否为空等。栈的实现栈是较容易实...
  • 判断栈是否为空。 S.push(x);将x入栈 S.pop();弹出栈顶 S.size();栈的存储元素个数 2.队列常用函数 Q.empty()判断队列是否为空 Q.front()返回队列头部元素 Q.back()返回队列尾部元素 Q.pop()弹出队列头部元素 Q....
  • C++数据结构之栈的实现(顺序栈) 首先我们定义了一个栈模板类,它有几个纯虚函数...同样我们定义了判断栈是否为空函数IsEmpty(),以及保护成员—栈的高度(长度)height; 模板类定义代码如下 template<class typ...
  • 包含min函数

    2019-09-24 21:15:44
    思路:借助一个辅助栈,压入时判断辅助栈是否为空或者要压入的元素比栈顶元素小,弹出是判断,要弹出元素是否为辅助栈栈顶,是则弹出。min函数则是返回辅助栈栈顶元素。 代码: class Solution { private: ...
  • 1.栈 #coding=gbk #栈的常用操作 # Stack() 建立一个空的栈对象 # push() 把一个元素添加到栈的最顶层 ...# isEmpty() 判断栈是否为空 # size() 返回栈中元素的个数 #使用Python中的列表进行对栈的实...
  • stack #include<bits/stdc++.h> using namespace srd; int main(){ stack <int> a;//创建 a.top();//返回顶层元素 a.pop();//弹出顶层元素 ...//返回内元素个数 ...//判断是否为空 } ...
  • 021包含min函数的栈 ...push:data栈直接push,判断min栈是否为空,为空直接push,不为空,判断要插入的元素是否小于最上面的元素,小于就插入。 pop:判断如果data栈的最顶部元素跟min栈的最顶部元素...
  • 20包含min函数

    2020-02-17 19:19:09
    题目描述 定义的数据结构,请在该类型中实现一个...push时,数据直接push,最小值需要判断是否空则直接push,非空判断minStack的栈顶元素值和node值的大小。栈顶大就再压入一次栈顶元素,node大就压入node...
  • 的基本概念以及java实现

    千次阅读 2018-08-09 08:37:04
    判断栈是否为空 清空栈 链式栈 构造函数 压栈 出栈 查询栈顶元素 判断栈是否为空 清空栈 顺序栈与链式栈的比较 代码传送门,欢迎star:https://github.com/mcrwayfun/java-data-structure 1. 栈的基本...
  • 包含min函数,就是能查询到里面的最小值是多少思路:定义一个数组element来存放数,定义一个minStack来存放每个元素对应的最小值,min记录当前最小值,用size来表明当前大小,用ensureCapacity来判断是否需要扩...
  • 19 包含min函数

    2017-12-05 22:59:00
    思路:一个存普通元素,一个最小存放目前位置最小的元素,只在压入的时候判断是否为空以及最小元素,其他情况正常处理。 class Solution { public: void push(int value) { s.push(value); ...
  • 2020-04-27 16:12:19
    本节讲栈,然后讲一道关于pat的题目。数据结构或许才能有算法吧! 栈 初始化init 压栈push 弹栈pop 看栈顶元素top。 讲一讲关于其中的细节:...判断栈是否为空。也可以去通过使用函数去进行封装起来 看栈顶元素: 其...
  • stack s; //定义一个名为s,保存整形元素的栈 ... //判断栈是否为空,空则返回true s.size(); //返回栈中包含的元素个数 queue q; //定义一个名为q, 保存整形元素的队列 q.push(i
  • //1.括号匹配 /* 取一个字符: 1.检测该字符是否为括号: 是括号,继续1,否则返回 ...栈是否为空: 空:正确 非空:左比右括号多 */ int IsBrackets(char ch)//判断括号函数 { if (('(' == ch) || (')' == ...
  • class Solution { public: void push(int value) { st.push(value);//主输入一个数 if(smin.empty())//判断辅助2是否为空,如果为空直接入栈 { smin.push(value); } else//...
  • 题目描述 定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度...push函数中,对于A来说,直接使用append方法添加到末尾,对于B需要判断栈中最后一个元素是否大于新元素,从而决...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 330
精华内容 132
关键字:

判断栈是否为空函数