码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居纽约。


Java中栈的实现——菜鸟学数据结构(二)

栈(stack)和队列(queue)是一种最基本、最常用的数据结构。今天我们用Java来实现栈的最基本的功能。栈(stack)的基本操作包括压栈(push)、出栈(pop)和查看栈顶元素(peek)。还经常用到的操作包括获取栈的大小(元素个数)、判断是否为空等此文当中略去,可以通过检测peek()获取的元素是否为空进行实现。楠哥计算机学习网www.liubonan.com

栈的特点是后进先出,因此我们只用一个元素top记录栈顶元素的引用即可。push()操作通过将栈顶的标示移往新填入的元素实现,peek()通过返回top的数据实现,pop()通过将栈顶标示向反方向移动并返回原来的top元素实现。请注意,因为栈当中的标示操作存在向反方向移动,所以Node的定义当中,使用了previous来记录前一个结点的引用,这与linklist稍有不同。本文采用int型作为数据,源码如下。楠哥计算机学习网www.liubonan.com

package ds;

public class Node {
	private int data;
	private Node previous;
	
	public Node(){}
	
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public Node getPrevious() {
		return previous;
	}
	public void setPrevious(Node previous) {
		this.previous = previous;
	}
	
}

package ds;

public class Stack {
	private Node top;
	
	public Stack(int data)
	{
		top = new Node();
		top.setData(data);
		top.setPrevious(null);
	}
	
	public void push(int data)
	{
		Node temp = new Node();
		temp.setData(data);
		temp.setPrevious(top);
		top = temp;
	}
	
	public boolean empty()
	{
		if(top == null)
			return true;
		else
			return false;
	}
	
	public int pop()
	{
		int temp = top.getData();
		top = top.getPrevious();
		
		return temp;
	}
	
	public int peek(){
		return top.getData();
	}
	
}

package ds;

public class Tester {
	
	static public void main(String[] args)
	{
		Stack s = new Stack(0);
		
		for(int i=1;i<=10;i++)
			s.push(i);
		
		while(!s.empty())
			System.out.print(s.pop()+" ");
	}

}
最近的文章

用Lisp解决简单的模式匹配(Pattern Match)问题

Lisp是人工智能中比较常用的语言之一,本文以一个经典的模式匹配(Pattern Match)问题为例,简要分析一下Lisp的语言结构。(楠哥计算机学习网www.liubonan.info) Lisp…

Technical, Career继续阅读
更早的文章

Java链表——菜鸟学数据结构(一)

数据结构一方面是专业程序员必须熟练掌握的基础知识,另一方面也是非专业人员比较头痛的内容。从本篇文章开始,楠哥将开始连载数据结构的入门知识。本篇为大家介绍Java实现链表。 因为在Java当中,所有的元…

Technical, Career继续阅读
comments powered by Disqus