Java模拟栈和队列数据结构的基本示例讲解
栈和队列：
一般是作为程序员的工具，用于辅助构思算法，生命周期较短，运行时才被创建；
访问受限，在特定时刻，只有一个数据可被读取或删除；
是一种抽象的结构，内部的实现机制，对用户不可见，比如用数组、链表来实现栈。
模拟栈结构
同时，只允许一个数据被访问，后进先出
对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数，操作比较快
例，使用数组作为栈的存储结构
publicclassStackS<T>{
privateintmax;
privateT[]ary;
privateinttop;//指针，指向栈顶元素的下标
publicStackS(intsize){
this.max=size;
ary=(T[])newObject[max];
top=-1;
}
//入栈
publicvoidpush(Tdata){
if(!isFull())
ary[++top]=data;
}
//出栈
publicTpop(){
if(isEmpty()){
returnnull;
}
returnary[top--];
}
//查看栈顶
publicTpeek(){
returnary[top];
}
//栈是否为空
publicbooleanisEmpty(){
returntop==-1;
}
//栈是否满
publicbooleanisFull(){
returntop==max-1;
}
//size
publicintsize(){
returntop+1;
}
publicstaticvoidmain(String[]args){
StackS<Integer>stack=newStackS<Integer>(3);
for(inti=0;i<5;i++){
stack.push(i);
System.out.println("size:"+stack.size());
}
for(inti=0;i<5;i++){
Integerpeek=stack.peek();
System.out.println("peek:"+peek);
System.out.println("size:"+stack.size());
}
for(inti=0;i<5;i++){
Integerpop=stack.pop();
System.out.println("pop:"+pop);
System.out.println("size:"+stack.size());
}
System.out.println("----");
for(inti=5;i>0;i--){
stack.push(i);
System.out.println("size:"+stack.size());
}
for(inti=5;i>0;i--){
Integerpeek=stack.peek();
System.out.println("peek:"+peek);
System.out.println("size:"+stack.size());
}
for(inti=5;i>0;i--){
Integerpop=stack.pop();
System.out.println("pop:"+pop);
System.out.println("size:"+stack.size());
}
}
}
上面的例子，有一个maxSize的规定，因为数组是要规定大小的，若想无限制，可以使用其他结构来做存储，当然也可以new一个新的长度的数组。
例，使用LinkedList存储来实现栈
publicclassStackSS<T>{
privateLinkedList<T>datas;
publicStackSS(){
datas=newLinkedList<T>();
}
//入栈
publicvoidpush(Tdata){
datas.addLast(data);
}
//出栈
publicTpop(){
returndatas.removeLast();
}
//查看栈顶
publicTpeek(){
returndatas.getLast();
}
//栈是否为空
publicbooleanisEmpty(){
returndatas.isEmpty();
}
//size
publicintsize(){
returndatas.size();
}
publicstaticvoidmain(String[]args){
StackS<Integer>stack=newStackS<Integer>(3);
for(inti=0;i<5;i++){
stack.push(i);
System.out.println("size:"+stack.size());
}
for(inti=0;i<5;i++){
Integerpeek=stack.peek();
System.out.println("peek:"+peek);
System.out.println("size:"+stack.size());
}
for(inti=0;i<5;i++){
Integerpop=stack.pop();
System.out.println("pop:"+pop);
System.out.println("size:"+stack.size());
}
System.out.println("----");
for(inti=5;i>0;i--){
stack.push(i);
System.out.println("size:"+stack.size());
}
for(inti=5;i>0;i--){
Integerpeek=stack.peek();
System.out.println("peek:"+peek);
System.out.println("size:"+stack.size());
}
for(inti=5;i>0;i--){
Integerpop=stack.pop();
System.out.println("pop:"+pop);
System.out.println("size:"+stack.size());
}
}
}
例，单词逆序，使用Statck结构
publicclassWordReverse{
publicstaticvoidmain(String[]args){
reverse("株式会社");
}
staticvoidreverse(Stringword){
if(word==null)return;
StackSS<Character>stack=newStackSS<Character>();
char[]charArray=word.toCharArray();
intlen=charArray.length;
for(inti=0;i<len;i++){
stack.push(charArray[i]);
}
StringBuildersb=newStringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pop());
}
System.out.println("反转后："+sb.toString());
}
}
打印：
反转后：社会式株
模拟队列(一般队列、双端队列、优先级队列)
队列：
先进先出，处理类似排队的问题，先排的，先处理，后排的等前面的处理完了，再处理
对于插入和移除操作的时间复杂度都为O(1)，从后面插入，从前面移除
双端队列：
即在队列两端都可以insert和remove：insertLeft、insertRight，removeLeft、removeRight
含有栈和队列的功能，如去掉insertLeft、removeLeft，那就跟栈一样了；如去掉insertLeft、removeRight，那就跟队列一样了
一般使用频率较低，时间复杂度O(1)
优先级队列：
内部维护一个按优先级排序的序列。插入时需要比较查找插入的位置，时间复杂度O(N)，删除O(1)
/*
*队列先进先出，一个指针指示插入的位置，一个指针指示取出数据项的位置
*/
publicclassQueueQ<T>{
privateintmax;
privateT[]ary;
privateintfront;//队头指针指示取出数据项的位置
privateintrear;//队尾指针指示插入的位置
privateintnItems;//实际数据项个数
publicQueueQ(intsize){
this.max=size;
ary=(T[])newObject[max];
front=0;
rear=-1;
nItems=0;
}
//插入队尾
publicvoidinsert(Tt){
if(rear==max-1){//已到实际队尾，从头开始
rear=-1;
}
ary[++rear]=t;
nItems++;
}
//移除队头
publicTremove(){
Ttemp=ary[front++];
if(front==max){//列队到尾了，从头开始
front=0;
}
nItems--;
returntemp;
}
//查看队头
publicTpeek(){
returnary[front];
}
publicbooleanisEmpty(){
returnnItems==0;
}
publicbooleanisFull(){
returnnItems==max;
}
publicintsize(){
returnnItems;
}
publicstaticvoidmain(String[]args){
QueueQ<Integer>queue=newQueueQ<Integer>(3);
for(inti=0;i<5;i++){
queue.insert(i);
System.out.println("size:"+queue.size());
}
for(inti=0;i<5;i++){
Integerpeek=queue.peek();
System.out.println("peek:"+peek);
System.out.println("size:"+queue.size());
}
for(inti=0;i<5;i++){
Integerremove=queue.remove();
System.out.println("remove:"+remove);
System.out.println("size:"+queue.size());
}
System.out.println("----");
for(inti=5;i>0;i--){
queue.insert(i);
System.out.println("size:"+queue.size());
}
for(inti=5;i>0;i--){
Integerpeek=queue.peek();
System.out.println("peek:"+peek);
System.out.println("size:"+queue.size());
}
for(inti=5;i>0;i--){
Integerremove=queue.remove();
System.out.println("remove:"+remove);
System.out.println("size:"+queue.size());
}
}
}
/*
*双端队列<spanstyle="white-space:pre"></span>两端插入、删除
*/
publicclassQueueQT<T>{
privateLinkedList<T>list;
publicQueueQT(){
list=newLinkedList<T>();
}
//插入队头
publicvoidinsertLeft(Tt){
list.addFirst(t);
}
//插入队尾
publicvoidinsertRight(Tt){
list.addLast(t);
}
//移除队头
publicTremoveLeft(){
returnlist.removeFirst();
}
//移除队尾
publicTremoveRight(){
returnlist.removeLast();
}
//查看队头
publicTpeekLeft(){
returnlist.getFirst();
}
//查看队尾
publicTpeekRight(){
returnlist.getLast();
}
publicbooleanisEmpty(){
returnlist.isEmpty();
}
publicintsize(){
returnlist.size();
}
}
/*
*优先级队列队列中按优先级排序，是一个有序的队列
*/
publicclassQueueQP{
privateintmax;
privateint[]ary;
privateintnItems;//实际数据项个数
publicQueueQP(intsize){
this.max=size;
ary=newint[max];
nItems=0;
}
//插入队尾
publicvoidinsert(intt){
intj;
if(nItems==0){
ary[nItems++]=t;
}else{
for(j=nItems-1;j>=0;j--){
if(t>ary[j]){
ary[j+1]=ary[j];//前一个赋给后一个小的在后相当于用了插入排序，给定序列本来就是有序的，所以效率O(N)
}else{
break;
}
}
ary[j+1]=t;
nItems++;
}
System.out.println(Arrays.toString(ary));
}
//移除队头
publicintremove(){
returnary[--nItems];//移除优先级小的
}
//查看队尾优先级最低的
publicintpeekMin(){
returnary[nItems-1];
}
publicbooleanisEmpty(){
returnnItems==0;
}
publicbooleanisFull(){
returnnItems==max;
}
publicintsize(){
returnnItems;
}
publicstaticvoidmain(String[]args){
QueueQPqueue=newQueueQP(3);
queue.insert(1);
queue.insert(2);
queue.insert(3);
intremove=queue.remove();
System.out.println("remove:"+remove);
}
}