一、棧 Stack
1.特點
（1）棧是一種線性數(shù)據(jù)結(jié)構(gòu)
（2）規(guī)定只能從棧頂添加元素，從棧頂取出元素
（3）是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)（Last First Out）LIFO
2.具體實現(xiàn)
Java中可以直接調(diào)用方法來實現(xiàn)棧
如何自己寫代碼來實現(xiàn)棧呢？
先定義一個接口，方便后邊進(jìn)行調(diào)用
package com.algo.lesson.lesson02.stack;
public interface Stack_I<T> {
//入棧
void push(T ele);
//出棧
T pop();
//查看棧頂元素
T peek();
//判斷是否為空
boolean isEmpty();
//后去棧中元素
int getSize();
}
接下來來實現(xiàn)棧的方法，調(diào)用接口，完善方法：
package com.algo.lesson.lesson02.stack;
import com.algo.lesson.lesson01.MyArr;
//以數(shù)組作為棧頂?shù)牡讓訑?shù)據(jù)結(jié)構(gòu)
public class ArrStack<T> implements Stack_I<T> {
private MyArr<T>data;
int size;
public ArrStack() {
this.data=new MyArr<>(100);
this.size=0;
}
@Override
public void push(T ele) {
//在數(shù)組尾部添加元素
this.data.add(ele);
this.size++;
}
@Override
public T pop() {
if(isEmpty()){
return null;
}
this.size--;
return this.data.removeBFromLast();
}
@Override
public T peek() {
return this.data.getLastValue();
}
@Override
public boolean isEmpty() {
return this.size==0;
}
@Override
public int getSize() {
return this.size;
}
}
以上就是方法的代碼，接下來，寫個main函數(shù)來調(diào)用，檢查方法是否正確
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+" ");
}
//結(jié)束時間
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);
}
}
注：其中l(wèi)ong startTime=System.nanoTime();方法是獲取一個時間（單位毫秒）
在程序運行前和運行后個添加一個，最后將兩個時間相減，得到程序運行時間。
3.時間復(fù)雜度分析
二、隊列
1.特點
（1）隊列也是一種線性數(shù)據(jù)結(jié)構(gòu)
（2）只能從一端添加元素，另一端取出元素
（3）是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（FIFO——fist in fist out ）
2.具體實現(xiàn)
Java中也可以直接調(diào)用隊列的方法：
自己的實現(xiàn)：
接口：
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;//隊列中元素的個數(shù)
*/
public ArrQueue(){
this.data=new MyArr<>(50);
}
@Override
public void offer(T ele) {
this.data.add(ele);
}
@Override
public T poll() {
if(isEmpty()){
return null;
}
return this.data.removeByIndex(0);
}
@Override
public T peek() {
if(isEmpty()){
return null;
}
return this.data.getValueByIndex(0);
}
@Override
public int getSize() {
return this.data.getSize();
}
@Override
public boolean isEmpty() {
return this.data.isEmpty();
}
}
3.出現(xiàn)的問題
入隊列時間復(fù)雜度為O(n)，因為在出隊時，元素要前移，會出現(xiàn)假溢出的情況。
所以就出現(xiàn)了循環(huán)隊列來解決這個問題
循環(huán)隊列：
front記錄隊首，tail記錄隊尾，隊尾達(dá)到容積時，返回到隊頭，將空位置補上，可以繼續(xù)存儲數(shù)據(jù)。
package com.algo.lesson.lesson02.queue;
import java.util.Random;
/*
基于Java中的數(shù)組進(jìn)行二次封裝,制作一個可變數(shù)組
*/
//泛型:就是類型作為參數(shù)
public class LoopArr<T> {
private T[] data;//保存數(shù)據(jù)
private int size;//數(shù)組中實際存放元素的個數(shù)
private int front;//隊首
private int tail;//隊尾
int capacity;//容積
//構(gòu)造函數(shù)
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]);
}
//獲取數(shù)組中實際存放元素的個數(shù)
public int getSize() {
return this.size;
}
//獲取數(shù)組的容積
public int getCapacity() {
return this.capacity;
}
//判斷數(shù)組是否為空
public boolean isEmpty() {
return this.front == this.tail;
}
//向數(shù)組中添加元素(尾部)
public void add(T item) {
//判斷數(shù)組是否滿
if ((this.tail + 1) % this.capacity == this.front) {
//擴容
resize((this.capacity-1)*2+1);
}
//從index位置開始元素需要進(jìn)行后移
this.data[this.tail] = item;
this.tail = (this.tail + 1) % this.capacity;
//更新this.size
this.size++;
}
private void resize(int newCapacity) {
System.out.println("resize:" + newCapacity);
T[] newData = (T[]) (new Object[newCapacity]);
//將原數(shù)組駕到新數(shù)組里
for (int i = 0; i < this.size; i++) {
newData[i] = this.data[(this.front+i)%this.capacity];
}
//改變?nèi)萜? 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;
}
@Override
public 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);
}
@Override
public void offer(T ele) {
this.data.add(ele);
}
@Override
public T poll() {
return this.data.remove();
}
@Override
public T peek() {
return this.data.getValueByIndex();
}
@Override
public int getSize() {
return this.data.getSize();
}
@Override
public boolean isEmpty() {
return this.data.isEmpty();
}
}
4.循環(huán)隊列的復(fù)雜度分析
三、棧和隊列的互相實現(xiàn)
既然我們了解了棧和隊列，知道了這兩種數(shù)據(jù)結(jié)構(gòu)十分相似，也就可以大膽假設(shè)以下，可不可以相互實現(xiàn)，不是用上面所寫的以數(shù)組為底層，而是相互為底層存儲。
1.用棧來實現(xiàn)隊列
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.用隊列實現(xiàn)棧
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();
}
}
這就是這兩種數(shù)據(jù)結(jié)構(gòu)相互實現(xiàn)的代碼
在LeetCode中也有相對應(yīng)的題目：
力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長平臺（棧實現(xiàn)隊列）文章來源：http://www.zghlxwxcb.cn/news/detail-807662.html
力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長平臺（隊列實現(xiàn)棧）文章來源地址http://www.zghlxwxcb.cn/news/detail-807662.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——Java實現(xiàn)棧和隊列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
