`
suhuanzheng7784877
  • 浏览: 702736 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
Ff8d036b-05a9-33b5-828a-2633bb68b7e6
读金庸故事,品程序人生
浏览量:47713
社区版块
存档分类
最新评论

Java基础复习笔记05数据结构-栈

阅读更多

1.      

栈是一种比较特殊的线性表,它的原则就是先进后出,后进先出。你就把他想做一个你放书的大箱子,要想看放在最底层的书(压箱底的),那么得先拿出来上面的所有书之后那本最底层的书才能取到。同样栈也是这个意思。

 

2.       栈的操作

栈的操作比线性表的操作要少一些,这也可以看出来栈结构实际上就是在线性表的基础上加了一些不能进行的操作才叫做栈。栈的操作有:入栈、出栈、访问栈顶元素、清空栈。

3.       栈的使用场景

展示一个比较有用的结构,比如做语法分析、递归、支持撤消都可以使用栈来实现。

4.       栈的顺序实现

栈的顺序实现和线性表的顺序实现差不多,都是用一个数组来进行数据的存取。

如下

package dateStructer.stack;

/**
 * 栈的顺序实现
 * @author liuyan
 * @param <E>
 */
public class MyArrayStack<E> {

	// 临时数组
	private Object[] objects;

	// 默认临时数组的初始大小
	private final static int Def_Size = 16;

	// 记录实实在在的元素个数
	private int elementSize;

	public MyArrayStack() {
		objects = new Object[Def_Size];
	}

	/**
	 * 栈顶添加元素
	 * @param e
	 */
	public void push(E e) {

		if (elementSize == 0) {
			objects[0] = e;
			elementSize++;
			return;
		}

		for (int i = 0; i < objects.length; i++) {
			if (objects[i] == null) {
				objects[i] = e;
				elementSize++;
				break;
			}
		}

	}

	/**
	 * 从栈顶出元素,删除栈顶元素
	 * 
	 * @return
	 */
	public E pop() {
		if (isEmpty()) {
			throw new RuntimeException("栈已经空");
		}
		E lastElement = (E) objects[elementSize - 1];
		
		objects[elementSize - 1] = null;
		elementSize--;

		return lastElement;
	}

	/**
	 * 从栈顶出元素,不删除栈顶元素
	 * 
	 * @return
	 */
	public E peek() {
		if (isEmpty()) {
			throw new RuntimeException("栈已经空");
		}

		E lastElement = (E) objects[objects.length - 1];
		return lastElement;
	}

	/**
	 * 栈空间大小
	 * @return
	 */
	public int getSize() {
		return elementSize;
	}

	/**
	 * 栈是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return elementSize == 0;
	}
	
	/**
	 * 清空所有元素
	 */
	public void clear() {
		for (int i = 0; i < elementSize; i++) {
			objects[i] = 0;
		}
		elementSize = 0;
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");

		for (int i = 0; i < elementSize; i++) {

			str.append("[" + objects[i].toString() + "],");

		}

		if (elementSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
}

 5.       栈的链表实现

使用链表结构实现栈其实用一个栈顶临时标记记录着时刻变化的栈顶元素即可,算法如下

package dateStructer.stack;

public class MyLinkStack<E> {

	/**
	 * 单向链表结构
	 */
	public class LinkNode {

		// 真正的数据域
		private E date;

		// 记录下一个节点
		private LinkNode nextLinkNode;

		public LinkNode() {

		}

		public LinkNode(E date, LinkNode nextLinkNode) {
			this.date = date;
			this.nextLinkNode = nextLinkNode;
		}
	}

	// 结点个数
	private int elementSize;

	// 头结点
	private LinkNode topNode;

	public MyLinkStack() {
		topNode = new LinkNode();
	}

	/**
	 * 栈顶添加元素
	 * 
	 * @param e
	 */
	public void push(E e) {

		if (elementSize == 0) {
			if (topNode == null) {
				topNode = new LinkNode(e, null);
			} else {
				topNode.date = e;
			}
			elementSize++;
			return;
		}

		LinkNode linkNode = topNode;

		LinkNode linkNodeNewTop = new LinkNode(e, linkNode);

		topNode = linkNodeNewTop;
		elementSize++;
	}

	/**
	 * 从栈顶出元素,删除栈顶元素
	 * 
	 * @return
	 */
	public E pop() {
		if (isEmpty()) {
			throw new RuntimeException("栈已经空");
		}

		LinkNode linkNode = topNode;

		topNode = topNode.nextLinkNode;

		E date = linkNode.date;

		linkNode.date = null;
		linkNode.nextLinkNode = null;

		elementSize--;

		return date;
	}

	/**
	 * 从栈顶出元素,不删除栈顶元素
	 * 
	 * @return
	 */
	public E peek() {
		if (isEmpty()) {
			throw new RuntimeException("栈已经空");
		}

		E date = topNode.date;

		return date;
	}

	/**
	 * 栈空间大小
	 * 
	 * @return
	 */
	public int getSize() {
		return elementSize;
	}

	/**
	 * 栈是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return elementSize == 0;
	}

	/**
	 * 清空所有元素
	 */
	public void clear() {
		LinkNode linkNode = topNode;
		for (int i = 0; i < elementSize; i++) {
			linkNode.date = null;
			linkNode = linkNode.nextLinkNode;
		}

		elementSize = 0;
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");

		LinkNode linkNode = topNode;

		for (int i = 0; i < elementSize; i++) {

			str.append("[" + linkNode.date.toString() + "],");
			linkNode = linkNode.nextLinkNode;
		}

		if (elementSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
}

 测试代码同顺序栈的测试代码相同,在此就不在赘述。这里面利用了一个topNode变量来作为栈顶的标记,时刻改变、维护这个变量就可以轻易获取站定元素。

6.       利用现有JDK集合实现

其实我们可以使用Java现有的集合辅助类类轻易实现栈结构。

package dateStructer.stack;

import java.util.ArrayList;

public class MyStack<T> {

	ArrayList<T> list;

	public MyStack() {
		list = new ArrayList<T>();
	}

	/**
	 * 栈顶添加元素
	 * 
	 * @param e
	 */
	public void push(T e) {
		list.add(e);
	}

	/**
	 * 从栈顶出元素
	 * 
	 * @return
	 */
	public T pop() {

		if (isEmpty()) {
			throw new RuntimeException("栈已经空");
		}

		T lastElement = list.get(list.size() - 1);
		list.remove(list.size() - 1);
		return lastElement;
	}

	/**
	 * 栈空间大小
	 * 
	 * @return
	 */
	public int getSize() {
		return list.size();
	}

	/**
	 * 栈是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return list.size() == 0;
	}
	
	public void clear(){
		list.clear();
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");

		for (int i = 0; i < list.size(); i++) {

			str.append("[" + list.get(i).toString() + "],");

		}

		if (list.size() > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
}

 其实和数组的顺序实现也差不多,无非就是节省了自己维护数组操作的逻辑。

7.       总结

在此总结了栈的特点和实现方式。Java自己有一个栈的实现类就是java.util.Stack。显示开发中可以使用此类完成栈的操作。栈与队列经常是一起提到,下次我们复习复习队列,唉~~今天状态不是很好,先睡了!

  • 大小: 20.1 KB
分享到:
评论
1 楼 spadesacn 2012-02-28  
纯讨论啊。
第一个数组实现的时候,其实找一个变量记录栈顶位置就好了,否则push是O(n),记录栈顶位置的push是O(1),clear()虽然不是基本ADT的内容,但是this.object[] = new object[capability]更快。数组实现最耗的是在enlarge storeage时候。

相关推荐

    Java基础复习笔记06数据结构-队列

    Java基础复习笔记06数据结构-队列,详细介绍了队列的知识

    java基础数据结构-栈

    在《Java基础复习笔记05数据结构-栈》中提到,**栈**是一种特殊的线性表,它遵循“先进后出”(First In Last Out, FILO)的原则,即最后进入的数据项将最先被取出。可以将其想象成一个装书的盒子,如果想要拿到最...

    Java基础复习笔记09数据结构-哈夫曼树

    ### Java基础复习笔记09数据结构-哈夫曼树 #### 1. 哈夫曼树概述 哈夫曼树是一种特殊的二叉树,它在计算机科学领域有着广泛的应用,尤其是在数据压缩方面。哈夫曼树也被称为最优二叉树,其构建原则是使得带权路径...

    Java基础复习笔记04数据结构-线性表

    ### Java基础复习笔记04数据结构-线性表:深入解析与应用 #### 线性表的概念 线性表是计算机科学中最基础的数据结构之一,它由一系列相同类型的元素组成,这些元素按照一定的顺序排列,形成一个有序的序列。在逻辑...

    Java基础复习笔记10数据结构-排序二叉树

    【Java基础复习笔记10数据结构-排序二叉树】 排序二叉树是一种特殊类型的二叉树,其每个节点的数据值满足以下特性:对于任意节点,其左子树中的所有节点值都小于该节点,而右子树中的所有节点值都大于或等于该节点...

    Java基础复习笔记08数据结构-二叉树和二叉树的遍历

    ### Java基础复习笔记08数据结构-二叉树和二叉树的遍历 #### 一、二叉树概述 二叉树(Binary Tree)是一种重要的数据结构,在计算机科学中有广泛的应用。二叉树中的每个节点最多有两个子节点,分别称为左子节点和右...

    微博的搜索引擎优化价值分析等资料.rar

    2012-05-27 11:08 180,401 Java基础复习笔记05数据结构-栈.pdf 2012-05-27 11:05 834,613 jqueryui-API(最完整).pdf 2012-05-27 10:58 31,758,963 Linux程序设计(原书第2版).pdf 2012-05-27 11:03 2,023,736 ...

    资料合集.part2.rar

    2012-05-27 11:08 180,401 Java基础复习笔记05数据结构-栈.pdf 2012-05-27 11:05 834,613 jqueryui-API(最完整).pdf 2012-05-27 10:58 31,758,963 Linux程序设计(原书第2版).pdf 2012-05-27 11:03 2,023,736 ...

    资料合集.part1.rar

    2012-05-27 11:08 180,401 Java基础复习笔记05数据结构-栈.pdf 2012-05-27 11:05 834,613 jqueryui-API(最完整).pdf 2012-05-27 10:58 31,758,963 Linux程序设计(原书第2版).pdf 2012-05-27 11:03 2,023,736 ...

    Java基础尚硅谷宋红康学习笔记

    【Java基础】 Java是一种广泛使用的面向对象的编程语言,由Sun Microsystems(现已被Oracle公司收购)于1995年发布。Java以其“一次编写,到处运行”的特性,成为跨平台应用开发的首选语言。Java的基础部分主要包括...

    java ee 复习笔记

    Java EE的复习笔记是学习这个复杂框架的重要参考资料,尤其对于开发者来说,深入理解其核心概念和技术是必不可少的。 首先,Struts是Java EE中的一个MVC(Model-View-Controller)框架,它的主要任务是分离业务逻辑...

    Java基础复习笔记.docx

    这份《Java基础复习笔记.docx》提供了全面的复习材料,涵盖了Java编程的基础至进阶概念,对于那些希望提升Java技能的学习者来说是宝贵的资源。 首先,笔记详细介绍了Java的基本数据类型,包括整型(如int)、浮点型...

Global site tag (gtag.js) - Google Analytics