数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码)

这篇具有很好参考价值的文章主要介绍了数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码),数据结构,数据结构,栈,java,原理,实现,c++


前言:在前面的文章中,我们讲解了顺序表,单链表,双向链表。而我们今天要分享的栈则是基于之前的数据结构上搭建的,但是相较于顺序表和链表来说,栈的实现就非常简单了。

目录

一.栈(Stack)的概念

二.栈的数据结构

三.栈的实现

判断栈已满

判断栈非空

入栈push

出栈pop

查看栈顶元素

完整代码

Java版本

c语言版


一.栈(Stack)的概念

栈是一种先进后出(LIFO)的数据结构,在其中元素的的添加(称为“入栈”)和删除(称为“出栈”)仅在栈的顶部进行。因此,最后一个插入到栈中的元素是第一个从栈中删除的元素。

它通常有两个主要操作:

  • push:在栈的顶部插入一个元素。
  • pop:从栈的顶部移除一个元素。

栈的push入栈图解:

数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码),数据结构,数据结构,栈,java,原理,实现,c++

栈的pop出栈图解 :

数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码),数据结构,数据结构,栈,java,原理,实现,c++

我们可以看见对于栈的操作,我们都是在栈顶上操作的,先进来的元素会被后面的元素覆盖,而最后一个进来的元素也就是栈顶,因此我们称为先进后出(LIFO)

像传统的狙击步枪的弹夹就属于是一种栈的结构 

数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码),数据结构,数据结构,栈,java,原理,实现,c++


二.栈的数据结构

对于栈的实现,我们通常使用数组,当然也可以使用链表,不过相对而言数组的实现是更容易的。

而对于一个栈的数据结构,他首先得有存放元素的位置,我们这里选择用数组来存放,其次还得有栈内元素个数的记录:

public class MyStack {
    public int[] elem;
    public int usedSize;
}

三.栈的实现

对于一个栈,他应该有以下这些功能:

  • 入栈
  • 出栈
  • 判断栈是否为空
  • 判断栈已满
  • 查看栈顶元素

判断栈已满

当已经使用的数组的大小等于数组本身的大小的时候,栈就相当于满了

    public boolean isFull() {
        return usedSize == elem.length;
    }

判断栈非空

当数组内一个元素都没有,也就是已经使用的数组大小为0的时候,栈就是空的

    public boolean isEmpety() {
        return usedSize == 0;
    }

入栈push

当我们要将元素放入栈内的时候,先进行判断,只有在栈内还有剩余空间的情况下,我们才会进行入栈操作,如果没有剩余空间,我们就进行扩容

数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码),数据结构,数据结构,栈,java,原理,实现,c++

    public void push(int val) {
        if (isFull()) {
            //扩容
            elem = Arrays.copyOf(elem, elem.length * 2);
        }
        elem[usedSize++] = val;
    }

出栈pop

出栈前要先进行判断,如果栈内一个元素都没有,那自然是不能进行出栈操作的,我们就抛出一个自定义异常然后抛出;对于正常的出栈操作,我们拿出栈顶的元素,然后让记录数组的个数减一

    public int pop() {
        if (isEmpety()) {
            //栈为空,无法出栈
            throw new EmptyStackException("栈为空,无法弹出");
        }
        int popNumber = elem[usedSize-1];
        usedSize--;
        return popNumber;
    }

查看栈顶元素

和出栈不一样的是,查看栈顶元素只是将元素拿出来展示,并没有实际上删除这个元素

    public int peek() {
        if (isEmpety()) {
            //栈为空,无法出栈
            throw new EmptyStackException("栈为空,无法弹出");
        }
        return elem[usedSize - 1];
    }

完整代码

栈的整体实现相较于顺序表和链表是非常简单的,这里附上完整代码

Java版本

import java.util.Arrays;

public class MyStack {
    public int[] elem;
    public int usedSize;
    public static int DEFULT_SIZE = 10;
    
    public MyStack() {
        this.elem = new int[DEFULT_SIZE];
    }
    
    public void push(int val) {
        if (isFull()) {
            //扩容
            elem = Arrays.copyOf(elem, elem.length * 2);
        }
        elem[usedSize++] = val;
    }
    
    public int pop() {
        if (isEmpety()) {
            //栈为空,无法出栈
            throw new EmptyStackException("栈为空,无法弹出");
        }
        int popNumber = elem[usedSize-1];
        usedSize--;
        return popNumber;
    }
    
    public int peek() {
        if (isEmpety()) {
            //栈为空,无法出栈
            throw new EmptyStackException("栈为空,无法弹出");
        }
        return elem[usedSize - 1];
    }
    
    public boolean isFull() {
        return usedSize == elem.length;
    }
    
    public boolean isEmpety() {
        return usedSize == 0;
    }

}

c语言版

#include <stdio.h>
#include <stdlib.h>

#define STACK_SIZE 10

// 定义栈结构体
typedef struct {
    int data[STACK_SIZE];  // 存放数据的数组
    int top;               // 栈顶指针
} Stack;

// 初始化栈
void init_stack(Stack *s) {
    s->top = -1;  // 栈顶初始化为-1
}

// 判断栈是否为空
int is_empty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int is_full(Stack *s) {
    return s->top == STACK_SIZE-1;
}

// 入栈
void push(Stack *s, int value) {
    if (is_full(s)) {
        printf("Stack overflow\n");
        exit(1);
    }
    s->data[++s->top] = value;  // 栈顶指针先加1,再将元素入栈
}

// 出栈
int pop(Stack *s) {
    if (is_empty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->data[s->top--];  // 先将元素出栈,再将栈顶指针减1
}

// 获取栈顶元素
int peek(Stack *s) {
    if (is_empty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->data[s->top];
}




 数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码),数据结构,数据结构,栈,java,原理,实现,c++ 本次的分享就到此为止了,希望我的分享能给您带来帮助,也欢迎大家三连支持,你们的点赞就是博主更新最大的动力!数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码),数据结构,数据结构,栈,java,原理,实现,c++如有不同意见,欢迎评论区积极讨论交流,让我们一起学习进步!数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码),数据结构,数据结构,栈,java,原理,实现,c++有相关问题也可以私信博主,评论区和私信都会认真查看的,我们下次再见数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码),数据结构,数据结构,栈,java,原理,实现,c++文章来源地址https://www.toymoban.com/news/detail-754320.html

到了这里,关于数据结构:栈(Stack)的各种操作(入栈,出栈,判断栈非空,判断栈已满,附源码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包