栈
栈（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();
接口
package com.ghg.data_structure.stack;
public interface MyStack<T> {
/**
* 判断是否为空
* @return
*/
public boolean isEmpty();
/**
* 获取长度
* @return
*/
public int length();
/**
* 清空栈
*/
public void clear();
/**
* 入栈
* @param data
* @return
*/
public boolean push(T data);
/**
* 出栈,移除最后一个
* @return
*/
public T pop();
/**
* 出栈不移除
* @return
*/
public T peek();
}
数组实现
package com.ghg.data_structure.stack.imp;
import com.ghg.data_structure.stack.MyStack;
public class MyArrayStack<T> implements MyStack<T> {
private Object [] objs= new Object[16];
private int size;
public boolean isEmpty() {
return size==0;
}
public int length() {
return size;
}
public void clear() {
for(int i = 0; i <objs.length ; i++){
objs[i]=null;
size--;
}
}
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;
}
@SuppressWarnings("unchecked")
public T pop() {
return size==0?null:(T) objs[(size--)-1];
}
@SuppressWarnings("unchecked")
public T peek() {
return size==0?null:(T) objs[size-1];
}
}
列表实现
package com.ghg.data_structure.stack.imp;
import com.ghg.data_structure.stack.MyStack;
import com.sun.org.apache.bcel.internal.generic.ReturnaddressType;
public class MyListStack<T> implements MyStack<T> {
private int size;
private Node top;
public class Node {
// 数据
T data;
// 前一个
Node pre;
}
public boolean isEmpty() {
return size == 0;
}
public int length() {
return size;
}
public void clear() {
top = null;
}
public boolean push(T data) {
Node node = new Node();
node.data = data;
if (size == 0) {
top = node;
} else {
node.pre=top;
top=node;
}
size++;
return true;
}
public T pop() {
if (size == 0) {
return null;
}
T data = top.data;
top = top.pre;
size--;
return data;
}
public T peek() {
if (size == 0) {
return null;
}
T data = top.data;
return data;
}
}
测试
package com.ghg.data_structure.stack;
import com.ghg.data_structure.stack.imp.MyArrayStack;
import com.ghg.data_structure.stack.imp.MyListStack;
public class Test1 {
public static void main(String[] args) {
MyStack<Integer> myStack1 = new MyListStack<Integer>();
MyStack<Integer> myStack2 = new MyArrayStack<Integer>();
for (int i = 0; i < 50; i++) {
myStack1.push(i);
myStack2.push(i);
}
System.out.println(myStack1.length());
System.out.println(myStack2.length());
System.out.println("\n#########list 链表 peek#####");
for (int i = 0; i < 50; i++) {
System.out.print(myStack1.peek() + "\t");
}
System.out.println("\n#########array 数组 peek#####");
for (int i = 0; i < 50; i++) {
System.out.print(myStack2.peek() + "\t");
}
System.out.println("\n#########list 链表#####");
for (int i = 0; i < 50; i++) {
System.out.print(myStack1.pop() + "\t");
}
System.out.println("\n#########array 数组#####");
for (int i = 0; i < 50; i++) {
System.out.print(myStack2.pop() + "\t");
}
}
}
结果
50
50
#########list 链表 peek#####
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
#########array 数组 peek#####
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
#########list 链表#####
49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 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
#########array 数组#####
49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 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
网友评论