欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java语言实现数据结构栈代码详解

程序员文章站 2023-12-13 09:41:40
近来复习数据结构,自己动手实现了栈。栈是一种限制插入和删除只能在一个位置上的表。最基本的操作是进栈和出栈,因此,又被叫作“先进后出”表。 首先了解下栈的概念: 栈是...

近来复习数据结构,自己动手实现了栈。栈是一种限制插入和删除只能在一个位置上的表。最基本的操作是进栈和出栈,因此,又被叫作“先进后出”表。

首先了解下栈的概念:

栈是限定仅在表头进行插入和删除操作的线性表。有时又叫lifo(后进先出表)。要搞清楚这个概念,首先要明白”栈“原来的意思,如此才能把握本质。

"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈、出栈的说法。

实现方式是这样的:首先定义了一个接口,然后通过这个接口实现了线性栈和链式栈,代码比较简单,如下:

package com.peter.java.dsa.interfaces;
/**
 * 栈操作定义
 * 
 * @author peter pan
 */
public interface stack<t> {
	/* 判空 */
	boolean isempty();
	/* 清空栈 */
	void clear();
	/* 弹栈 */
	t pop();
	/* 入栈 */
	boolean push(t data);
	/* 栈的长度 */
	int length();
	/* 查看栈顶的元素,但不移除它 */
	t peek();
	/* 返回对象在栈中的位置 */
	int search(t data);
}

线性栈:以数组的方式实现。

package com.peter.java.dsa.common;
import com.peter.java.dsa.interfaces.stack;
/**
 * 线性栈
 * 
 * @author peter pan
 */
public class linearstack<t> implements stack<t> {
	@suppresswarnings("unchecked")
	 private t[] t = (t[]) new object[16];
	private int size = 0;
	@override
	 public boolean isempty() {
		// todo auto-generated method stub
		return size == 0;
	}
	@override
	 public void clear() {
		// todo auto-generated method stub
		for (int i = 0; i < t.length; i++) {
			t[i] = null;
		}
		size = 0;
	}
	@override
	 public t pop() {
		// todo auto-generated method stub
		if (size == 0) {
			return null;
		}
		t tmp = t[size - 1];
		t[size - 1] = null;
		size--;
		return tmp;
	}
	@override
	 public boolean push(t data) {
		// todo auto-generated method stub
		if (size >= t.length) {
			resize();
		}
		t[size++] = data;
		return true;
	}
	@override
	 public int length() {
		// todo auto-generated method stub
		return size;
	}
	@override
	 public t peek() {
		// todo auto-generated method stub
		if (size == 0) {
			return null;
		} else {
			return t[size - 1];
		}
	}
	/* return index of data, return -1 if no data */
	@override
	 public int search(t data) {
		// todo auto-generated method stub
		int index = -1;
		for (int i = 0; i < t.length; i++) {
			if (t[i].equals(data)) {
				index = i;
				break;
			}
		}
		return index;
	}
	@suppresswarnings("unchecked")
	 private void resize() {
		t[] tmp = (t[]) new object[t.length * 2];
		for (int i = 0; i < t.length; i++) {
			tmp[i] = t[i];
			t[i] = null;
		}
		t = tmp;
		tmp = null;
	}
	/* from the left to the right is from the top to the bottom of the stack */
	@override
	 public string tostring() {
		// todo auto-generated method stub
		stringbuffer buffer = new stringbuffer();
		buffer.append("linear stack content:[");
		for (int i = t.length - 1; i > -1; i--) {
			buffer.append(t[i].tostring() + ",");
		}
		buffer.append("]");
		buffer.replace(buffer.lastindexof(","), buffer.lastindexof(",") + 1, "");
		return buffer.tostring();
	}
}

链式栈:通过单链表进行实现。

package com.peter.java.dsa.common;
import com.peter.java.dsa.interfaces.stack;
public class linkedstack<t> implements stack<t> {
	private node top;
	private int size;
	@override
	 public boolean isempty() {
		// todo auto-generated method stub
		return size == 0;
	}
	@override
	 public void clear() {
		// todo auto-generated method stub
		top = null;
		size = 0;
	}
	@override
	 public t pop() {
		// todo auto-generated method stub
		t topvalue = null;
		if (top != null) {
			topvalue = top.data;
			node oldtop = top;
			top = top.prev;
			oldtop.prev = null;
			size--;
		}
		return topvalue;
	}
	@override
	 public boolean push(t data) {
		// todo auto-generated method stub
		node oldtop = top;
		top = new node(data);
		top.prev = oldtop;
		size++;
		return true;
	}
	@override
	 public int length() {
		// todo auto-generated method stub
		return size;
	}
	@override
	 public t peek() {
		// todo auto-generated method stub
		t topvalue = null;
		if (top != null) {
			topvalue = top.data;
		}
		return topvalue;
	}
	@override
	 public int search(t data) {
		// todo auto-generated method stub
		int index = -1;
		node tmp = top;
		for (int i = size - 1; i > -1; i--) {
			if (tmp.data.equals(data)) {
				index = i;
				break;
			} else {
				tmp = tmp.prev;
			}
		}
		tmp = null;
		return index;
	}
	@override
	 public string tostring() {
		// todo auto-generated method stub
		stringbuffer buffer = new stringbuffer();
		buffer.append("linked stack content:[");
		node tmp = top;
		for (int i = 0; i < size - 1; i++) {
			buffer.append(tmp.tostring() + ",");
			tmp = tmp.prev;
		}
		tmp = null;
		buffer.append("]");
		buffer.replace(buffer.lastindexof(","), buffer.lastindexof(",") + 1, "");
		return super.tostring();
	}
	private class node {
		t data;
		node prev;
		public node(t data) {
			// todo auto-generated constructor stub
			this.data = data;
		}
	}
}

学习还在进行中,以后会继续更新代码。

就是本文关于java语言实现数据结构栈代码详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

上一篇:

下一篇: