文档章节

数据结构---->栈

小强斋太
 小强斋太
发布于 2016/11/09 20:05
字数 1286
阅读 3
收藏 0
点赞 0
评论 0

栈与队列(一)

栈和队列是两种重要的数据结构。从栈与队列的逻辑结构上来说,它们也是线性结构,与线性表不同的是它们所支持的基本操作是受到限制的,它们是操作受限的线性表,是一种限定性的数据结构。

一、栈

1.1栈的定义和抽象数据类型

栈(stack)又称堆栈,它是运算受限的线性表,其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端称为栈顶(top),栈顶保存的元素称为栈顶元素。相对的,表的另一端称为栈(bottom)。

当栈中没有数据元素时称为空栈;向一个栈插入元素又称为进栈或入栈;从一个栈中删除元素又称为出栈或退栈。由于栈的插入和删除操作仅在栈顶进行,后进栈的元素必定先出栈,所以又把堆栈称为后进先出表(LastIn First Out,简称LIFO)。

一个堆栈及数据元素插入和删除的过程。

Stack接口

package stack;

//Stack 接口
public interface Stack {
	// 返回堆栈的大小
	public int getSize();

	// 判断堆栈是否为空
	public boolean isEmpty();

	// 数据元素e 入栈
	public void push(Object e);

	// 栈顶元素出栈
	public Object pop() throws StackEmptyException;

	// 取栈顶元素
	public Object peek() throws StackEmptyException;
}

其中涉及的异常类定义如下:

StackEmptyException堆栈为空时出栈或取栈顶元素抛出此异常

package stack;

//StackEmptyException 堆栈为空时出栈或取栈顶元素抛出此异常
public class StackEmptyException extends RuntimeException {
	public StackEmptyException(String err) {
		super(err);
	}
}

 

1.2 栈的顺序存储实现

和线性表类似,堆栈也有两种基本的存储结构:顺序存储结构和链式存储结构。

顺序栈是使用顺序存储结构实现的堆栈,即利用一组地址连续的存储单元依次存放堆栈中的数据元素。由于堆栈是一种特殊的线性表,因此在线性表的顺序存储结构的基础上,选择线性表的一端作为栈顶即可。根据数组操作的特性,选择数组下标大的一端,即线性表顺序存储的表尾来作为栈顶,此时入栈、出栈等操作可以在Ο(1)时间完成。

由于堆栈的操作都在栈顶完成,因此在顺序栈的实现中需要附设一个指针top 来动态的指示栈顶元素在数组中的位置。通常top 可以用栈顶元素所在数组下标来表示,top=-1 时表示空栈。堆栈在使用过程中所需的最大空间很难估计,因此,一般来说在构造堆栈时不应设定堆栈的最大容量。一种合理的做法和线性表的实现类似,先为堆栈分配一个基本容量,然后在实际的使用过程中,当堆栈的空间不够时再倍增存储空间,这个过程所需的时间均摊到每个数据元素时间为Θ(1),不会影响操作实现的时间复杂度。

package stack;

public class StackArray implements Stack {
	private final int LEN = 8; // 数组的默认大小
	private Object[] elements; // 数据元素数组
	private int top; // 栈顶指针

	public StackArray() {
		top = -1;
		elements = new Object[LEN];
	}

	// 返回堆栈的大小
	public int getSize() {
		return top + 1;
	}

	// 判断堆栈是否为空
	public boolean isEmpty() {
		return top < 0;
	}

	// 数据元素e 入栈
	public void push(Object e) {
		if (getSize() >= elements.length)
			expandSpace();
		elements[++top] = e;
	}

	private void expandSpace() {
		Object[] a = new Object[elements.length * 2];
		for (int i = 0; i < elements.length; i++)
			a[i] = elements[i];
		elements = a;
	}

	// 栈顶元素出栈
	public Object pop() throws StackEmptyException {
		if (getSize() < 1)
			throw new StackEmptyException("错误,堆栈为空。");
		Object obj = elements[top];
		elements[top--] = null;
		return obj;
	}

