Java数据结构之栈的详解

目录
  • 栈的抽象定义
  • 顺序栈-----------使用数组表示栈空间
  • 总结

栈是先进后出的特殊线性表,只允许在表的末端进行插入和删除,后面将介绍两种实现栈的方式,分别是基于数组的实现、基于链表的实现。

栈的抽象定义

class Mystack
{
public:
	Mystack() {}
	virtual void push(int &x) = 0;
	virtual bool pop(int &x) = 0;
	virtual bool Top(int &x) const = 0;
	virtual bool IsEmpty()const = 0;
	virtual bool IsFull()const = 0;
	virtual int getSize()const = 0;
};

顺序栈-----------使用数组表示栈空间

定义:

#pragma once
#include "Mystack.h"
#include <iostream>
#include <assert.h>
using namespace std;
const int stackIncreament = 20;

class SeqStack : public Mystack
{
public:
	SeqStack(int sz = 50);                 //建立一个空栈
	~SeqStack() { delete[]elements; }      //析构函数
	//如果栈满,则溢出程序处理,否则插入x
	void push(int &x);
	//如果栈空,则返回FALSE,否则使用x传递栈顶的值,top-1
	bool pop(int &x);
	//如果栈空,则返回FALSE,否则使用x传递栈顶的值
	bool Top(int &x);
	//判断栈是否为空
	bool IsEmpty()const {
		return (top == -1) ? true : false;
	}
	//判断栈是都为满
	bool IsFull()const {
		return (top == maxSize - 1) ? true : false;
	}
	//获取栈当前的size
	int getSize()const {
		return top + 1;
	}
	//将栈置空
	void MakeEmpty() {
		top = -1;
	}
	//重载 操作 <<
	friend ostream& operator<<(ostream& os, SeqStack& s);

private:
	int *elements;				//栈数组指针
	int top;					//栈顶指针
	int maxSize;				//栈的最大容量
	void overflowProcess();		//溢出处理程序
};

实现:

#include "SeqStack.h"

SeqStack::SeqStack(int sz):top(-1),maxSize(sz)
{
	elements = new int[maxSize];		//创建栈的数组空间
	assert(elements == NULL);            //断言:动态分配是否成功
}
void SeqStack::push(int & x)
{
	//首先判断栈是否已满,满则转入溢出处理
	if(IsFull() == true){
		overflowProcess();
	}
	elements[++top] = x;    //将top+1,再插入值x
}
bool SeqStack::pop(int & x)
{
	//先判断是否为空,为空则返回FALSE
	if (IsEmpty() == true) {
		return false;
	}
	x = elements[top--];     //使用x返回top所指,再讲top-1
	return true;
}
bool SeqStack::Top(int & x)
{
	//空栈则为FALSE
	if (IsEmpty() == true) {
		return false;
	}
	//栈不为空,则返回栈顶元素的值
	x = elements[top];
	return true;
}
ostream& operator<<(ostream& os, SeqStack& s) {
	//输出栈中元素
	os << "top = " << s.top << endl;
	for (int i = 0; i <= s.top; ++i) {
		os << i << ": " << s.elements[i] << endl;
	}
	return os;
}

void SeqStack::overflowProcess()
{
	//栈溢出时,扩充栈的存储空间
	int *Newelement = new int[maxSize + stackIncreament];
	if (Newelement == NULL) {
		cout << "分配内存失败";
		exit(1);
	}
	for (int i = 0; i <= top; ++i) {
		Newelement[i] = elements[i];
	}
	delete[] elements;
	elements = Newelement;
}

