文档章节

(堆)栈

自由的角马
 自由的角马
发布于 2015/01/10 13:57
字数 765
阅读 9
收藏 0

(堆)栈概述

栈是一种特殊的线性表,是操作受限的线性表

栈的定义和特点
定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈
特点:先进后出(FILO)或后进先出(LIFO

栈的结构

如下图所示:

线性表的操作主要包括:

1清空(堆)栈

(2)判断是否为空

3)元素的个数

4)入

5

(6)取栈顶元素

接口

由此,对队列的抽象数据类型定义Queue接口如下:
package stack;
/**
 * (堆)栈
 * @author Administrator
 *
 */
public interface Stack {
	/**
	 * 清空堆栈
	 */
	public void clear();
	/**
	 * 入栈
	 * @param obj 入栈的元素
	 */
	public void push(Object obj);
	/**
	 * 出栈
	 * @return 出栈的结果
	 */
	public Object pop();
	/**
	 * 判断是否为空
	 * @return
	 */
	public boolean isEmpty();
	/**
	 * 求元素的个数
	 * @return 元素的个数
	 */
	public int size();
	/**
	 * 取栈顶元素
	 * @return 栈顶元素
	 */
	public Object peek();
	
}

顺序(堆)栈


结构模型


栈顶指针top,指向实际栈顶后的空位置,初值为0。

栈的初始空间大小为M

top=0,栈空,此时出栈,则下溢(underflow);

top=M,栈满,此时入栈,则上溢(overflow);


源代码

package stack;
/**
 * 顺序(堆)栈
 * @author Administrator
 *
 */
public class ArrayStack implements Stack{
	private static int DEFAULT_SIZE = 100; 
	private int Top;
	Object array[];
	
	public ArrayStack() {
		Top = 0;
		array = new Object[DEFAULT_SIZE];
	}
	
	public boolean isEmpty() {
		
			return 0 == Top ;

	}
	public void expand() {
		Object[] newArray = new Object[2 * array.length];
		for(int i=0; i<array.length; i++) {
			newArray[i] = array[i];
		}
		array = newArray;
	}
	/*
	public void expand() {
		try {
			Object[] newArray = new Object[2*DEFAULT_SIZE];
			for(int i=0; i<array.length; i++) {
				newArray[i] = array[i];
			}
			array = newArray;
		}catch(OutOfMemoryError e) {
			System.out.println("error in expand of Stack class!");
			//e.printStackTrace();
		}
		
		
		DEFAULT_SIZE = 2*DEFAULT_SIZE;
	}
	*/
	public void push(Object obj) {
		if(Top == array.length) {
			expand();
		}	
		array[Top] =obj;
		Top ++;
		
	}
	
	public Object pop() {
		if(0 == Top) throw new IllegalStateException();
		Object val = array[-- Top];
		array[Top] = null;
		return val;
		
	}
	
	public void clear() {
		for(int i=0; i<array.length; i++) {
			array[i] = null;
			Top = 0;
		}
	}
	
	public Object peek() {
		if(0 == Top) throw new IllegalStateException();
		return array[Top - 1];
	}
	
	public int size() {
		return Top;
	}
	
	public String toString() {
		String s = "[";
		for(int i=Top-1; i>=0 ; i--) {
			s = s + array[i];
			s = s + ",  ";
		}
		s = s + "]";
		return s;
	}
	
}


链式(堆)栈


结构模型


源代码


package stack;

/**
 * 链式(堆)栈的结点
 * @author luoweifu
 *
 */
class Node{
	Object data;	//数据元素
	Node next;		//后驱结点
	public Node() {
		this(null);
	}
	public Node(Object data) {
		this.data = data;
		this.next = null;
	}
}

/**
 * 链式(堆)栈, 无头结点
 * @author Administrator
 *
 */
public class LinkStack implements Stack {
	private Node top;	//栈顶指针
	private int size;	//栈的大小
	
	public LinkStack() {
		top = null;
		size = 0;
	}
	
	@Override
	public void clear() {
		top = null;
		size = 0;
	}

	@Override
	public void push(Object obj) {
		Node p = new Node(obj);
		if(top == null) {
			top = p;
		} else {
			p.next = top;
			top = p;
		}
		size ++;
	}

	@Override
	public Object pop() {
		Node p = top;
		top = top.next;
		size --;
		return p.data;
	}

