07、数据结构和算法 - 实战：栈的设计与实现
1.1 什么是栈
栈是一种抽象数据结构，是对现实世界对象的模拟。比如，自助餐厅中的一叠盘子，新盘子放在这一叠盘子的最上面，取得时候也是从最上面取。将其抽象出来就是栈，这是最合适的抽象方式。
栈的特点
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
1.2 JAVA模拟对栈的实现
栈是用数组实现的，内部定义了一个数组，一个表示最大容量的值以及一个指向栈顶元素的top变量。构造方法根据参数规定的容量创建一个新栈。
常用方法
push()方法：是向栈中压入元素，指向栈顶的变量top加1，使它指向原顶端数据项上面的一个位置，并在这个位置上存储一个数据。
pop()方法：返回top变量指向的元素，然后将top变量减一，便移除了数据项。要知道 top 变量指向的始终是栈顶的元素。
peek()：检索但不删除此队列的头，如果此队列为空，则返回 null。
package com.yuanxw.datastructure.chapter7;
import java.util.NoSuchElementException;
public class CustomArrayStack<E> {
private int top = -1;
private int capacity;
private E[] stack;
private static final int DEFAULT_CAPACITY = 11;
/**
* 定义默认构造函数，默认容量为
*/
public CustomArrayStack() {
this(DEFAULT_CAPACITY);
}
/**
* 指定容量大小
*
* @param capacity
*/
public CustomArrayStack(int capacity) {
this.capacity = capacity;
this.stack = (E[]) new Object[this.capacity];
this.top = -1;
}
/**
* 判断是否为空
*
* @return
*/
public boolean isEmpty() {
return top == -1;
}
/**
* 判断是否为空
*
* @return
*/
public boolean isFull() {
return top == capacity;
}
public int size() {
return (this.top + 1);
}
/**
* 添加元素
*
* @param element
* @return
*/
public boolean push(E element) {
if (isFull()) {
throw new IllegalStateException("Stack full");
}
this.stack[++top] = element;
return true;
}
/**
* 检索但不删除此队列的头，如果此队列为空，则返回 null 。
*
* @return
*/
public E peek() {
if (isEmpty()) {
return null;
}
return stack[top];
}
/**
* 检索并删除此队列的头，如有必要，等待元素可用。
*
* @return
*/
public E pop() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return this.stack[top--];
}
/**
* 是否包含元素
* @param element
* @return
*/
public boolean contains(E element){
for (E elem : this.stack) {
if(elem.equals(element) || elem == element){
return true;
}
}
return false;
}
/**
* 清空元素列表
* @return
*/
public boolean clear(){
this.stack = (E[]) new Object[this.capacity];
this.top = -1;
return true;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
if(isEmpty()){
return builder.append("[]").toString();
}
builder.append("[");
for (int i = (size()-1); i >= 0; i--) {
builder.append(this.stack[i]).append(",");
}
builder.deleteCharAt(builder.length() -1);
builder.append("]");
return builder.toString();
}
public static void main(String[] args) {
CustomArrayStack customArrayStack = new CustomArrayStack(3);
customArrayStack.push("Message 1");
customArrayStack.push("Message 2");
customArrayStack.push("Message 3");
// customArrayStack.add("Message 4");
System.out.println("统计自定义customArrayStack对象元素个数："+customArrayStack.size());
System.out.println("列出customArrayStack对象元素：" + customArrayStack);
System.out.println("------------------------------------------------------------------------------------");
System.out.println("获得第一个元素: " + customArrayStack.peek());
System.out.println("判断列表是否包含【Message 2】这个元素:" + customArrayStack.contains("Message 2"));
System.out.println("------------------------------------------------------------------------------------");
System.out.println("当前customArrayStack对象中pop()数据值为：" + customArrayStack.pop());
System.out.println("当前customArrayStack对象中peek()数据值为：" + customArrayStack.peek());
System.out.println("------------------------------------------------------------------------------------");
System.out.println("当前customArrayStack对象中pop()数据值为：" + customArrayStack.pop());
System.out.println("查看列出customArrayStack对象所有节点元素：" + customArrayStack);
System.out.println("------------------------------------------------------------------------------------");
customArrayStack.clear();
System.out.println("清空customArrayStack对象所有元素：" + customArrayStack);
}
}
执行结果：
统计自定义customArrayStack对象元素个数：3
列出customArrayStack对象元素：[Message 3,Message 2,Message 1]
------------------------------------------------------------------------------------
获得第一个元素: Message 3
判断列表是否包含【Message 2】这个元素:true
------------------------------------------------------------------------------------
当前customArrayStack对象中pop()数据值为：Message 3
当前customArrayStack对象中peek()数据值为：Message 2
------------------------------------------------------------------------------------
当前customArrayStack对象中pop()数据值为：Message 2
查看列出customArrayStack对象所有节点元素：[Message 1]
------------------------------------------------------------------------------------
清空customArrayStack对象所有元素：[]