栈(Stack)作为一个先进后出(FILO) 的线性结构,只支持在栈顶的插入和弹出。
队列(Queue)作为一个先进先出(FIFO) 的线性结构,支持在队首获取元素,在对尾插入元素。
栈的实现:
public class StackDemo<E> {
private Object[] data = null;
private int capacity;
private int top;
/**
* 默认栈容量为10
*/
public StackDemo() {
this(10);
}
/**
* 初始化栈容量
*
* @param initSize
*/
public StackDemo(int initSize) {
if (initSize >= 0) {
capacity = initSize;
data = new Object[initSize];
top = 0;
} else {
throw new RuntimeException("初始化栈容量大小不能小于0" + initSize);
}
}
/**
* 判断栈是否为空
*
* @return
*/
public boolean isEmpty() {
return top == 0 ? true : false;
}
/**
* 获取栈顶元素,但是不弹出
*
*/
public E peek() {
return (E) data[top - 1];
}
/**
* 弹出栈顶元素
*
* @return
*/
public E pop() {
if (isEmpty()) {
throw new RuntimeException("栈已空,没有元素可以弹出。");
}
return (E) data[--top];
}
/**
* 向栈顶压入e
*
* @param e
* @return
*/
public boolean push(E e) {
ensureCapacity();
data[top] = e;
top++;
return true;
}
/**
* 检查存储数据数组容量,如果数组已满,则扩容否则不操作。
*/
private void ensureCapacity() {
if (top == capacity) {
capacity *= 2;
Object[] newData = new Object[capacity];
for (int i = 0; i < top; i++) {
newData[i] = data[i];
}
data = newData;
}
}
@Override
public String toString() {
String string = "";
for (int i = 0; i < top; i++) {
string += (data[i] + " ");
}
return string;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成的方法存根
StackDemo<Double> stackDemo = new StackDemo<>();
for (int i = 0; i < 15; i++) {
stackDemo.push(i+1.0);
System.out.println(stackDemo.toString());
}
System.out.println(stackDemo.peek() + " ");
for (int i = 0; i < 15; i++) {
System.out.println(stackDemo.pop() + "");
}
}
}
队列的实现
- /**
- * 队列的实现
- * @param <E>
- * @author <a href="mailto:bao.yiming@live.cn" mce_href="mailto:bao.yiming@live.cn">Bao Yiming</a>
- */
- public class Queue<E> {
- Object[] data = null;
- private int capacity; // capacity: 队的容量
- private int tail; // tail: 队尾指针
- /**
- * 初始化为声明大小,则设置为10。
- */
- Queue() {
- this(10);
- }
- /**
- * 初始化队列,声明保存数据的数组大小。
- * @param initialSize 队列的初始化大小
- */
- Queue(int initialSize) {
- if (initialSize >= 0) {
- this.capacity = initialSize;
- data = new Object[initialSize];
- tail = 0;
- } else {
- throw new RuntimeException("初始化大小不能小于0:" + initialSize);
- }
- }
- /**
- * 判断队列是否为空
- * @return
- */
- public boolean empty() {
- return tail == 0 ? true : false;
- }
- /**
- * 在队尾插入元素
- * @param e 待插入的元素
- * @return
- */
- public boolean add(E e) {
- ensureCapacity();
- data[tail] = e;
- ++tail;
- return true;
- }
- /**
- * 获取队首的元素内容,但不将该元素出队。
- * @return
- */
- public E peek() {
- return (E) data[0];
- }
- /**
- * 将队首元素出队。
- * @return
- */
- public E poll() {
- E e = (E) data[0];
- for (int index = 1; index < tail; ++index) {
- data[index - 1] = data[index];
- }
- data[tail - 1] = null;
- --tail;
- return e;
- }
- /**
- * 检查存储数据的数组容量,如果数组已经满,则扩充容量;否则不操作。
- */
- private void ensureCapacity() {
- int index;
- if (tail == capacity) {
- capacity *= 2;
- Object[] newData = new Object[capacity];
- for (index = 0; index < tail; ++index) {
- newData[index] = data[index];
- }
- data = newData;
- }
- }
- @Override
- public String toString() {
- String str = "";
- for (int index = 0; index < tail; ++index) {
- if (data[index] != null) {
- str += (data[index] + " ");
- }
- }
- return str;
- }
- }