一、 栈与队列的定义
栈[Stack]:是一种限定仅在表尾进行插入和删除操作的线性表；即后进先出（LIFO-last in first out），最后插入的元素最先出来。
队列[Queue]：是一种限定仅在表头进行删除操作，仅在表尾进行插入操作的线性表；即先进先出（FIFO-first in first out）:最先插入的元素最先出来。
二、 用数组实现栈
1、栈的接口定义
/**
* 定义栈的接口
*
* @author zhuhuix
* @date 2020-05-01
*/
public interface Stack {
/**
* 入栈
* @param object 入栈元素
*/
void push(Object object);
/**
* 出栈
* @return 出栈元素
*/
Object pop();
/**
* 获取元素个数
* @return 元素个数
*/
int getElementCount();
/**
* 遍历栈的元素
*/
void traverse();
}
2、栈的接口实现
/**
* 栈的接口实现
*
* @author zhuhuix
* @date 2020-05-01
*/
public class StackImpl implements Stack {
protected Object[] element;
protected int elementCount;
private int defaultSize = 16;
private int maxSize;
StackImpl() {
element = new Object[defaultSize];
maxSize = defaultSize;
}
StackImpl(int size) {
element = new Object[size];
maxSize = size;
}
@Override
public void push(Object object) {
//如果元素个数已经达到数组的最大个数，则进行扩容
if (elementCount == maxSize) {
element = Arrays.copyOf(element, elementCount + defaultSize);
}
element[elementCount++] = object;
}
// 本代码未实现数组的自动缩小，具体方法可参考JDK
@Override
public Object pop() {
if (elementCount == 0) {
throw new ArrayIndexOutOfBoundsException("栈中无元素");
}
Object object = element[--elementCount];
element[elementCount] = null;
return object;
}
@Override
public int getElementCount() {
return elementCount;
}
@Override
public void traverse() {
for (int i = 0; i < elementCount; i++) {
System.out.print(element[i] + ",");
}
System.out.println();
}
}
3、栈的测试
public class StackTest {
public static void main(String[] args) {
Stack stack = new StackImpl();
//第一次入栈:压入1-15
for (int i = 0; i < 16; i++) {
stack.push(i);
}
System.out.println("第一次入栈后元素个数为：" + stack.getElementCount());
stack.traverse();
//第二次入栈:压入16-31
for (int i = 16; i < 32; i++) {
stack.push(i);
}
System.out.println("第二次入栈后的元素个数为：" + stack.getElementCount());
stack.traverse();
//第一次出栈:取出31-16
for (int i = 0; i < 16; i++) {
stack.pop();
}
System.out.println("第一次出栈后的元素个数为：" + stack.getElementCount());
stack.traverse();
//第二次出栈:取出15-0
for (int i = 0; i < 16; i++) {
stack.pop();
}
System.out.println("第二次出栈后的元素个数为：" + stack.getElementCount());
stack.traverse();
//栈中无元素，出栈报错
stack.pop();
}
}
三、 用数组实现队列
1、队列的接口定义
/**
* 定义队列的接口
*
* @author zhuhuix
* @date 2020-05-01
*/
public interface Queue {
/**
* 获取队列大小
* @return 队列大小
*/
int getMaxSize();
/**
* 入队
* @param object 入队元素
*/
void push(Object object);
/**
* 出队
* @return 出栈元素
*/
Object pull();
/**
* 获取元素个数
* @return 元素个数
*/
int getElementCount();
/**
* 获取队头元素
* @return 队头元素
*/
Object getFront();
/**
* 获取队尾元素
* @return 队尾元素
*/
Object getRear();
/**
* 遍历队列的元素
*/
void traverse();
}
2、队列的接口实现
/**
* 队列的接口实现
*
* @author zhuhuix
* @date 2020-05-01
*/
public class QueueImpl implements Queue {
protected Object[] element;
protected int elementCount;
//队头
private int front;
//队尾
private int rear;
private int defaultSize = 16;
private int maxSize;
QueueImpl() {
element = new Object[defaultSize];
maxSize = defaultSize;
front = 0;
rear = -1;
}
QueueImpl(int size) {
element = new Object[size];
maxSize = size;
front = 0;
rear = -1;
}
@Override
public int getMaxSize() {
return maxSize;
}
@Override
public void push(Object object) {
//如果元素个数已经达到数组的最大个数，则进行扩容
if (elementCount == maxSize) {
throw new ArrayIndexOutOfBoundsException("队列已满，请先进行出队");
}
element[++rear] = object;
if (rear == element.length) {
rear = -1;
}
elementCount++;
}
@Override
public Object pull() {
if (elementCount == 0) {
throw new ArrayIndexOutOfBoundsException("队列中无元素");
}
Object object = element[front];
element[front] = null;
front++;
elementCount--;
//队列清空，队头队尾恢复初始值
if (elementCount == 0) {
front = 0;
rear = -1;
}
return object;
}
@Override
public int getElementCount() {
return elementCount;
}
@Override
public Object getFront() {
if (elementCount == 0) {
System.out.print("队头无元素");
return null;
}
return element[front];
}
@Override
public Object getRear() {
if (elementCount == 0) {
System.out.print("队尾无元素");
return null;
}
return element[rear];
}
@Override
public void traverse() {
if (elementCount == 0) {
return;
}
for (int i = front; i <= rear; i++) {
System.out.print(element[i] + ",");
}
System.out.println();
}
}
3、队列的测试
public class QueueTest {
public static void main(String[] args) {
Queue queue = new QueueImpl();
//获取队列大小
System.out.println("队列中最大可放置元素：" + queue.getMaxSize());
//第一次入队列:压入1-15
for (int i = 0; i < 16; i++) {
queue.push(i);
}
System.out.println("第一次入队后元素个数为：" + queue.getElementCount());
queue.traverse();
System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
//第一次出队:取出0-15
for (int i = 0; i < 16; i++) {
queue.pull();
}
System.out.println("第一次出队后元素个数为：" + queue.getElementCount());
queue.traverse();
System.out.println("队头："+queue.getFront()+" 队尾："+queue.getRear());
//第二次入队列:压入16，31
for (int i = 16; i < 32; i++) {
queue.push(i);
}
System.out.println("第二次入队后元素个数为：" + queue.getElementCount());
queue.traverse();
//第二次出队:取出16-31
for (int i = 0; i < 16; i++) {
queue.pull();
}
System.out.println("第二次出队后元素个数为：" + queue.getElementCount());
queue.traverse();
//空队列出队报错
queue.pull();
}
}
测试结果：
转载：https://blog.csdn.net/jpgzhu/article/details/105876785
查看评论