总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • Java如何自定义异常打印非堆栈信息详解

    前言 在学习Java的过程中,想必大家都一定学习过异常这个篇章,异常的基本特性和使用这里就不再多讲了.什么是异常?我不知道大家都是怎么去理解的,我的理解很简单,那就是不正常的情况,比如我现在是个男的,但是我却有着女人所独有的东西,在我看来这尼玛肯定是种异常,简直不能忍.想必大家都能够理解看懂,并正确使用. 但是,光学会基本异常处理和使用不够的,在工作中出现异常并不可怕,有时候是需要使用异常来驱动业务的处理,例如: 在使用唯一约束的数据库的时候,如果插入一条重复的数据,那么可以通过捕获唯一约束异常

  • JAVA基于静态数组实现栈的基本原理与用法详解

    本文实例讲述了JAVA基于静态数组实现栈.分享给大家供大家参考,具体如下: 1.栈的定义 栈是一种"先进后出"的一种线性数据结构,有压栈出栈两种操作方式.如下图: 2.栈的分类 栈主要分为两类: 静态栈 动态栈 [静态栈] 静态栈的核心是数组,类似于一个连续内存的数组,我们只能操作其栈顶元素. [动态栈] 静态栈的核心是数组,类似于一个连续内存的数组,我们只能操作其栈顶节点. 此节我们在我们之前封装的动态数组的基础上(引用封装好的动态数组),实现基本的栈操作. 3.栈实现 1.先定义一

  • Java基于链表实现栈的方法详解

    本文实例讲述了Java基于链表实现栈的方法.分享给大家供大家参考,具体如下: 在上几小节中我们实现了基本的链表结构,并在上一节的底部给出了有关链表的源码,此处在贴一次吧,猛戳 在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加.删除.查找操作,时间复杂度均为O(1),基于链表的这几个优势,我们在此基础上实现栈. 前言,在写本小节之前,我们已经实现了一个基于静态数组的栈,转到查看.此处我们实现基于链表的栈. 1.链表类拷贝到Stack 包下: 在实现基于静态数组的栈的时候,我们已经新建了

  • 详解Java线程堆栈

    写在前面: 线程堆栈应该是多线程类应用程序非功能问题定位的最有效手段,可以说是杀手锏.线程堆栈最擅长与分析如下类型问题: 系统无缘无故CPU过高. 系统挂起,无响应. 系统运行越来越慢. 性能瓶颈(如无法充分利用CPU等) 线程死锁.死循环,饿死等. 由于线程数量太多导致系统失败(如无法创建线程等). 如何解读线程堆栈 如下面一段Java源代码程序: package org.ccgogoing.study.stacktrace; /** * @Author: LuoChong400 * @Des

  • Java数据结构之栈的线性结构详解

    目录 一:栈 二:栈的实现 三:栈的测试 四:栈的应用(回文序列的判断) 总结 一:栈 栈是限制插入和删除只能在一个位置上进行的表,此位置就是表的末端,叫作栈顶. 栈的基本操作分为push(入栈) 和 pop(出栈),前者相当于插入元素到表的末端(栈顶),后者相当于删除栈顶的元素. 二:栈的实现 public class LinearStack { /** * 栈的初始默认大小为10 */ private int size = 5; /** * 指向栈顶的数组下标 */ int top = -1

  • 详解java中jvm虚拟机栈的作用

    jvm虚拟机栈的作用 jvm虚拟机栈栈帧的组成 jvm虚拟机栈,也叫java栈,它由一个个的栈帧组成,而栈帖由以下几个部分组成 局部变量表-存储方法参数,内部使用的变量 操作数栈-在变量进行存储时,需要进行入栈和出栈 动态连接-引用类型的指针 方法出口-方法的返回 一段原程序代码 package com.lind.basic; public class Demo1 { static int hello() { int a = 1; int b = 2; int c = a + b; return

  • Java数据结构之栈的详解

    目录 栈的抽象定义 顺序栈-----------使用数组表示栈空间 总结 栈是先进后出的特殊线性表,只允许在表的末端进行插入和删除,后面将介绍两种实现栈的方式,分别是基于数组的实现.基于链表的实现. 栈的抽象定义 class Mystack { public: Mystack() {} virtual void push(int &x) = 0; virtual bool pop(int &x) = 0; virtual bool Top(int &x) const = 0; vi

  • Java数据结构之堆(优先队列)详解

    目录 堆的性质 堆的分类 堆的向下调整 堆的建立 堆得向上调整 堆的常用操作 入队列 出队列 获取队首元素 TopK 问题 例子 数组排序 堆的性质 堆逻辑上是一棵完全二叉树,堆物理上是保存在数组中 . 总结:一颗完全二叉树以层序遍历方式放入数组中存储,这种方式的主要用法就是堆的表示. 并且 如果已知父亲(parent) 的下标, 则: 左孩子(left) 下标 = 2 * parent + 1; 右孩子(right) 下标 = 2 * parent + 2; 已知孩子(不区分左右)(child

  • Java数据结构之单链表详解

    一.图示 二.链表的概念及结构 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 . 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构: 单向.双向 带头.不带头 循环.非循环 今天,我们实现的是一个 单向 无头 非循环的链表. 下面是此链表的结构组成. 三.单链表的实现 (1)定义一个节点类型 我们创建一个 ListNode 的类作为节点类型,那么我们如何定义成员属性呢? 通过上面的结构分析,我们需要定义两个成员变量 val --作为该节点的

  • Java数据结构顺序表用法详解

    目录 1.什么是顺序表 2.顺序表的基本功能和结构 3.顺序表基本功能的实现和解析 1.判断线性表是否为空 2.获取指定位置的元素 3.向线性表表添加元素 4.在位置i处插入元素 5.删除指定位置的元素,并返回该元素 6.查找t第一次出现的位置 7.手动扩容方法 1.什么是顺序表 在程序中,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等.一组数据中包含的元素个数可能发生变化(可以增加或删除元素). 对于这种需求,最简单的解决方

  • Java数据结构之散列表详解

    目录 介绍 1 散列表概述 1.1 散列表概述 1.2 散列冲突(hash collision) 2 散列函数的选择 2.1 散列函数的要求 2.2 散列函数构造方法 3 散列冲突的解决 3.1 分离链接法 3.2 开放定址法 3.3 再散列法 4 散列表的简单实现 4.1 测试 介绍 本文详细介绍了散列表的概念.散列函数的选择.散列冲突的解决办法,并且最后提供了一种散列表的Java代码实现. 数组的特点是寻址容易,插入和删除困难:而链表的特点是寻址困难,插入和删除容易.而对于tree结构,它们

  • Java数据结构之线段树详解

    目录 介绍 代码实现 线段树构建 区间查询 更新 总结 介绍 线段树(又名区间树)也是一种二叉树,每个节点的值等于左右孩子节点值的和,线段树示例图如下 以求和为例,根节点表示区间0-5的和,左孩子表示区间0-2的和,右孩子表示区间3-5的和,依次类推. 代码实现 /** * 使用数组实现线段树 */ public class SegmentTree<E> { private Node[] data; private int size; private Merger<E> merge

  • java 数据结构并查集详解

    目录 一.概述 二.实现 2.1 Quick Find实现 2.2 Quick Union实现 三.优化 3.1基于size的优化 3.2基于rank优化 3.2.1路径压缩(Path Compression ) 3.2.2路径分裂(Path Spliting) 3.2.3路径减半(Path Halving) 一.概述 并查集:一种树型数据结构,用于解决一些不相交集合的合并及查询问题.例如:有n个村庄,查询2个村庄之间是否有连接的路,连接2个村庄 两大核心: 查找 (Find) : 查找元素所在

  • Java数据结构之KMP算法详解以及代码实现

    目录 暴力匹配算法(Brute-Force,BF) 概念和原理 next数组 KMP匹配 KMP全匹配 总结 我们此前学了前缀树Trie的实现原理以及Java代码的实现.Trie树很好,但是它只能基于前缀匹配实现功能.但是如果我们的需求是:一个已知字符串中查找子串,并且子串并不一定符合前缀匹配,那么此时Trie树就无能为力了. 实际上这种字符串匹配的需求,在开发中非常常见,例如判断一个字符串是否包括某些子串,然后进行分别的处理. 暴力匹配算法(Brute-Force,BF) 这是最常见的算法字符

  • Java数据结构之对象比较详解

    目录 1. PriorityQueue中插入对象 2. 元素的比较 2.1 基本类型的比较 2.2 对象比较的问题 3. 对象的比较 3.1 覆写基类的equals 3.2 基于Comparble接口类的比较 3.3 基于比较器比较 3.4 三种方式的对比 4.集合框架中PriorityQueue的比较方式 本篇博客主要内容: Java中对象的比较 集合框架中PriorityQueue的比较方式 模拟实现PriorityQueue 1. PriorityQueue中插入对象 优先级队列在插入元素

  • Java语言实现数据结构栈代码详解

    近来复习数据结构,自己动手实现了栈.栈是一种限制插入和删除只能在一个位置上的表.最基本的操作是进栈和出栈,因此,又被叫作"先进后出"表. 首先了解下栈的概念: 栈是限定仅在表头进行插入和删除操作的线性表.有时又叫LIFO(后进先出表).要搞清楚这个概念,首先要明白"栈"原来的意思,如此才能把握本质. "栈"者,存储货物或供旅客住宿的地方,可引申为仓库.中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈.出栈的说法. 实现方式是

随机推荐