文档章节

数据结构---->栈

小强斋太
 小强斋太
发布于 2016/11/09 20:05
字数 1286
阅读 3
收藏 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 线性结构

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

zhixin9001
02/07
0
0
栈与栈的实现

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

月见樽
2017/11/28
0
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

没有更多内容

加载失败,请刷新页面

加载更多

String转成JSON的实现

String转成JSON 这个依赖很重要,我们将围绕fastjson中的JSONObject这个类来谈转换 欢迎工作一到八年的Java工程师朋友们加入Java高级交流:854630135 本群提供免费的学习指导 架构资料 以及免...

编程SHA
2分钟前
0
0
详解Object.values(),Object.keys(),Object.entries(),Object.create(),includes()

(1)Object.keys() // 返回数组,成员是参数对象自身的(不含继承的)所有可遍历(enumerable)属性的键名。 eg:var obj = {a:1,b:'gy'} Object.keys(obj) // ['a','b'] (2)...

JamesView
26分钟前
1
0
SpringBoot中Mybatis打印sql

application.properties中添加 logging.level.com.example.demo.dao=debug com.example.demo.dao 是对应xml中相应interface层...

writeademo
26分钟前
1
0
Git —— 创建版本库和提交回退版本

二、 创建版本库 版本库又叫做仓库,简单理解就是一个目录,这个目录里面所有的文件都可以被Git管理起来,每个文件的修改、删除,Git都可以跟踪,便于追踪历史与还原。找到一个合适的位置,创...

lwenhao
36分钟前
3
0
guava cache使用介绍

今天在项目中发现大量使用guava cache提供缓存,觉得不错。 jvm堆大小为5G /** * * 占用JVM内存,内部数据结构类似于ConcurrentHashMap。因为JVM堆大小的限制,guava cac...

jack_peng
41分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部