文档章节

数据结构---->栈

小强斋太
 小强斋太
发布于 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
数据结构1 线性结构

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

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

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

秋风醉了
2014/09/14
0
0
前端你应该了解的数据结构与算法

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

幸福拾荒者
2018/06/29
0
0
两个栈实现队列(经典面试题)java

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

qq_19259415
2017/11/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Cookie 显示用户上次访问的时间

import javax.servlet.ServletException;import javax.servlet.annotation.WebServlet;import javax.servlet.http.Cookie;import javax.servlet.http.HttpServlet;import javax.serv......

gwl_
今天
1
0
网络编程

第14天 网络编程 今日内容介绍  网络通信协议  UDP通信  TCP通信 今日学习目标  能够辨别UDP和TCP协议特点  能够说出UDP协议下两个常用类名称  能够说出TCP协议下两个常用类名称...

stars永恒
今天
1
0
二进制相关

二进制 众所周知计算机使用的是二进制,数字的二进制是如何表示的呢? 实际就是逢二进一。比如 2 用二进制就是 10。那么根据此可以推算出 5的二进制等于 10*10+1 即为 101。 在计算机中,负数以...

NotFound403
昨天
3
0
day22:

1、写一个getinterface.sh 脚本可以接受选项[i,I],完成下面任务: 1)使用格式:getinterface.sh [-i interface | -I ip] 2)当用户使用-i选项时,显示指定网卡的IP地址;当用户使用-I选项...

芬野de博客
昨天
2
0
Spring Cloud Alibaba基础教程:使用Nacos实现服务注册与发现

自Spring Cloud Alibaba发布第一个Release以来,就备受国内开发者的高度关注。虽然Spring Cloud Alibaba还没能纳入Spring Cloud的主版本管理中,但是凭借阿里中间件团队的背景,还是得到不少...

程序猿DD
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部