Java語言如何實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)棧

這篇文章主要介紹了Java語言如何實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)棧，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

首先了解下棧的概念：

棧是限定僅在表頭進(jìn)行插入和刪除操作的線性表。有時(shí)又叫LIFO（后進(jìn)先出表）。要搞清楚這個(gè)概念，首先要明白”?！霸瓉淼囊馑迹绱瞬拍馨盐毡举|(zhì)。

"棧“者,存儲(chǔ)貨物或供旅客住宿的地方,可引申為倉庫、中轉(zhuǎn)站，所以引入到計(jì)算機(jī)領(lǐng)域里，就是指數(shù)據(jù)暫時(shí)存儲(chǔ)的地方，所以才有進(jìn)棧、出棧的說法。

實(shí)現(xiàn)方式是這樣的：首先定義了一個(gè)接口，然后通過這個(gè)接口實(shí)現(xiàn)了線性棧和鏈?zhǔn)綏?，代碼比較簡單，如下：

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();
	/* 查看棧頂?shù)脑?，但不移除?nbsp;*/
	T peek();
	/* 返回對(duì)象在棧中的位置 */
	int search(T data);
}

線性棧：以數(shù)組的方式實(shí)現(xiàn)。

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();
	}
}

鏈?zhǔn)綏＃和ㄟ^單鏈表進(jìn)行實(shí)現(xiàn)。

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;
		}
	}
}

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“Java語言如何實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)?！边@篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!