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

2024-07-13 10:13:34

字体：大中小

来源：转载

供稿：网友

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

首先了解下栈的概念：

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

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

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

java;">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语言实现数据结构栈代码详解的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

注：相关教程知识阅读请移步到JAVA教程频道。

上一篇：Java动态规划之硬币找零问题实现代码

下一篇：Java编程实现打地鼠文字游戏实例代码