文档章节

数据结构---->栈

小强斋太
 小强斋太
发布于 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,2,3,4,5,再顺序出栈是5,4,3,2,1 栈的基本操作 栈的基本操作有如下几种: 检测栈是否为空 返回栈存储...

月见樽
2017/11/28
0
0
前端你应该了解的数据结构与算法

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

幸福拾荒者
06/29
0
0
数据结构1 线性结构

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

zhixin9001
02/07
0
0
Java实现栈Stack_栈内部使用数组存储结构

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

秋风醉了
2014/09/14
0
0
前端也要会的数据结构 (不定期更新篇)

前端的软肋 一说到前端大家脑子里只有,布局、展示数据、修改样式等等。可是数据是哪里来的呢?后端给的后端给的。数据的结构呢?后端给啥用啥。 这就是前端的一个软肋。我们的业务让我们并不...

酸楚与甘甜
08/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

play framework 如何支持多数据源

有段时间没有写博客了,但今天又写一篇了,主要是因为这事有一丝自己的思考和动手实践,所以就记录下来了。 现有的问题: play 1.2.4 两台数据库服务器,但是play1.2.4 并不支持同时连接两台...

tuerqidi
20分钟前
0
0
Mysql only_full_group_by解析

查看当前数据库模式: select @@sql_mode; 原因: mysql 5.7中的sql_mode的值中包含'ONLY_FULL_GROUP_BY'; 处理:执行以下SQL set GLOBAL sql_mode ='STRICT_TRANS_TABLES,NO_ZERO_IN_DATE,N......

年轻的中年大叔
22分钟前
1
0
防止表单重复提交

1:前端方式(治标不治本) $("#admin-role-save").click(function(){//admin-role-save为submit的idvar ts=$(this);var ts_old_val=ts.val();ts.val("提交中....");ts.att...

uug
22分钟前
1
0
保持屏幕常亮

getWindow().setFlags(WindowManager.LayoutParams.FLAG_KEEP_SCREEN_ON, WindowManager.LayoutParams.FLAG_KEEP_SCREEN_ON); 在act的created方法中调用即可,一般是播放视频的时候......

Carbenson
22分钟前
1
0
智能合约实施指南

与区块链技术一样,智能合约在商业领域也非常有价值。 为了让我们的读者彻底了解智能合约是什么以及它们如何影响现代商业的交易方式,我们准备了本指南。 集中商业模式正在给去中心化的模式让...

geek12345
25分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部