Java实现栈和队列
本文内容纲要：
栈：LIFO（后进先出）
队列：FIFO（先进先出）
栈的顺序存储结构实现：
/**
*基于数组实现的顺序栈
*@param<E>
*/
publicclassStack<E>{
privateObject[]data=null;
privateintmaxSize=0;//栈容量
privateinttop=-1;//栈顶指针
/**
*构造函数：根据给定的size初始化栈
*/
Stack(){
this(10);//默认栈大小为10
}
Stack(intinitialSize){
if(initialSize>=0){
this.maxSize=initialSize;
data=newObject[initialSize];
top=-1;
}else{
thrownewRuntimeException("初始化大小不能小于0："+initialSize);
}
}
//判空
publicbooleanempty(){
returntop==-1?true:false;
}
//进栈,第一个元素top=0；
publicbooleanpush(Ee){
if(top==maxSize-1){
thrownewRuntimeException("栈已满，无法将元素入栈！");
}else{
data[++top]=e;
returntrue;
}
}
//查看栈顶元素但不移除
publicEpeek(){
if(top==-1){
thrownewRuntimeException("栈为空！");
}else{
return(E)data[top];
}
}
//弹出栈顶元素
publicEpop(){
if(top==-1){
thrownewRuntimeException("栈为空！");
}else{
return(E)data[top--];
}
}
//返回对象在堆栈中的位置，以1为基数
publicintsearch(Ee){
inti=top;
while(top!=-1){
if(peek()!=e){
top--;
}else{
break;
}
}
intresult=top+1;
top=i;
returnresult;
}
}
栈的链式存储结构实现：
publicclassLinkStack<E>{
//链栈的节点
privateclassNode<E>{
Ee;
Node<E>next;
publicNode(){}
publicNode(Ee,Nodenext){
this.e=e;
this.next=next;
}
}
privateNode<E>top;//栈顶元素
privateintsize;//当前栈大小
publicLinkStack(){
top=null;
}
//当前栈大小
publicintlength(){
returnsize;
}
//判空
publicbooleanempty(){
returnsize==0;
}
//入栈：让top指向新创建的元素，新元素的next引用指向原来的栈顶元素
publicbooleanpush(Ee){
top=newNode(e,top);
size++;
returntrue;
}
//查看栈顶元素但不删除
publicNode<E>peek(){
if(empty()){
thrownewRuntimeException("空栈异常！");
}else{
returntop;
}
}
//出栈
publicNode<E>pop(){
if(empty()){
thrownewRuntimeException("空栈异常！");
}else{
Node<E>value=top;//得到栈顶元素
top=top.next;//让top引用指向原栈顶元素的下一个元素
value.next=null;//释放原栈顶元素的next引用
size--;
returnvalue;
}
}
}
基于LinkedList实现的栈结构：
importjava.util.LinkedList;
/**
*基于LinkedList实现栈
*在LinkedList实力中只选择部分基于栈实现的接口
*/
publicclassStackList<E>{
privateLinkedList<E>ll=newLinkedList<E>();
//入栈
publicvoidpush(Ee){
ll.addFirst(e);
}
//查看栈顶元素但不移除
publicEpeek(){
returnll.getFirst();
}
//出栈
publicEpop(){
returnll.removeFirst();
}
//判空
publicbooleanempty(){
returnll.isEmpty();
}
//打印栈元素
publicStringtoString(){
returnll.toString();
}
}
队列的顺序存储结构实现
publicclassQueue<E>{
privateObject[]data=null;
privateintmaxSize;//队列容量
privateintfront;//队列头，允许删除
privateintrear;//队列尾，允许插入
//构造函数
publicQueue(){
this(10);
}
publicQueue(intinitialSize){
if(initialSize>=0){
this.maxSize=initialSize;
data=newObject[initialSize];
front=rear=0;
}else{
thrownewRuntimeException("初始化大小不能小于0："+initialSize);
}
}
//判空
publicbooleanempty(){
returnrear==front?true:false;
}
//插入
publicbooleanadd(Ee){
if(rear==maxSize){
thrownewRuntimeException("队列已满，无法插入新的元素！");
}else{
data[rear++]=e;
returntrue;
}
}
//返回队首元素，但不删除
publicEpeek(){
if(empty()){
thrownewRuntimeException("空队列异常！");
}else{
return(E)data[front];
}
}
//出队
publicEpoll(){
if(empty()){
thrownewRuntimeException("空队列异常！");
}else{
Evalue=(E)data[front];//保留队列的front端的元素的值
data[front++]=null;//释放队列的front端的元素
returnvalue;
}
}
//队列长度
publicintlength(){
returnrear-front;
}
}
循环队列的顺序存储结构实现
importjava.util.Arrays;
publicclassLoopQueue<E>{
publicObject[]data=null;
privateintmaxSize;//队列容量
privateintrear;//队列尾，允许插入
privateintfront;//队列头，允许删除
privateintsize=0;//队列当前长度
publicLoopQueue(){
this(10);
}
publicLoopQueue(intinitialSize){
if(initialSize>=0){
this.maxSize=initialSize;
data=newObject[initialSize];
front=rear=0;
}else{
thrownewRuntimeException("初始化大小不能小于0："+initialSize);
}
}
//判空
publicbooleanempty(){
returnsize==0;
}
//插入
publicbooleanadd(Ee){
if(size==maxSize){
thrownewRuntimeException("队列已满，无法插入新的元素！");
}else{
data[rear]=e;
rear=(rear+1)%maxSize;
size++;
returntrue;
}
}
//返回队首元素，但不删除
publicEpeek(){
if(empty()){
thrownewRuntimeException("空队列异常！");
}else{
return(E)data[front];
}
}
//出队
publicEpoll(){
if(empty()){
thrownewRuntimeException("空队列异常！");
}else{
Evalue=(E)data[front];//保留队列的front端的元素的值
data[front]=null;//释放队列的front端的元素
front=(front+1)%maxSize;//队首指针加1
size--;
returnvalue;
}
}
//队列长度
publicintlength(){
returnsize;
}
//清空循环队列
publicvoidclear(){
Arrays.fill(data,null);
size=0;
front=0;
rear=0;
}
}
队列的链式存储结构实现
publicclassLinkQueue<E>{
//链栈的节点
privateclassNode<E>{
Ee;
Node<E>next;
publicNode(){
}
publicNode(Ee,Nodenext){
this.e=e;
this.next=next;
}
}
privateNodefront;//队列头，允许删除
privateNoderear;//队列尾，允许插入
privateintsize;//队列当前长度
publicLinkQueue(){
front=null;
rear=null;
}
//判空
publicbooleanempty(){
returnsize==0;
}
//插入
publicbooleanadd(Ee){
if(empty()){//如果队列为空
front=newNode(e,null);//只有一个节点，front、rear都指向该节点
rear=front;
}else{
Node<E>newNode=newNode<E>(e,null);
rear.next=newNode;//让尾节点的next指向新增的节点
rear=newNode;//以新节点作为新的尾节点
}
size++;
returntrue;
}
//返回队首元素，但不删除
publicNode<E>peek(){
if(empty()){
thrownewRuntimeException("空队列异常！");
}else{
returnfront;
}
}
//出队
publicNode<E>poll(){
if(empty()){
thrownewRuntimeException("空队列异常！");
}else{
Node<E>value=front;//得到队列头元素
front=front.next;//让front引用指向原队列头元素的下一个元素
value.next=null;//释放原队列头元素的next引用
size--;
returnvalue;
}
}
//队列长度
publicintlength(){
returnsize;
}
}
基于LinkedList实现队列结构
/**
*使用java.util.Queue接口,其底层关联到一个LinkedList（双端队列）实例.
*/
importjava.util.LinkedList;
importjava.util.Queue;
publicclassQueueList<E>{
privateQueue<E>queue=newLinkedList<E>();
//将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回true，
//如果当前没有可用的空间，则抛出IllegalStateException。
publicbooleanadd(Ee){
returnqueue.add(e);
}
//获取，但是不移除此队列的头。
publicEelement(){
returnqueue.element();
}
//将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，
//此方法通常要优于add(E)，后者可能无法插入元素，而只是抛出一个异常。
publicbooleanoffer(Ee){
returnqueue.offer(e);
}
//获取但不移除此队列的头；如果此队列为空，则返回null
publicEpeek(){
returnqueue.peek();
}
//获取并移除此队列的头，如果此队列为空，则返回null
publicEpoll(){
returnqueue.poll();
}
//获取并移除此队列的头
publicEremove(){
returnqueue.remove();
}
//判空
publicbooleanempty(){
returnqueue.isEmpty();
}
}
本文内容总结：
原文链接：https://www.cnblogs.com/CherishFX/p/4608880.html