	// 取栈顶元素
	public Object peek() throws StackEmptyException {
		if (getSize() < 1)
			throw new StackEmptyException("错误,堆栈为空。");
		return elements[top];
	}
}

1.3 栈的链式存储实现

链栈即采用链表作为存储结构实现的栈。当采用单链表存储线性表后,根据单链表的操作特性选择单链表的头部作为栈顶。

不带头结点的单链表实现堆栈的示意图(a1最后入栈)

 

package stack;

//Stack 的链式存储实现
public class StackSLinked implements Stack {
	private SLNode top; // 链表首结点引用
	private int size; // 栈的大小

	public StackSLinked() {
		top = null;
		size = 0;
	}

	// 返回堆栈的大小
	public int getSize() {
		return size;
	}

	// 判断堆栈是否为空
	public boolean isEmpty() {
		return size == 0;
	}

	// 数据元素e 入栈
	public void push(Object e) {
		SLNode q = new SLNode(e, top);
		top = q;
		size++;
	}

	// 栈顶元素出栈
	public Object pop() throws StackEmptyException {
		if (size < 1)
			throw new StackEmptyException("错误,堆栈为空。");
		Object obj = top.getData();
		top = top.getNext();
		size--;
		return obj;
	}

	// 取栈顶元素
	public Object peek() throws StackEmptyException {
		if (size < 1)
			throw new StackEmptyException("错误,堆栈为空。");
		return top.getData();
	}
}

其中节点的定义如下

package stack;

public class SLNode {
	private Object element;
	private SLNode next;

	public SLNode() {
		this(null, null);
	}

	public SLNode(Object ele, SLNode next) {
		this.element = ele;
		this.next = next;
	}

	public SLNode getNext() {
		return next;
	}

	public void setNext(SLNode next) {
		this.next = next;
	}

	/**************** Methods of Node Interface **************/
	public Object getData() {

		return element;
	}

	public void setData(Object obj) {
		element = obj;
	}
}


 

 

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2012/11/18/5637144.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
栈与栈的实现

栈 栈是一种基础的数据结构,只从一端读写数据。基本特点就”后进先出“,例如顺序入栈1,2,3,4,5,再顺序出栈是5,4,3,2,1 栈的基本操作 栈的基本操作有如下几种: 检测栈是否为空 返回栈存储...

月见樽
2017/11/28
0
0
数据结构1 线性结构

数据结构是指数据元素的结合及元素间的相互关系和构造方法。元素之间的相互关系是数据的逻辑结构,元素关系的存储形式成为存储结构。数据结构按照逻辑关系的不同分为线性结构和非线性结构两大...

zhixin9001
02/07
0
0
前端你应该了解的数据结构与算法

提到数据结构与算法都感觉这应该是后端要掌握的知识,对前端来说只要写写页面,绑定事件,向后台发发数据就好了,用不到数据结构与算法,也许对于一些数据查找 简单的for循环就能搞定,也许只...

幸福拾荒者
06/29
0
0
Java实现栈Stack_栈内部使用数组存储结构

Java实现栈Stack_栈内部使用数组存储结构 抽象数据类型栈的定义: 栈(stack),是限定在表尾进行插入或删除操作的线性表,因此对栈来说表尾有其特殊的含义,称为栈顶,相应的,表头端称为栈...

秋风醉了
2014/09/14
0
0
Java数据结构与算法(第四章栈和队列)

本章涉及的三种数据存储类型:栈、队列和优先级队列。 不同类型的结构 程序员的工具 数组是已经介绍过的数据存储结构,和其他结构(链表、树等等)一样,都适用于数据应用中作数据记录。 然而...

小风89
2015/10/24
250
0
两个栈实现队列(经典面试题)java

问题描述:用两个栈实现队列的基本方法,比如向队尾添加元素(offer)、获取队头元素(peek)、获取并删除队头元素(poll)。 解决思路:栈是先进后出的结构。比如1、2、3顺序进栈,出栈顺序...

