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

时间:2021-12-26 14:42:00

栈(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:bao.yiming@live.cn" mce_href="mailto:bao.yiming@live.cn">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. }