public interface MyStack<T> {
public void push(T element);
public T pop() throws Exception;
public int size();
public boolean isEmpty();
}
1.用数组实现
/**
* @author jy
* @date 2018年6月1日
* <p>Description: </p>
*/
package datastruct;
import java.util.Stack;
/**
* @author jy
*FILO with array
*/
public class MyStackWithArray<T> implements MyStack<T>{
private Object array[];
private int n;//element num of stack
public MyStackWithArray(){
n=0;
array=new Object[3];
}
public boolean isEmpty(){
return n==0;
}
public int size()
{
return n;
}
/**
* @param array2
*<p>Description: </p>
*/
private void resize() {
Object temp[] = Arrays.copyOf(array, array.length * 2);
array = temp;
}
/* (non-Javadoc)
* @see datastruct.MyStack#push(java.lang.Object)
*/
@Override
public void push(T element) {
if(n==array.length){
resize();
}
array[n++]=element;
}
/* (non-Javadoc)
* @see datastruct.MyStack#pop()
*/
@Override
public T pop() throws Exception {
if(isEmpty()){
throw new Exception("stack is empty");
}
T elem=(T) array[--n];
array[n]=null;
return elem;
}
}
采坑日记，如果是数组类型，默认值是0，无法置为null
image.png
2.用链表实现
/**
* @author jy
* @date 2018年6月1日
* <p>Description: </p>
*/
package datastruct;
/**
* @author jy
* FILO
*
*/
public class MyStackWithLinkedlist<T> implements MyStack<T> {
private MyNode<T> head=null;//虚拟头部
private int n;//element num of stack
public boolean isEmpty(){
return n==0;
}
public int size(){
return n;
}
/**
* 每次都往头部的前面插入元素
* @param e
*<p>Description: </p>
*/
public void push(T e){
MyNode node =new MyNode();
node.setData(e);
node.setNext(head);
head=node;
n++;
}
/*
* 弹出头部元素
*/
public T pop() throws Exception{
if(isEmpty()){
throw new Exception("stack is empty");
}
T e=head.getData();
head=head.getNext();
n--;
return e;
}
}
Node
/**
* @author jy
* @date 2018年6月1日
* <p>Description: </p>
*/
package datastruct;
/**
* @author jy
* @param <T>
*
*/
public class MyNode<T> {
private MyNode next;
private T data;
public MyNode getNext() {
return next;
}
public void setNext(MyNode next) {
this.next = next;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
}
链表的头插法，每次往头结点的前面插入结点，并使新插入的结点为头结点。后进的先出。
测试：
/**
* @author jy
* @date 2018年6月4日
* <p>Description: </p>
*/
package datastruct;
import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;
/**
* @author jy
*
*/
public class MyStackWithArrayTest {
MyStack stackWithArray;
/**
* @throws java.lang.Exception
*<p>Description: </p>
*/
@BeforeClass
public static void setUpBeforeClass() throws Exception {
}
/**
* @throws java.lang.Exception
*<p>Description: </p>
*/
@Before
public void setUp() throws Exception {
//stackWithArray=new MyStackWithArray();
//stackWithArray=new MyStackWithLinkedlist();
stackWithArray=new MyStackWithQueue();
}
/**
* Test method for {@link datastruct.MyStackWithArray#push(java.lang.Object)}.
*/
@Test
public void testPush() {
assertEquals(stackWithArray.isEmpty(),true);
stackWithArray.push(1);
assertEquals(stackWithArray.size(),1);
stackWithArray.push(2);
stackWithArray.push(3);
stackWithArray.push(4);
stackWithArray.push(5);
assertEquals(stackWithArray.size(),5);
}
/**
* Test method for {@link datastruct.MyStackWithArray#pop()}.
*/
@Test
public void testPop() {
testPush();
assertEquals(stackWithArray.pop(), 5);
assertEquals(stackWithArray.pop(), 4);
assertEquals(stackWithArray.pop(), 3);
assertEquals(stackWithArray.pop(), 2);
assertEquals(stackWithArray.pop(), 1);
//stackWithArray.pop();
}
}
3.用队列实现栈
/**
* @author jy
* @date 2018年6月4日
* <p>Description: </p>
*/
package datastruct;
/**
* @author jy
*
*/
public class MyStackWithQueue<T> implements MyStack<T> {
MyQueue<T> queue=new MyQueueWithLinkedlist<T>();
/* (non-Javadoc)
* @see datastruct.MyStack#push(java.lang.Object)
*/
@Override
public void push(T element) {
queue.push(element);
}
/* (non-Javadoc)
* @see datastruct.MyStack#pop()
*1->2->3 3->1->2 2->1
*/
@Override
public T pop() throws Exception {
for(int i=1;i<queue.size();i++){
queue.push(queue.pop());
}
return queue.pop();
}
/* (non-Javadoc)
* @see datastruct.MyStack#size()
*/
@Override
public int size() {
return queue.size();
}
/* (non-Javadoc)
* @see datastruct.MyStack#isEmpty()
*/
@Override
public boolean isEmpty() {
return queue.isEmpty();
}
}
push时，将队列直接入队放入队尾。pop时将队列中除了最后一个元素外的其他元素，逐个添加到队列的尾部。
