栈
基本概念
栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆。取走时，只能从上面一件一件取。读和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一端称栈底。插入一般称为进栈，删除则称为退栈。 栈也称为后进先出表。
代码
public class MyStack {
//底层实现是一个数组
private long[] arr;
// 数组下标
private int top;
/**
* 默认构造方法
*/
public MyStack() {
arr = new long[10];
top = -1;
}
/**
* 带参数的构造方法
*
* @param maxSize 数组的初始化长度
*/
public MyStack(int maxSize) {
arr = new long[maxSize];
top = -1;
}
/**
* 添加数据（压栈）
*
* @param value 添加的数值
*/
public void push(int value) {
// ++top后top由-1变为了0，即第一个值添加到arr[0]的位置
arr[++top] = value;
}
/**
* 移除数据
*
* @return
*/
public long pop() {
return arr[top--];
}
/**
* 查看栈顶数据
*
* @return
*/
public long peek() {
return arr[top];
}
/**
* 判断是否为空
*
* @return
*/
public boolean isEmpty() {
return top == -1;
}
/**
* 判断是否满了
*
* @return
*/
public boolean isFull() {
return top == arr.length - 1;
}
}
测试
public class TestMyStack {
public static void main(String[] args) {
MyStack ms = new MyStack(4);
ms.push(0);
ms.push(1);
ms.push(2);
ms.push(3);
System.out.println(ms.isEmpty());
System.out.println(ms.isFull());
System.out.println(ms.peek());
while (!ms.isEmpty()){
System.out.print(ms.pop()+" ");
}
System.out.println();
System.out.println(ms.isEmpty());
System.out.println(ms.isFull());
}
}
结果
false
true
3
3 2 1 0
true
false
从结果中可以看到，往栈中压入数据的顺序(0,1,2,3)和弹出数据的顺序(3,2,1,0)刚好相反。
队列
基本概念
队列的操作是在两端进行的，其中一端只能进行插入，该端称为队列的队尾，而另一端只能进行删除，该端称为队列的队首。
队列在我们日常生活中经常碰到，例如，排队买东西，谁先来，谁先买，买完就走，谁后来，谁在队的最后面排队。队列的运算规则是FIFO（first in first out），或者叫做先进先出。
代码
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;
}
/**
* 带参数的构造方法
*
* @param maxSize
*/
public MyQueue(int maxSize) {
arr = new long[maxSize];
elements = 0;
front = 0;
end = -1;
}
/**
* 从队尾插入数据
*
* @param value
*/
public void insert(long value) {
if (end == arr.length - 1) {
end = -1;
}
//每次都从队尾插入数据
arr[++end] = value;
elements++;
}
/**
* 从队头删除数据
*
* @return
*/
public long remove() {
long value = arr[front++];
if (front == arr.length) {
front = 0;
}
elements--;
return value;
}
/**
* 从队头查看数据
*
* @return
*/
public long peek() {
return arr[front];
}
/**
* 判断队列是否为空
*
* @return
*/
public boolean isEmpty() {
return elements == 0;
}
/**
* 判断队列是否满了
*
* @return
*/
public boolean isFull() {
return elements == arr.length;
}
}
测试
public class TestMyqueue {
public static void main(String[] args) {
MyQueue mq = new MyQueue(4);
mq.insert(0);
mq.insert(1);
mq.insert(2);
mq.insert(3);
System.out.println(mq.isEmpty());
System.out.println(mq.isFull());
System.out.println(mq.peek());
while (!mq.isEmpty()){
System.out.print(mq.remove()+" ");
}
System.out.println();
System.out.println(mq.isEmpty());
System.out.println(mq.isFull());
}
}
结果
false
true
0
0 1 2 3
true
false
从结果中可以看到，往队列中添加数据的顺序(0,1,2,3)和移除数据的顺序(0,1,2,3)相同。
