文章目录
- 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);
}
}
}
}
运行结果：
满了
0
1
2
3
4
5
6
7
8
9
空的
3. 参考链接
Java泛型详解（史上最全泛型知识详解）
数据结构：栈和队列(Stack & Queue)【详解】
