1.栈
先进后出，后进先出
栈（stack）又称堆栈，是仅允许在表的一端进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
package com.lq.stack;
public class MyStack {
//底层是一个数组
private long []arr;
private int top;
/**
* 默认构造方法
*/
public MyStack(){
arr = new long[10];
top = -1;
}
/**
* 带参数的构造方法
*/
public MyStack(int maxsize){
arr = new long[maxsize];
top = -1;
}
/**
* 添加数据
*/
public void push(int value){
arr[++top] = value;
}
/**
* 移除pop数据
*/
public long pop(){
return arr[top--]; //返回数据并递减
}
/**
* 查看数据
*/
public long peek(){
return arr[top]; //返回数据
}
/**
* 判断 是否是空
*/
public boolean isEmpty(){
return top == -1; //top为-1，就是空
}
/**
* 判断 是否满了
*/
public boolean isFull(){
return top == arr.length-1;
}
}
测试
package com.lq.stack;
public class TestMyStack {
public static void main(String[] args) {
MyStack stack = new MyStack(4);
System.out.println(stack.isEmpty());
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
System.out.println(stack.isFull());
System.out.println(stack.peek());
while (!stack.isEmpty()){
System.out.print(stack.pop()+",");
}
}
}
2.队列
先进先出
队列（queue）是只允许在一端进行插入操作，另一端进行删除操作的线性表。只允许插入的一端称为队尾（rear），只允许删除的一端称为队头（front）。队列是一种先进先出的结构，具有很强烈的顺序特征。队列会记录下零散无序的数据进入队列的顺序，并且在出队列的时候保持这个顺序，以方便程序算法的利用。
package com.lq.queue;
public class MyQueue {
//底层使用数组
private long []arr;
//有效数据的多少
private int elements;
//队头
private int front;
//队尾
private int end;
/**
* 默认构造方法
*/
public MyQueue(){
arr = new long[10];
elements = 0;
front = 0;
end = -1;
}
/**
* 带参数的构造方法，参数为数组大小
*/
public MyQueue(int maxsize){
arr = new long[maxsize];
elements = 0;
front = 0;
end = -1;
}
/**
* 添加数据，从队尾插入
*/
public void insert(long value){
arr[++end] = value;
elements++;
}
/**
* 删除数据，从队尾删除
*/
public long remove(){
elements--;
return arr[front++];
}
/**
* 查看数据，从对头查看
*/
public long peek(){
return arr[front];
}
/**
* 判断是否为空
*/
public boolean isEmpty(){
return elements == 0;
}
/**
* 判断是否满了
*/
public boolean isFull(){
return elements == arr.length;
}
}
测试
public class TestMyQueue {
public static void main(String[] args) {
MyQueue queue = new MyQueue(4);
queue.insert(10);
queue.insert(20);
queue.insert(30);
queue.insert(40);
System.out.println(queue.isFull());
System.out.println(queue.isEmpty());
System.out.println(queue.peek());
while (!queue.isEmpty()){
System.out.print(queue.remove()+",");
}
}
}
3.循环队列
为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。这种循环队列可以以单链表的方式来在实际编程应用中来实现。
对insert和remove方法进行修改
/**
* 添加数据，从队尾插入
*/
public void insert(long value){
if (end == arr.length-1){
end = -1; //如果到达了队列尽头，初始化end
}
arr[++end] = value;
elements++;
}
/**
* 删除数据，从队尾删除
*/
public long remove(){
long value = arr[front++];
if (front == arr.length){
front=0; //如果到达了队列尽头，初始化front
}
elements--;
return value;
}
网友评论