首页 > 代码库 > 队列和堆栈的实现
队列和堆栈的实现
队列的堆栈的元素移动
import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
public class stackQueue {
public static void main(String[] args) {
System.out.println("--------------------堆栈--------------------");
MyStack<Integer> stack = new MyStack<Integer>();
System.out.println("刚创建堆栈时，stack.isEmpty():" + stack.isEmpty() +",stack.size():" + stack.size());
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("push 3个元素时，栈内元素个数为" + stack.size() + ",元素转化成字符串后为：" + stack.toString());
stack.pop();
stack.pop();
System.out.println("弹出2个元素后，栈内剩余的元素个数为" + stack.size() + ",元素转化成字符串后为：" + stack.toString());
System.out.println("--------------------队列开始--------------------");
MyQueue<Integer> queue = new MyQueue<Integer>(5);
System.out.println("刚创建堆栈时，queue.isEmpty():" + queue.isEmpty() +",queue.isFull():"+queue.isFull()+ ",queue.size():" + queue.size());
for (int i = 0; i < 3; i++) {
queue.add(i);
}
System.out.println("添加3个元素：");
System.out.println("队列头元素为："+queue.getHead()+",队尾元素为："+queue.getTail()+"，队列长度为："+queue.size());
System.out.println(queue);
System.out.println("去掉2个元素：");//去掉元素，元素只是不能访问到了，被去掉的元素可以被添加的覆盖
queue.remove();
queue.remove();
System.out.println("队列头元素为："+queue.getHead()+",队尾元素为："+queue.getTail()+"，队列长度为："+queue.size());
queue.add(7);
System.out.println(queue);
for (int i = 3; i < 6; i++) {
queue.add(i);
}
System.out.println("添加4个元素：");//此时尾指又要从开始处添加元素，remove掉的被覆盖
System.out.println("队列头元素为："+queue.getHead()+",队尾元素为："+queue.getTail()+"，队列长度为："+queue.size());
System.out.println(queue);
System.out.println("去掉4个元素：");//此时尾指又要从开始处添加元素
queue.remove();queue.remove();queue.remove();queue.remove();
System.out.println("queue.getHead():"+queue.getHead()+",queue.getTail()："+queue.getTail()+"，queue.size()："+queue.size());
System.out.println(queue);
}
}
class MyStack<E> {
private ArrayList<E> list;
public MyStack() {
list = new ArrayList<E>();
}
/**
* 栈是否为空
*
* @return
*/
public boolean isEmpty() {
return list.size() == 0;
}
/**
* 栈内容长度
*
* @return
*/
public int size() {
return list.size();
}
/**
* 添加元素
*
* @param e
*/
public void push(E e) {
list.add(e);
}
/**
* 弹出元素
*
* @return
*/
public E pop() {
if (list.size() > 0) {
return list.remove(list.size() - 1);
}
return null;
}
@Override
public String toString() {
return Arrays.toString(list.toArray());
}
}
class MyQueue<E> {
private int maxSize;// 队列容量
private E queue[];// 队列
private int head;// 头指针
private int tail;// 尾指针
private int nItems;// 元素个数
@SuppressWarnings("unchecked")
public MyQueue(int maxSize) {
this.maxSize = maxSize;
this.queue = (E[]) new Object[maxSize];
this.head = 0;// 移除元素一般从下标0开始，头指针指向待移除的元素（也就是移除元素的下标）
this.tail = -1;// 一般设为-1，当添加元素后，尾指针数值为当前已经添加的元素的下标位置
this.nItems = 0;
}
/**
* 队列是否为空
*
* @return
*/
public boolean isEmpty() {
return nItems == 0;
}
/**
* 队列是否已满
*
* @return
*/
public boolean isFull() {
return nItems == queue.length;
}
/**
* 添加从队尾开始
*
* @param e
*/
public void add(E e) {
if (isFull()) {
throw new RuntimeException("队列已满");
}
// 当队尾指针已经到达数组的末尾，但数组却未填满（数组前面有空缺），此时又从起始位置添加元素
if (tail == maxSize - 1) {
tail = -1;
}
queue[++tail] = e;
nItems++;
}
/**
* 删除从对头开始
*
* @return
*/
public E remove() {
if (isEmpty()) {
throw new RuntimeException("队列已空");
}
// 当对头指针到达数组末尾，但数组个数却不为空（说明数组前面还有元素），此时又从起始位置删除元素
if (head == maxSize) {
head = 0;
}
nItems--;
return queue[head++];
}
/**
* 获取对头元素
*
* @return
*/
public E getHead() {
return queue[head];
}
/**
* 获取队尾元素
*
* @return
*/
public E getTail() {
return queue[tail];
}
/**
* 队列元素个数
*
* @return
*/
public int size() {
return nItems;
}
@Override
public String toString() {
return Arrays.toString(queue);
}
}
运行结果：
队列和堆栈的实现