数据结构-栈 队列(数组实现栈、队列、循环队列)
栈和队列
栈
1栈描述
先进后出 底层是一个数组
2类的概念
永远记住
类是由类的属性和方法组成的，在类中写其它的就是错误
3 栈
/**
* @Auther: liuhaidong
* Data: 2019/9/15 0015、17:14
* Description:
* @version: 1.0
*/
public class MyStack {
//底层是一个数组
private long[] arr;
private int top;
/*
* @Author liuhaidong
* @Description 默认的构造方法
* @Date 17:19 2019/9/15 0015
**/
public MyStack(){
arr = new long[10];
top = -1;
}
/*
* @Author liuhaidong
* @Description 带参数的构造方法
* @Date 17:20 2019/9/15 0015
**/
public MyStack(int maxsize){
arr = new long[maxsize];
top = -1;
}
/*
* @Author liuhaidong
* @Description 添加数据
* @Date 17:21 2019/9/15 0015
**/
public void push(int value){
arr[++top] =value;
}
/*
* @Author liuhaidong
* @Description 移除数据
* @Date 17:23 2019/9/15 0015
**/
public long pop(){
return arr[top--];
}
/*
* @Author liuhaidong
* @Description 查看数据
* @Date 17:24 2019/9/15 0015
**/
public long peek(){
return arr[top];
}
/*
* @Author liuhaidong
* @Description 判断是否为空
* @Date 17:24 2019/9/15 0015
**/
public boolean isEmpty(){
return top == -1;
}
/*
* @Author liuhaidong
* @Description 判断是否满了
* @Date 17:26 2019/9/15 0015
**/
public boolean isFull(){
return top == arr.length -1;
}
}
4 主函数
/**
* @Auther: liuhaidong
* Data: 2019/9/15 0015、17:32
* Description:
* @version: 1.0
*/
public class testMyStack {
public static void main(String[] args) {
MyStack myStack = new MyStack(4);
myStack.push(23);
myStack.push(65);
myStack.push(11);
myStack.push(13);
System.out.println(myStack.isEmpty());
System.out.println(myStack.isFull());
System.out.println(myStack.peek());
while (!myStack.isEmpty()){
System.out.println(myStack.pop() + ",");
}
System.out.println(myStack.isEmpty());
System.out.println(myStack.isFull());
}
}
上述方式不行，如果一直push会报bug
所以需要改进
public class MyStack {
private Integer[] arr;
private Integer size;
public MyStack(){
arr = new Integer[10];
size = 10;
}
public MyStack (int initSize) {
if (initSize < 0) {
throw new IllegalArgumentException("The init size is less than 0");
}
arr = new Integer[initSize];
size = 0;
}
public Integer peek() {
if (size == 0) {
return null;
}
return arr[size - 1];
}
public void push(int obj) {
if (size == arr.length) {
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
arr[size++] = obj;
}
public Integer pop() {
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
return arr[--size];
}
}
继续对上述代码进行改进，对数组能进行扩容，对类型能进行自动化
public class MyStack1<E> {
private Object[] stack;
private int size;
public MyStack1() {
stack = new Object[10];
//初始长度为10
}
public MyStack1(int initSize) {
stack = new Object[initSize];
//初始长度为10
}
/** * 判断栈是否为空 * */
public boolean isEmpty() {
return size == 0;
}
/** * 返回栈顶的一个元素，但是不进行出栈操作 * */
public E peek() {
if(isEmpty()) {
return null;
}
return (E)stack[size -1];
//返回栈顶元素
}
/** * 弹出 * */
public E pop() {
E e = peek();
//取得栈顶数据
if(size > 0) {
//检查栈中是否有数据
stack[size - 1] = null;
//将出栈后的位置置为空
size--;
}
//将栈中元素个数减一
return e;
}
/** * 压入 * */
public E push(E item) {
ensureCapacity(size + 1);
stack[size++] = item;
return item;
}
/** * 当栈满的时候，对栈进行扩容 * */
private void ensureCapacity(int size) {
int len = stack.length;
if(size > len) {
//数组已满
int newLen = 10;
//每次数组扩充的容量
stack = Arrays.copyOf(stack, newLen);
}
}
/** * 打印出栈中所有的数据 * */
public void printStack() {
System.out.println("开始进行出栈：");
while(size > 0) {
System.out.println("出栈：" + pop());
}
System.out.println("出栈操作结束！");
}
}
以上代码显然还是有问题，扩容不对
public class testMyStack {
public static void main(String[] args) {
MyStack1<String> myStack = new MyStack1<String>(4);
myStack.push("23");
myStack.push("23");
myStack.push("23");
myStack.push("23");
myStack.push("23");
myStack.push("23");
}
}
队列
简单队列
/**
* @Auther: liuhaidong
* Data: 2019/9/15 0015、17:40
* Description:
* @version: 1.0
*/
public class MyQueue {
//底层使用数组
private long[] arr;
//有效数据的大小
private int elements;
//队头
private int front;
//队尾
private int end;
/*
* @Author liuhaidong
* @Description 默认的构造方法
* @Date 17:41 2019/9/15 0015
**/
public MyQueue(){
arr = new long[10];
elements =0;
front =0;
end = -1;
}
/*
* @Author liuhaidong
* @Description 带参数的构造方法，参数为数组的大小
* @Date 17:43 2019/9/15 0015
**/
public MyQueue(int maxsize){
arr = new long[maxsize];
elements =0;
front =0;
end = -1;
}
/*
* @Author liuhaidong
* @Description 添加数据，从队尾插入
* @Date 17:43 2019/9/15 0015
**/
public void insert(long value){
arr[++end] = value;
elements++;
}
/*
* @Author liuhaidong
* @Description 删除数据，从队头删除
* @Date 17:43 2019/9/15 0015
**/
public long remove(){
elements--;
return arr[front++];
}
/*
* @Author liuhaidong
* @Description 查看数据，从队头查看
* @Date 17:52 2019/9/15 0015
**/
public long peek(){
return arr[front];
}
/*
* @Author liuhaidong
* @Description 判断是否为空
* @Date 17:53 2019/9/15 0015
**/
public boolean isEmpty(){
return elements ==0;
}
/*
* @Author liuhaidong
* @Description 判断是否满了
* @Date 17:54 2019/9/15 0015
**/
public boolean isFull(){
return elements == arr.length;
}
}
主函数
/**
* @Auther: liuhaidong
* Data: 2019/9/15 0015、17:56
* Description:
* @version: 1.0
*/
public class testMyQueue {
public static void main(String[] args) {
MyQueue mq = new MyQueue(4);
mq.insert(23);
mq.insert(1);
mq.insert(2);
mq.insert(18);
System.out.println(mq.isFull());
System.out.println(mq.isEmpty());
System.out.println(mq.peek());
while (!mq.isEmpty()){
System.out.println(mq.remove()+" ");
}
//以下会报错
mq.insert(23);
}
}
这里的重点是从队尾插入，从对头删除。
数组越界
ArrayIndexOutOfBoundsException
public class ArrayIndexOutOf BoundsExceptionextends IndexOutOfBoundsException用非法索引访问数组时抛出的异常。如果索引为负或大于等于数组大小，则该索引为非法索引。
循环队列
/**
* @Auther: liuhaidong
* Data: 2019/9/15 0015、18:31
* Description:
* @version: 1.0
*/
public class MyCycleQueue {
//底层使用数组
private long[] arr;
//有效数据的大小
private int elements;
//队头
private int front;
//队尾
private int end;
/*
* @Author liuhaidong
* @Description 默认的构造方法
* @Date 17:41 2019/9/15 0015
**/
public MyCycleQueue(){
arr = new long[10];
elements =0;
front =0;
end = -1;
}
/*
* @Author liuhaidong
* @Description 带参数的构造方法，参数为数组的大小
* @Date 17:43 2019/9/15 0015
**/
public MyCycleQueue(int maxsize){
arr = new long[maxsize];
elements =0;
front =0;
end = -1;
}
/*
* @Author liuhaidong
* @Description 循环队列，解决插入bug的问题
* @Date 18:27 2019/9/15 0015
**/
public void insert(long value){
if(end == arr.length -1){
end = -1;
}
arr[++end] = value;
elements++;
}
/*
* @Author liuhaidong
* @Description 删除数据，从队头删除
* @Date 17:43 2019/9/15 0015
**/
public long remove(){
long value = arr[front++];
if(front == arr.length){
front =0;
}
elements--;
return value;
}
/*
* @Author liuhaidong
* @Description 查看数据，从队头查看
* @Date 17:52 2019/9/15 0015
**/
public long peek(){
return arr[front];
}
/*
* @Author liuhaidong
* @Description 判断是否为空
* @Date 17:53 2019/9/15 0015
**/
public boolean isEmpty(){
return elements ==0;
}
/*
* @Author liuhaidong
* @Description 判断是否满了
* @Date 17:54 2019/9/15 0015
**/
public boolean isFull(){
return elements == arr.length;
}
}
主函数
/**
* @Auther: liuhaidong
* Data: 2019/9/15 0015、18:33
* Description:
* @version: 1.0
*/
public class CycleQueueTest {
public static void main(String[] args) {
MyCycleQueue mq = new MyCycleQueue(4);
mq.insert(23);
mq.insert(1);
mq.insert(2);
mq.insert(18);
System.out.println(mq.isFull());
System.out.println(mq.isEmpty());
System.out.println(mq.peek());
while (!mq.isEmpty()){
System.out.println(mq.remove()+" ");
}
mq.insert(23);
mq.insert(1);
mq.insert(2);
mq.insert(18);
while (!mq.isEmpty()){
System.out.println(mq.remove()+" ");
}
}
}
这样就不会有问题了
查看8道真题和解析