Java栈的实例-数组和链表两种方法（转）-阿里云开发者社区

Java栈的实例-数组和链表两种方法（转）

2016-03-13 935

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 一、栈栈的定义栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。 (1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。 (2)当表中没有元素时称为空栈。

一、栈

栈的定义
栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出（Last In First Out）的线性表，简称为 LIFO 表。
栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"
最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，
要到最后才能删除。

2、栈的基本运算

（1）判断栈是否为空
boolean isEmpty();
（2）清空栈
void clear();
（3）栈的长度
int length();
（4）数据入栈
boolean push(T data);
（5）数据出栈，栈中删除
T pop();
（6）数据出栈 ,栈中不删除

T peek();

二、代码编写

1、接口类

[java] view plain copy

package com.lin.stack;
/**
* 功能概要：栈的接口类
*
* @author linbingwen
* @since 2015年8月29日
*/
public interface MyStack<T> {
/**
* 判断栈是否为空
* @author linbingwen
* @since 2015年8月29日
* @return
*/
boolean isEmpty();
/**
* 清空栈
* @author linbingwen
* @since 2015年8月29日
*/
void clear();
/**
* 栈的长度
* @author linbingwen
* @since 2015年8月29日
* @return
*/
int length();
/**
* 数据入栈
* @author linbingwen
* @since 2015年8月29日
* @param data
* @return
*/
boolean push(T data);
/**
* 数据出栈，栈中删除
* @author linbingwen
* @since 2015年8月29日
* @return
*/
T pop();
/**
* 数据出栈 ,栈中不删除
* @author linbingwen
* @since 2015年8月29日
* @return
*/
T peek();
}

2、数组实现栈

[java] view plain copy

package com.lin.stack;
/**
* 功能概要：数组实现栈
*
* @author linbingwen
* @since 2015年8月29日
*/
public class MyArrayStack<T> implements MyStack<T> {
private Object[] objs = new Object[16];
private int size;
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
for (int i = 0; i < objs.length; i++) {
objs[i] = null;
size--;
}
}
@Override
public int length() {
return size;
}
@Override
public boolean push(T data) {
if(size == (objs.length-1)){
Object[] temp = new Object[objs.length*2];
for (int i = 0; i < objs.length; i++) {
temp[i]=objs[i];
}
objs= temp;
}
objs[size++]=data;
return true;
}
@Override
@SuppressWarnings("unchecked")
public T pop() {
return size == 0?null:(T) objs[(size--)-1];
}
@Override
@SuppressWarnings("unchecked")
public T peek() {
return size == 0?null:(T) objs[size];
}
}

3、链表实现栈

[java] view plain copy

package com.lin.stack;
/**
* 功能概要：
*
* @author linbingwen
* @since 2015年8月29日
*/
public class MyListStack<T> implements MyStack<T>{
private int size;
private Node top;
class Node{
T data;
Node pre;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
top = null;
}
@Override
public int length() {
return size;
}
@Override
public boolean push(T data) {
Node node = new Node();
node.data=data;
if( null == top){
top = node;
}else {
node.pre = top;
top =node;
}
size++;
return true;
}
@Override
public T pop() {
if(size == 0){
return null;
}
T data = top.data;
top = top.pre;
size--;
return data;
}
@Override
public T peek() {
if(size == 0){
return null;
}
T data = top.data;
return data;
}
}

4、测试

[java] view plain copy

package com.lin.stack;
/**
* 功能概要：
*
* @author linbingwen
* @since 2015年8月29日
*/
public class StackTest {
/**
* @author linbingwen
* @since 2015年8月29日
* @param args
*/
public static void main(String[] args) {
MyStack<Integer> myStack1 = new MyArrayStack<Integer>();
MyStack<Integer> myStack2 = new MyListStack<Integer>();
for(int i =0;i<30;i++){
myStack1.push(i);
myStack2.push(i);
}
System.out.println("数组实现的栈输出如下 ");
for(int j =0;j<30;j++){
System.out.print(myStack1.pop()+" ");
}
System.out.println();
System.out.println("链表实现的栈输出如下 ");
for(int k =0;k<30;k++){
System.out.print(myStack2.pop()+" ");
}
}
}

输出结果如下：

或者看这里：

数组实现的栈输出如下
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
链表实现的栈输出如下
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

http://blog.csdn.net/evankaka/article/details/48088983

Java栈的实例-数组和链表两种方法（转）

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

Java栈的实例-数组和链表两种方法（转）

热门文章

最新文章

相关课程

相关电子书