本文旨作于收集整理使用！！
导航
一、栈
允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不含任何数据元素的栈称为空栈。栈又称为后进先出或先进后出的线性表。
如下图所示，我们在容器最顶端的位置称为栈顶，每放入一个数字我们称之为入栈，入栈的数字就处在栈顶。每弹出一个数字我们称之为出栈，而之前的数就处于栈顶了。
换个角度，我们经常使用手机浏览器浏览网页，我们每点击浏览一个网页，那么就相当于入栈，系统会展示栈顶的页面，我们点击返回则相当于出栈，系统显示之前入栈的界面，当然这个界面现在也已经处于栈顶额。
栈的应用：无处不在的撤销操作、程序调用的系统栈、括号/符号匹配等。
1、使用数组实现栈
import java.util.Arrays;
public class ArrayStack<E> {
private int size;
private int top;
private E[] data;
public ArrayStack(int capacity) {
if (size<=0){
throw new IllegalArgumentException("capacity can't number=0");
}else {
data=(E[]) new Object[capacity];
size=capacity;
top=-1;
}
}
public ArrayStack() {
data=(E[]) new Object[10];
size=10;
top=-1;
}
public void push(E e){
//判断数组是否需要扩容
isGrow(top+1);
data[++top]=e;
}
public void pop(){
if (size>=0){
data[top]=null;
top--;
}else {
throw new IllegalArgumentException("pop failed. no data");
}
}
public E peek(){
E e=null;
if (size>=0){
e=data[top];
}else {
throw new IllegalArgumentException("No elements are available！");
}
return e;
}
/**
* 对数组实现动态扩容，若数组容量不够，理论上直接将容量扩展一倍
* @param minCapacity 入栈后数组长度容量
*/
private void isGrow(int minCapacity) {
int capacity=size;
int newCapacity=0;
if (capacity<=minCapacity){
if ((capacity<<1)>Integer.MAX_VALUE){
newCapacity=Integer.MAX_VALUE;
}else {
newCapacity=(capacity<<1);
}
this.size=newCapacity;
Arrays.copyOf(data,newCapacity);
}
}
}
2、使用链表实现栈
链表实现方式也很简单，我么直接使用第一章实现的栈！
public class LikeListStack<E> {
private SingleLinkedList<E> stack;
public LikeListStack() {
stack=new SingleLinkedList<>();
}
public void push(E e){
stack.addLast(e);
}
//暂时将SingleLinkedList中的size设置为public，为了严禁可以提供get方法访问
public void pop(){
stack.remove(stack.size-1);
}
public E peek(){
E e = stack.getLast();
return e;
}
}
二、队列
队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列则是一种先进先出原则。
队列的应用：任务执行顺序调度（如打印队列）、模拟现实世界中的队列（如排队等）、异步数据传输等。
队列的实现也可以用数组和链表实现。
2.1、循环队列（数组实现）
public class LoopQueue<E> {
private int maxsize;
private int front;
private int rear;
private E[] data;
private int nItems;
//循环队列必须制定队列的长度
public LoopQueue(int maxsize) {
if (maxsize<=0){
throw new IllegalArgumentException("maxsize can't number=0");
}else {
this.maxsize = maxsize;
data= (E[]) new Object[maxsize];
front=0;
rear=-1;
nItems=0;
}
}
public void insert(E e){
if (!isFull()){
if (rear==maxsize-1){
rear=0;
}
data[++rear]=e;
nItems++;
}
}
public void remove(){
if (nItems<=0){
throw new IllegalArgumentException("No elements are available！");
}else {
data[front]=null;
front++;
}
if (front==maxsize){
front=0;
}
nItems--;
}
public boolean isFull(){
return maxsize==nItems;
}
}
2.2、单向队列（链表实现）
当然我们也可以扩展，只能在尾部删除头部插入，下面只实现头部删除尾部插入的操作。
public class singleQueue<E> {
private SingleLinkedList<E> queue;
public singleQueue() {
queue=new SingleLinkedList<>();
}
public void insert(E e){
queue.addLast(e);
}
public void remove(){
queue.remove(0);
}
//.......
}
网友评论