qq_19259415
2017/11/22
0
0
STL系列之二 stack栈

栈(statck)这种数据结构在计算机中是相当出名的。栈中的数据是先进后出的(First In Last Out, FILO)。栈只有一个出口,允许新增元素(只能在栈顶上增加)、移出元素(只能移出栈顶元素)...

长平狐
2012/12/10
34
0
STL系列之二 stack栈

栈(statck)这种数据结构在计算机中是相当出名的。栈中的数据是先进后出的(First In Last Out, FILO)。栈只有一个出口,允许新增元素(只能在栈顶上增加)、移出元素(只能移出栈顶元素)...

彭博
2012/04/12
571
0
LeetCode题集整理- 栈、队列、堆

1、预备知识点 栈(Stack)和队列(Queue)是两种操作受限的线性表。 (线性表:线性表是一种线性结构,它是一个含有n≥0个结点的有限序列,同一个线性表中的数据元素数据类型相同并且满足“...

Blank_佐毅
2017/11/28
0
0
数据结构与算法JavaScript (一) 栈

序 数据结构与算法JavaScript这本书算是讲解得比较浅显的,优点就是用javascript语言把常用的数据结构给描述了下,书中很多例子来源于常见的一些面试题目,算是与时俱进,业余看了下就顺便记...

文艺小青年
2017/07/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java示例演示Functor 和monad

This article was initially an appendix in our Reactive Programming with RxJavabook. However introduction to monads, albeit very much related to reactive programming, didn't suit......

Quan全
14分钟前
0
0
微信官方jssdk Demo

1.html部分 <!DOCTYPE html><!-- saved from url=(0028){sh:$selfUrl} --><html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> <meta charset="utf-8"......

koloor
17分钟前
0
0
数据库命名规范

https://www.cnblogs.com/pangguoming/p/7126512.html 摘要:当前研发工作中经常出现因数据库表、数据库表字段格式不规则而影响开发进度的问题,在后续开发使用原来数据库表时,也会因为数据...

塔塔米
17分钟前
0
0
java https 请求工具类-通用

package com.ra.common.util; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintW......

轻量级赤影
18分钟前
0
0
MFC界面套包BCG Pro Edition for MFC正式发布v27.3|附下载

BCGControlBar Professional Edition for MFC是MFC的一个扩展库,您可以用来构建类似于Microsoft Office 2000/XP/2003/2007/2010/2013 和 Microsoft Visual Studio-like(打印、用户定制工具......

Miss_Hello_World
18分钟前
0
0
Spring Cloud云服务 - HongHu架构common-service 项目构建过程

上一篇我们介绍了《整合spring cloud云服务架构 - HongHu云架构common-service代码结构分析》,本节我们将对common-service整个项目进行剖析,将整个构建的流程给记录下来,让更多的关注者来...

itcloud
19分钟前
0
0
Connection reset

在使用HttpClient调用后台resetful服务时,“Connection reset”是一个比较常见的问题,有同学跟我私信说被这个问题困扰很久了,今天就来分析下,希望能帮到大家。例如我们线上的网关日志就会...

夜黑人模糊灬
23分钟前
0
0
如何写PHP规范注释

所有的文档标记都是在每一行的 * 后面以@开头。如果在一段话的中间出来@的标记,这个标记将会被当做普通内容而被忽略掉。 @access 该标记用于指明关键字的存取权限:private、public或prote...

度_
24分钟前
0
0
influxDB Ppostgis

PostGis 1.需要安装postgreSQL,postgis作为插件嵌入到postgreSQL中; 2.使用zip包直接安装,需要修改 makepostgisdb_using_extensions.bat文件中的路径,用户名,密码,然后直接运行; 3.没有...

courtzjl
27分钟前
0
0
多线程Thread-多线程顺序执行

需求:现在有两个任务,任务1和任务2,任务1中有多个线程,并且任务2必须等任务1完成后才能执行。 namespace TThread{ class Program { static void Main(string[] ar...

kaixinguo314
31分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部