摘要：返回棧頂元素，未出棧出棧，返回棧頂元素，同時從棧中移除該元素棧頂元素，代表空棧棧容量，默認為存放元素的數(shù)組添加元素，從棧頂數(shù)組尾部插入擴容從棧頂添加元素復制元素更新棧頂
Stack Interface
package com.nasuf.arraylist;
public interface Stack {
boolean isEmpty();
void push(T data);
/**
* 返回棧頂元素，未出棧
* @return
*/
T peek();
/**
* 出棧，返回棧頂元素，同時從棧中移除該元素
* @return
*/
T pop();
}
Sequence Stack
package com.nasuf.arraylist;
import java.io.Serializable;
import java.util.EmptyStackException;
public class SeqStack implements Stack, Serializable {
private static final long serialVersionUID = 7850303094177457725L;
/**
* 棧頂元素，-1代表空棧
*/
private int top = -1;
/**
* 棧容量，默認為10
*/
private int capacity = 10;
/**
* 存放元素的數(shù)組
*/
private T[] array;
private int size;
public SeqStack(int capacity) {
array = (T[]) new Object[capacity];
}
public SeqStack() {
array = (T[]) new Object[this.capacity];
}
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return this.top == -1;
}
/**
* 添加元素，從棧頂（數(shù)組尾部）插入
* @param data
*/
@Override
public void push(T data) {
if (array.length == size)
ensureCapacity(size*2+1); //擴容
// 從棧頂添加元素
array[++top] = data;
size ++;
}
@Override
public T peek() {
if (isEmpty())
throw new EmptyStackException();
return array[top];
}
@Override
public T pop() {
if(isEmpty())
throw new EmptyStackException();
size --;
return array[top--];
}
private void ensureCapacity(int capacity) {
if (capacity < size)
return;
T[] old = array;
array = (T[]) new Object[capacity];
// 復制元素
for (int i=0; i
LinkedStack
import java.io.Serializable;
import java.util.EmptyStackException;
public class LinkedStack implements Stack, Serializable{
private static final long serialVersionUID = -4338010259113832656L;
private static class Node {
public AnyType data;
public Node next;
public Node() {
}
public Node(AnyType d) {
data = d;
}
public Node(AnyType d, Node n) {
data = d;
next = n;
}
}
private Node top;
private int size;
public LinkedStack() {
this.top = new Node ();
}
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return top == null || top.data == null;
}
@Override
public void push(T data) {
if (data == null) {
throw new StackOverflowError();
}
if (this.top == null) {
this.top = new Node (data);
} else if (this.top.data == null) {
this.top.data = data;
} else {
Node p = new Node<>(data, this.top);
top = p; //更新棧頂
}
size ++;
}
@Override
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return top.data;
}
@Override
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
T data = top.data;
top = top.next;
size --;
return data;
}
}
文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/67410.html
