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

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

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

首先了解下栈的概念：

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

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

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

package com.peter.java.dsa.interfaces;

/**

* 栈操作定义

*

* @author Peter Pan

*/

public interface Stack {

/* 判空 */

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 implements Stack {

@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 methttp://hod stub

if (size == 0) {

PDKmqcr 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 implements Stack {

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。