摘要：返回栈顶元素，未出栈出栈，返回栈顶元素，同时从栈中移除该元素栈顶元素，代表空栈栈容量，默认为存放元素的数组添加元素，从栈顶数组尾部插入扩容从栈顶添加元素复制元素更新栈顶
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;
/**
* 存放元素的数组
*/
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;
}
/**
* 添加元素，从栈顶（数组尾部）插入
* @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;
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/67410.html