	@Override
	public boolean isEmpty() {
		if(size == 0)
			return true;
		else
			return false;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Object peek() {
		return top.data;
	}
	

	public String toString() {
		StringBuilder sb = new StringBuilder("[");
		Node p = top;
		if(p == null) {
			sb.append("");
		} else {
			do{
				sb.append(p.data + ",  ");
			}while((p = p.next) != null);
		}
		sb.append("]");
		return sb.toString();
	}
}

测试(堆)栈

package stack;

public class Test {
	/**
	 * 测试堆栈
	 * @param args
	 */
	public static void main(String[] args) {
		//Stack stack = new ArrayStack();
		Stack stack = new LinkStack();
		for(int i=0; i<10; i++) {
			stack.push(i);
		}
		System.out.println(stack.toString());
		Object a = stack.pop();
		System.out.println(a + stack.toString());
		stack.push(20);
		Object b = stack.peek();
		System.out.println( b + stack.toString());
		stack.clear();
		System.out.println( "数据数量:" + stack.size()
				+ "  isEmpty? " + stack.isEmpty() + "  数据为:" + stack.toString());
	}
	
}


结果

[9,  8,  7,  6,  5,  4,  3,  2,  1,  0,  ]
9[8,  7,  6,  5,  4,  3,  2,  1,  0,  ]
20[20,  8,  7,  6,  5,  4,  3,  2,  1,  0,  ]
数据数量:0  isEmpty? true  数据为:[]



本文转载自:http://blog.csdn.net/luoweifu/article/details/8507836

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
C/C++程序内存分配整理二——堆和栈的区别

1、申请方式 stack: 由系统自动分配。 例如,声明在函数中一个局部变量int b; 系统自动在栈中为b开辟空间。 heap: 需要程序员自己申请,并指明大小,在C中malloc函数,C++中是new运算符。 如...

吴国青
2013/09/09
0
0
C++用new来创建对象和非new来创建对象的区别

我们都知道C++中有三种创建对象的方法,如下: include <iostream> using namespace std; class A{private: public: }; int main(){   delete c;//释放对象 } 第一种和第二种没什么区别,一...

DannyCoder
2018/09/05
0
0
Stack vs. Heap:了解 Java 的内存分配机制

知道栈和堆之间的区别吗?什么时候该用哪一个,它们提供了什么功能? 这是一篇关于内存分配的指南。 栈和堆是与关于 Java 内存分配的两个重要概念。我们来看看这两个概念,为什么它们很重要,...

oschina
2017/08/14
2.9K
8
堆栈的区别及增长方向

一个由c/C++编译的程序占用的内存分为以下几个部分 1、栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。 2、堆区(heap) — ...

geek_loser
2016/07/04
36
0
内存分配——栈、堆、静态区、符号区等等

一个由C/C++编译的程序占用的内存分为以下几个部分 1、栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。 2、堆区(heap) — ...

AlphaJay
2010/06/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

GMTC2019|闲鱼-基于Flutter的架构演进与创新

作者:闲鱼技术-宗心 2012年应届毕业加入阿里巴巴,主导了闲鱼基于Flutter的新混合架构,同时推进了Flutter在闲鱼各业务线的落地。未来将持续关注终端技术的演变及趋势 Flutter的优势与挑战 ...

阿里云云栖社区
27分钟前
2
0
迪蒙人工智能共享停车吸引国际关注

  近来,华为创始人任正非多次提及人工智能。即便在华为生死攸关的关键时刻,任正非依旧不忘强调教育的重要性,“如果不重视教育,实际上我们会重返贫穷的,因为这个社会,最终是要走向人工智能的...

琴殇的
29分钟前
0
0
iOS开发之EventKitUI框架的应用

iOS开发之EventKitUI框架的应用 前面博客,有介绍EventKit这个框架的使用,使用EventKit可以与系统的日历和提醒应用进行交互,读写用户的日程事件。EventKitUI,顾名思义,其实基于EventKit框...

珲少
37分钟前
0
0
从MySQL源码看其网络IO模型

从MySQL源码看其网络IO模型 前言 MySQL是当今最流行的开源数据库,阅读其源码是一件大有裨益的事情(虽然其代码感觉比较凌乱)。而笔者阅读一个Server源码的习惯就是先从其网络IO模型看起。于是...

无毁的湖光-Al
37分钟前
0
0
WebService学习笔记

什么是Web Services? Web Services 是应用程序组件 Web Services 使用开放协议进行通信 Web Services 是独立的(self-contained)并可自我描述 Web Services 可通过使用UDDI来发现 Web Serv...

榴莲黑芝麻糊
54分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部