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

首先了解下栈的概念：

栈是限定仅在表头进行插入和删除操作的线性表。有时又叫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]; } } @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; } @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语言实现数据结构栈代码详解的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！