java实现数据结构——栈Stack与队列Queue

栈（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() + "");
}
}

}

 

队列的实现

1. /** 
2.  * 队列的实现 
3.  * @param <E>  
4.  * @author <a href="mailto:[e-mail]" mce_href="mailto:[e-mail]">Bao Yiming</a> 
5.  */  
6. public class Queue<E> {  
7.     Object[] data = null;  
8.     private int capacity; // capacity： 队的容量  
9.     private int tail; // tail： 队尾指针  
10.     /** 
11.      * 初始化为声明大小，则设置为10。 
12.      */  
13.     Queue() {  
14.         this(10);  
15.     }  
16.     /** 
17.      * 初始化队列，声明保存数据的数组大小。 
18.      * @param initialSize 队列的初始化大小 
19.      */  
20.     Queue(int initialSize) {  
21.         if (initialSize >= 0) {  
22.             this.capacity = initialSize;  
23.             data = new Object[initialSize];  
24.             tail = 0;  
25.         } else {  
26.             throw new RuntimeException("初始化大小不能小于0：" + initialSize);  
27.         }  
28.     }  
29.     /** 
30.      * 判断队列是否为空 
31.      * @return 
32.      */  
33.     public boolean empty() {  
34.         return tail == 0 ? true : false;  
35.     }  
36.     /** 
37.      * 在队尾插入元素 
38.      * @param e 待插入的元素 
39.      * @return 
40.      */  
41.     public boolean add(E e) {  
42.         ensureCapacity();  
43.         data[tail] = e;  
44.         ++tail;  
45.         return true;  
46.     }  
47.     /** 
48.      * 获取队首的元素内容，但不将该元素出队。 
49.      * @return 
50.      */  
51.     public E peek() {  
52.         return (E) data[0];  
53.     }  
54.     /** 
55.      * 将队首元素出队。 
56.      * @return 
57.      */  
58.     public E poll() {  
59.         E e = (E) data[0];  
60.         for (int index = 1; index < tail; ++index) {  
61.             data[index - 1] = data[index];  
62.         }  
63.         data[tail - 1] = null;  
64.         --tail;  
65.         return e;  
66.     }  
67.     /** 
68.      * 检查存储数据的数组容量，如果数组已经满，则扩充容量；否则不操作。 
69.      */  
70.     private void ensureCapacity() {  
71.         int index;  
72.         if (tail == capacity) {  
73.             capacity *= 2;  
74.             Object[] newData = new Object[capacity];  
75.             for (index = 0; index < tail; ++index) {  
76.                 newData[index] = data[index];  
77.             }  
78.             data = newData;  
79.         }  
80.     }  
81.     @Override  
82.     public String toString() {  
83.         String str = "";  
84.         for (int index = 0; index < tail; ++index) {  
85.             if (data[index] != null) {  
86.                 str += (data[index] + " ");  
87.             }  
88.         }  
89.         return str;  
90.     }  
91. }