8535.com-新浦京娱乐场官网|欢迎您

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

来源:http://www.dnamique.com 作者:计算机网络 人气:102 发布时间:2019-10-07
摘要:Java语言实现数据结构栈代码详解,java数据结构 近来复习数据结构,自己动手实现了栈。栈是一种限制插入和删除只能在一个位置上的表。最基本的操作是进栈和出栈,因此,又被叫作

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

近来复习数据结构,自己动手实现了栈。栈是一种限制插入和删除只能在一个位置上的表。...

本文由8535.com-新浦京娱乐场官网|欢迎您发布于计算机网络,转载请注明出处:Java语言实现数据结构栈代码详解,java数据结构

关键词:

上一篇:Ubuntu 7.10字体美化

下一篇:没有了

最火资讯