前言：之前介绍了线性表，今天来介绍一下堆栈/队列。
1：堆栈主要特点就是只允许固定的一段插入和删除。
采用的是先进后出的方式 如果洗盘子，再比如我们计算机中的递归调用 ，判断字符串是否为回文字符串，利用堆栈来计算算术表达式
我们只能从栈顶取出元素。而且元素也必须从栈顶进入。
同时堆栈又分为：顺序堆栈和链式堆栈
1.1.：顺序堆栈
数据集合：主要是通过数组的形式存储元素。
操作集合：可以定义为一个接口
1 public interface Stack { 2 public void push(Object object); //进栈 3 public Object pop(); //出栈 4 public Object getTop(); //获取栈顶的元素 5 public boolean notEmpty(); //判断栈是否为空 6 }
（2）顺序堆栈的具体实现
1 package com.hone.stack; 2 3 public class SeqStack implements Stack{ 4 final int defaultSize=10; //默认元素个数 5 int top; //栈顶位置 6 Object[] stack; //数组对象 7 int maxStackSize; //最大数据元素的个数 8 9 //创建一个构造方法可以初始化defaultSize 10 public SeqStack() { 11 initiate(defaultSize); 12 } 13 14 //创建一个带参数的构造函数，用于 15 public SeqStack(int sz){ 16 initiate(sz); 17 } 18 //初始化maxStackSize top stack 对象 19 private void initiate(int sz) { 20 maxStackSize=sz; 21 top=0; 22 stack=new Object[sz]; 23 } 24 25 /* 26 * 进栈 27 */ 28 @Override 29 public void push(Object obj) { 30 if (top==maxStackSize) { 31 System.out.println("堆栈已满！"); 32 } 33 stack[top]=obj; //保存刚传进来的元素并且马上建立一个空的栈顶 34 top++; //产生新栈顶位置（只有栈顶没有元素） 35 } 36 //出栈 37 @Override 38 public Object pop() { 39 if (top==0) { 40 System.out.println("堆栈已空"); 41 } 42 top--; //产生原来栈顶位置 43 //减1的原因（因为这里面加入了一个元素之后都会新开辟一个栈顶，所以无论怎么样都会有一个空的栈顶） 44 return stack[top]; //返回原来栈顶的元素 45 } 46 //获得栈顶位置的元素 47 @Override 48 public Object getTop() { 49 return stack[top-1]; //返回原栈顶元素 50 } 51 //判断栈是否为空 52 @Override 53 public boolean notEmpty() { 54 return (top>0); 55 } 56 }
1.2：链式节点
首先需要创建节电类，包含元素和下一个结点
1 /* 2 * 整个类使用于封装节点的类，包含两个元素一个是element/next 3 */ 4 public class Node { 5 Object element; 6 public Node next; 7 8 // 定义一个构造函数用于结点 9 public Node(Node nextval) { 10 next = nextval; 11 } 12 13 // 定义一个构造函数用于初始化结点和元素 14 public Node(Object o, Node nextval) { 15 element = o; 16 next = nextval; 17 } 18 19 public Object getElement() { 20 return element; 21 } 22 23 public void setElement(Object element) { 24 this.element = element; 25 } 26 27 public Node getNext() { 28 return next; 29 } 30 31 public void setNext(Node next) { 32 this.next = next; 33 } 34 35 //将获得的元素转化为String类型 36 public String toString(){ 37 return element.toString(); 38 } 39 }
链式栈的实现类：这里面只需要一个head节点就可以了
package com.hone.stack.lin; import com.hone.stack.Stack; public class LinStack implements Stack{ Node head ; //获得链式堆栈的头节点 int size; //结点的个数 //定义一个构造函数用于初始化head结点以及size的大小 public LinStack() { head=null; size=0; } //入栈 从头部开始插入 @Override public void push(Object object) { head=new Node(object, head); size++; } //出栈，从头部开始 @Override public Object pop() { if (size==0) { System.out.println("堆栈为空"); } Object object=head.getElement(); //这里面element行不行呢？ head=head.next; size--; return object; } //获得头部顶端的一个元素 @Override public Object getTop() { return head.getElement(); //这里面Element行不行？ } //判断栈是否为空，只需要判断head结点是否为空就可 @Override public boolean notEmpty() { return head!=null; } }
2：队列
队列的主要特点是从一端进，另一端出。队尾入，队头出。因此形成了先进先出的存储模式。
如果将队头和队尾连接起来就成了循环队列。
在队列中必须是队头为head节点，因为只有head节点才有next节点，否则，在出队的时候队尾无法找到rear.next节点
其次，由于顺序队列很容易存在“假溢出”情况 ，因此一般情况下都用顺序循环队列的形式
2.1：顺序循环队列 表现形式任然是数组形式
常用的操作集合：
1 public interface queue { 2 public void append(Object object); //入队 3 public Object delete(); //出队 4 public Object getFront(); //获得队头点的 5 public boolean notEmpty(); //判断队列是否为空 6 }
具体的顺序队列的实现类：
1 package com.hone.queue; 2 3 public class SeqQueue implements queue{ 4 5 static final int defaultSize=10; 6 int front; 7 int rear; 8 int count; //元素计数器 9 int maxsize; //数据元素最大的个数 10 Object [] data; //用于保存队列函数 11 12 public SeqQueue() { 13 initiate(defaultSize); 14 } 15 16 private void initiate(int sz) { 17 maxsize=sz; 18 front=rear=0; 19 count=0; 20 data=new Object[sz]; 21 } 22 23 //向一个队列中开始添加元素 入队列 24 @Override 25 public void append(Object object) { 26 if (count>0&&front==rear) { 27 System.out.println("队列已满"); 28 } 29 data[rear]=object; 30 rear= (rear+1)%maxsize; //加1取余获得最后队尾的数值 31 count++; //除以maxsize的原因是循环队列 32 } 33 34 //出队列 35 @Override 36 public Object delete() { 37 if (count==0) { 38 System.out.println("队列已空"); 39 } 40 Object temp=data[front]; 41 front=(front+1)%maxsize; //原来的队头+1后求模得到新的队头位置 42 count--; 43 return temp; 44 } 45 46 //获得队头的位置 47 @Override 48 public Object getFront() { 49 if (count==0) { 50 System.out.println("队列为空！"); 51 } 52 return data[front]; 53 } 54 55 @Override 56 public boolean notEmpty() { 57 return count!=0; 58 } 59 60 }
2.2：链式队列的具体实现形式
如前面所说：一个结点都必须包含元素+结点
1 /* 2 * 整个类使用于封装节点的类 3 */ 4 public class Node { 5 Object element; 6 public Node next; 7 8 // 定义一个构造函数用于初始化头结点 9 public Node(Node nextval) { 10 next = nextval; 11 } 12 13 // 定义一个构造函数用于初始化除了头结点以外的节点 14 public Node(Object o, Node nextval) { 15 element = o; 16 next = nextval; 17 } 18 19 public Object getElement() { 20 return element; 21 } 22 23 public void setElement(Object element) { 24 this.element = element; 25 } 26 27 public Node getNext() { 28 return next; 29 } 30 31 public void setNext(Node next) { 32 this.next = next; 33 } 34 35 //将获得的元素转化为String类型 36 public String toString(){ 37 return element.toString(); 38 } 42 }
链式队列的具体实现：
1 package com.hone.queue.lin; 2 3 4 public class LinQueue implements queue{ 5 Node rear; //获得尾结点 6 Node front; //获得尾结点 7 int count; //获得节点的个数 8 9 //定义一个函数用于初始化 10 private void initiate() { 11 rear=null; 12 front= null; 13 count=0; 14 } 15 16 public LinQueue() { 17 initiate(); 18 } 19 20 public LinQueue(int sz){ 21 initiate(); 22 } 23 24 //用链式的方法入队列 25 @Override 26 public void append(Object object) { 27 Node node=new Node(object, null); 28 if (rear!=null) { //如果队尾不为空，则在队尾加上一个新创建的节点 29 rear.next=node; //同时将新创建的节点（包含元素和指针）添加到队尾 30 rear=node; 31 } 32 if (front==null) { 33 front=node; 34 } 35 count++; 36 } 37 38 //用链式的方法出队列 39 @Override 40 public Object delete() { 41 if (count==0) System.out.println("队列已空"); 42 43 Object o=front.getElement(); 44 front=front.next; 45 count--; 46 return o; 47 } 48 49 //获取链式队列的队头位置 50 @Override 51 public Object getFront() { 52 if (count==0) { 53 System.out.println("队列已空！"); 54 } 55 return front.getElement(); 56 } 57 58 //判断链式队列是否为空 59 @Override 60 public boolean notEmpty() { 61 return count!=0; 62 } 63 }
2.3：队列同时具有优先级的情况先，将打破了队列 “先入先出” 的原则，优先按照优先级别来处理。
生活中也会分为轻重缓急。
那么此时，队列中各个节点，必须包括优先级别+元素
类似于前面的Node类，这里我们必须加上+ElementPripority类
1 package com.hone.queue.priority; 2 3 4 //定义element元素的属性，包含pripority和element两个属性 5 public class ElementPripority { 6 private Object element; 7 private int pripority; 8 9 // 定义一个构造函数用于初始化element ,pripority 10 public ElementPripority(Object o, int p) { 11 element = o; 12 pripority = p; 13 } 14 15 public Object getElement() { 16 return element; 17 } 18 19 public void setElement(Object element) { 20 this.element = element; 21 } 22 23 public int getPripority() { 24 return pripority; 25 } 26 27 public void setPripority(int pripority) { 28 this.pripority = pripority; 29 } 30 31 }
具体的实现：
1 package com.hone.queue.priority; 2 3 import com.hone.queue.queue; 4 5 public class SeqQueue implements queue{ 6 7 static final int defaultSize=10; 8 int front; 9 int rear; 10 int count; //元素计数器 11 int maxsize; //数据元素最大的个数 12 ElementPripority [] data; //用于保存队列的数组 13 14 public SeqQueue() { 15 initiate(defaultSize); 16 } 17 18 public SeqQueue(int sz){ 19 this.initiate(sz); 20 } 21 22 private void initiate(int sz) { 23 maxsize=sz; 24 front=rear=0; 25 count=0; 26 data=new ElementPripority[sz]; //创建一个数组并且规定他的大小 27 } 28 29 //从一个空的队列中开始添加元素 入队列的时候不用管他的pripority属性 30 @Override 31 public void append(Object object) { 32 if (count>0&&front==rear) { 33 System.out.println("队列已满"); 34 } 35 data[rear]=(ElementPripority) object; //加入的时候只是在乎他的element属性 36 rear= (rear+1)%maxsize; //加1取余获得最后队尾的数值 37 count++; 38 } 39 40 //出队列 41 @Override 42 public Object delete() { 43 if (count==0) { 44 System.out.println("队列已空"); 45 } 46 //首先要寻找最高优先级别的数，保存在min中 47 ElementPripority min=data[0]; 48 int minIndex=0; 49 for (int i = 0; i < count; i++) { 50 if(data[i].getPripority()<min.getPripority()){ 51 min=data[i]; 52 minIndex=i; //这个方法是在于找到优先级最小的值 53 } 54 } 55 56 for (int j = minIndex+1; j < count; j++) { 57 data[j-1]=data[j]; //因为暂时还没有涉及到除去，只是交换数据，让 58 //优先级别最高的排到队头去 59 } 60 rear--; 61 count--; 62 return min; 63 } 64 //获得队头的位置 65 @Override 66 public Object getFront() { 67 if (count==0) { 68 System.out.println("队列为空！"); 69 } 70 //首先要寻找最高优先级别的数，保存在min中 71 ElementPripority min=data[0]; 72 int minIndex=0; 73 for (int i = 0; i < count; i++) { 74 if(data[i].getPripority()<min.getPripority()){ 75 min=data[i]; 76 minIndex=i; //这个方法是在于找到优先级最小的值 77 } 78 } 79 return min; 80 } 81 82 @Override 83 public boolean notEmpty() { 84 return count!=0; 85 } 86 }
以上就是队列和堆栈的各种具体实现：
我们可以用堆栈来模拟回文字符串，或者将进程来模拟计算机中的“进程”。
利用堆栈+队列 来测试回文字符串
1 import com.hone.queue.SeqQueue; 2 import com.hone.stack.SeqStack; 3 4 public class TestOfHuiwen { 5 public static void main(String[] args) { 6 String string1="ABCDEDCBA"; 7 String string2="HGJEIEJHG"; 8 9 huiwen(string1); 10 huiwen(string2); 11 } 12 13 public static void huiwen(String s){ 14 int n=s.length(); 15 SeqStack mystack=new SeqStack(); 16 SeqQueue myqueue=new SeqQueue(); 17 18 //先将所有的字符串都加入多对应的队列中去 19 for (int i = 0; i < n; i++) { 20 mystack.push(s.substring(i, i+1)); 21 myqueue.append(s.substring(i, i+1)); 22 } 23 24 //从外面取出 25 while(myqueue.notEmpty()&&mystack.notEmpty()){ 26 if (! myqueue.delete().equals(mystack.pop())) { 27 System.out.println(s+" 不是回文字符串！"); 28 return ; //如果不是回文字符串则直接回到上面的while循环中 29 } 30 } 31 System.out.println(s+" 是回文字符串！"); 32 } 33 34 }
这个就是堆栈和队列的一些基本只是。
当然，这些在java中也已经给我们封装好了，不需要我们具体去写，只需要调用接口即可。
但是在c ,c++中经常利用与堆栈来进行，多项式的加减啊，用后缀表达式来求取表达式的值。
作为一个初学者，仍然是一知半解。