这篇文章主要介绍了Java语言如何实现数据结构栈，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。
首先了解下栈的概念：
栈是限定仅在表头进行插入和删除操作的线性表。有时又叫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语言如何实现数据结构栈”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
