（泛型+栈+队列+可变不可变）的实现（java版）

文章目录

1. 介绍
2. 代码实现
- 2.1 普通的栈
- 2.2 普通的循环队列
- 2.3 泛型栈
- 2.4 泛型循环队列
- 2.5 泛型可变栈
- 2.6 泛型可变队列
- 2.7 部分测试
3. 参考链接

如果你之前没有了解过栈或者队列，可以看看本文最后的链接，里面很详细

1. 介绍

泛型，泛指一切类型。
栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

2. 代码实现

2.1 普通的栈

class StackX{private int[] arr;private int index = 0;public StackX(int size){this.arr = new int[size];}// 判断是否为空public boolean isEmpty(){if(index == 0)return true;return false;}// 判断是否满了public boolean isFull(){if(arr != null && index == arr.length)return true;return false;}// 入栈public void push(int x){if(!isFull()){arr[index++] = x;}}// 出栈public int pop(){if(!isEmpty()){return arr[--index];}System.out.println("空");return 0;}// 获取栈顶元素public int getTop(){if(!isEmpty())return arr[index - 1];System.out.println("空的");return 0;}
}

2.2 普通的循环队列

class Queue{private int front = 0;private int last = 0;private int[] arr;public Queue(int size){arr = new int[size];}// 判空public boolean isEmpty(){if(front == last)return true;return false;}// 判满public boolean isFull(){if((last + 1) % arr.length == front)return true;return false;}// 入队public void add(int x){if(!isFull()){arr[front % arr.length] = x;front ++ ;}}// 出队public int pop(){if(!isEmpty()){last++;return arr[(last - 1) % arr.length];}System.out.println("空队列");return 0;}
}

2.3 泛型栈

class StackY<E>{private E[] arr;private int index = 0;public StackY(int size){this.arr = (E[])new Object[size];}// 判断是否为空public boolean isEmpty(){if(index == 0)return true;return false;}// 判断是否满了public boolean isFull(){if(arr != null && index == arr.length)return true;return false;}// 入栈public void push(E x){if(!isFull()){arr[index++] = x;return;}System.out.println("满了！！");}// 出栈public E pop(){if(!isEmpty()){return arr[--index];}System.out.println("空");return null;}// 获取栈顶元素public E getTop(){if(!isEmpty())return arr[index - 1];System.out.println("空的");return null;}
}

2.4 泛型循环队列

class QueueY<E>{private int front = 3;private int last = 3;private E[] arr;public QueueY(int size){// 牺牲一个空间进行判断arr = (E[])new Object[size + 1];}// 判空public boolean isEmpty(){if(front == last)return true;return false;}// 判满public boolean isFull(){if((front + 1) % arr.length == last){System.out.println("满了");return true;}return false;}// 入队public void add(E x){if(!isFull()){arr[front % arr.length] = x;front ++ ;}}// 出队public E pop(){if(!isEmpty()){last++;return arr[(last - 1) % arr.length];}return null;}
}

2.5 泛型可变栈

其实是每当出现栈满的时候，会进行增加一倍的操作

public class Stack2X<E> {private E[] arr = (E[]) new Object[10];private int flag = 0;public void add(E x){if(flag == arr.length){E[] arrnew = (E[]) new Object[arr.length * 2];for(int i = 0; i < arr.length; i++){arrnew[i] = arr[i];}arr = arrnew;}arr[flag] = x;flag++;}public E get(){if(flag == 0){return null;}else{E x = arr[flag - 1];flag--;return x;}}
}

2.6 泛型可变队列

每当队列满了以后进行扩展，利用（余数+原队列长度）进行扩展

public class Queue2<E> {private E[] arr = (E[]) new Object[4]; private int add = 0;private int get = 0;public void add(E x) {if(add - get == arr.length) {E[] arrnew = (E[]) new Object[arr.length * 2];for(int i = get; i < add; i++) {arrnew[i % arrnew.length] = arr[i % arr.length];}arr = arrnew;}arr[add % arr.length] = x;add++;}public E get() {if(add == get) {return null;}else {E x = arr[get % arr.length];get++;return x;}}
}

2.7 部分测试


public class Test {public static void main(String[] args) {QueueY<String> demo = new QueueY<>(10);for(int i =  0; i < 11; i++){demo.add(i + "");}for(int i = 0; i <11; i++){String out = demo.pop();if(out == null){System.out.println("空的");}else{System.out.println(out);}}}
}