数据结构——Java实现栈和队列

一、栈 Stack

1.特点

（1）栈是一种线性数据结构

（2）规定只能从栈顶添加元素，从栈顶取出元素

（3）是一种先进后出的数据结构（Last First Out）LIFO

2.具体实现

Java中可以直接调用方法来实现栈

如何自己写代码来实现栈呢？

先定义一个接口，方便后边进行调用

package com.algo.lesson.lesson02.stack;public interface Stack_I<T> {//入栈void push(T ele);//出栈T pop();//查看栈顶元素T peek();//判断是否为空boolean isEmpty();//后去栈中元素int getSize();
}

接下来来实现栈的方法，调用接口，完善方法：

package com.algo.lesson.lesson02.stack;import com.algo.lesson.lesson01.MyArr;//以数组作为栈顶的底层数据结构
public class ArrStack<T> implements Stack_I<T> {private MyArr<T>data;int size;public ArrStack() {this.data=new MyArr<>(100);this.size=0;}@Overridepublic void push(T ele) {//在数组尾部添加元素this.data.add(ele);this.size++;}@Overridepublic T pop() {if(isEmpty()){return null;}this.size--;return this.data.removeBFromLast();}@Overridepublic T peek() {return this.data.getLastValue();}@Overridepublic boolean isEmpty() {return this.size==0;}@Overridepublic int getSize() {return this.size;}
}

以上就是方法的代码，接下来，写个main函数来调用，检查方法是否正确

package com.algo.lesson.lesson02.stack;import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class StackTest<T> {public void test(Stack_I<T>stack, List<T> list){//开始时间long startTime=System.nanoTime();for(int i=0;i<list.size();i++){stack.push(list.get(i));}System.out.println(stack.getSize());while(!stack.isEmpty()){T ele=stack.pop();System.out.println(ele+"  ");}//结束时间long endTime=System.nanoTime();System.out.println("总耗时："+(endTime-startTime)/100000000.0);}public static void main(String[] args) {StackTest<Integer>stackTest=new StackTest<>();Stack_I<Integer>stack=new ArrStack<>();List<Integer>list=new ArrayList<>();Random random=new Random();for(int i=0;i<100;i++){int val= random.nextInt(1000);list.add(val);}stackTest.test(stack,list);}
}

注：其中long startTime=System.nanoTime();方法是获取一个时间（单位毫秒）

在程序运行前和运行后个添加一个，最后将两个时间相减，得到程序运行时间。

3.时间复杂度分析

二、队列

1.特点

（1）队列也是一种线性数据结构

（2）只能从一端添加元素，另一端取出元素

（3）是一种先进先出的数据结构（FIFO——fist in fist out ）

2.具体实现

Java中也可以直接调用队列的方法：

自己的实现：

接口：

package com.algo.lesson.lesson02.queue;public interface Queue_I<T> {void offer(T ele);//入队T poll();//出队T peek();//查找队首元素int getSize();boolean isEmpty();}

方法代码：

package com.algo.lesson.lesson02.queue;import com.algo.lesson.lesson01.MyArr;public class ArrQueue<T>implements Queue_I<T> {private MyArr<T>data;/*private int size;//队列中元素的个数
*/public ArrQueue(){this.data=new MyArr<>(50);}@Overridepublic void offer(T ele) {this.data.add(ele);}@Overridepublic T poll() {if(isEmpty()){return null;}return this.data.removeByIndex(0);}@Overridepublic T peek() {if(isEmpty()){return null;}return this.data.getValueByIndex(0);}@Overridepublic int getSize() {return this.data.getSize();}@Overridepublic boolean isEmpty() {return this.data.isEmpty();}
}

3.出现的问题

入队列时间复杂度为O(n)，因为在出队时，元素要前移，会出现假溢出的情况。

所以就出现了循环队列来解决这个问题

循环队列：

front记录队首，tail记录队尾，队尾达到容积时，返回到队头，将空位置补上，可以继续存储数据。

package com.algo.lesson.lesson02.queue;import java.util.Random;/*
基于Java中的数组进行二次封装,制作一个可变数组*/
//泛型:就是类型作为参数
public class LoopArr<T> {private T[] data;//保存数据private int size;//数组中实际存放元素的个数private int front;//队首private int tail;//队尾int capacity;//容积//构造函数public LoopArr(int capacity) {if (capacity <= 0) {this.capacity = 11;} else {this.capacity = capacity + 1;}this.size = 0;this.front = this.tail = 0;this.data = (T[]) (new Object[this.capacity]);}//获取数组中实际存放元素的个数public int getSize() {return this.size;}//获取数组的容积public int getCapacity() {return this.capacity;}//判断数组是否为空public boolean isEmpty() {return this.front == this.tail;}//向数组中添加元素(尾部)public void add(T item) {//判断数组是否满if ((this.tail + 1) % this.capacity == this.front) {//扩容resize((this.capacity-1)*2+1);}//从index位置开始元素需要进行后移this.data[this.tail] = item;this.tail = (this.tail + 1) % this.capacity;//更新this.sizethis.size++;}private void resize(int newCapacity) {System.out.println("resize:" + newCapacity);T[] newData = (T[]) (new Object[newCapacity]);//将原数组驾到新数组里for (int i = 0; i < this.size; i++) {newData[i] = this.data[(this.front+i)%this.capacity];}//改变容器this.data = newData;this.capacity = newCapacity;//将this.front置零this.front=0;this.tail=this.size;}//获取指定位置的值public T getValueByIndex() {if(isEmpty()){return null;}return this.data[this.front];}//移除队首元素public T remove() {if (isEmpty()) {return null;}//删除操作的核心/*1.找到删除的位置2.删除位置之后的元素要前移 arr[j-1]=arr[j]*/T delValue = this.data[this.front];this.front = (this.front + 1) % this.capacity;this.size--;//判断是否缩容if (this.size < this.capacity / 4 && this.capacity / 2 > 0) {resize((this.capacity-1) / 2 +1);}return delValue;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder("[");for (int i = 0; i < this.size; i++) {sb.append(this.data[i]);if (i != this.size - 1) {sb.append(",");}}sb.append("]");return sb.toString();}
}

package com.algo.lesson.lesson02.queue;public class LoopQueue<T> implements Queue_I<T>{private LoopArr<T>data;//容器public LoopQueue(){this.data=new LoopArr<>(100);}@Overridepublic void offer(T ele) {this.data.add(ele);}@Overridepublic T poll() {return this.data.remove();}@Overridepublic T peek() {return this.data.getValueByIndex();}@Overridepublic int getSize() {return this.data.getSize();}@Overridepublic boolean isEmpty() {return this.data.isEmpty();}
}

4.循环队列的复杂度分析

三、栈和队列的互相实现

既然我们了解了栈和队列，知道了这两种数据结构十分相似，也就可以大胆假设以下，可不可以相互实现，不是用上面所写的以数组为底层，而是相互为底层存储。

1.用栈来实现队列

import java.util.Stack;class MyQueue {private Stack<Integer> A;private Stack<Integer> B;public MyQueue() {A = new Stack<>();B = new Stack<>();}public void push(int x) {while (!B.isEmpty()) {A.push(B.pop());}A.push(x);while (!A.isEmpty()) {B.push(A.pop());}}public int pop() {return B.pop();}public int peek() {return B.peek();}public boolean empty() {return B.isEmpty();}
}

2.用队列实现栈

import java.util.LinkedList;
import java.util.Queue;class MyStack {private Queue<Integer> queue1;private Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {queue2.add(x);while (!queue1.isEmpty()) {queue2.add(queue1.remove());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}public int pop() {return queue1.remove();}public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}

这就是这两种数据结构相互实现的代码

在LeetCode中也有相对应的题目：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台（栈实现队列）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台（队列实现栈）