文章目录
栈Java实现栈节点定义栈定义进栈操作遍历栈出栈操作
队列Java实现队列队列定义
区别于数组和链表这种线性存储结构的基础，栈和队列都是线性存储结构的应用。
栈
栈可以看成一个放光盘的箱子，箱口与略大与光盘。然后
往箱子里面放东西叫做入栈往箱子里面取东西叫做出栈箱子的底部叫做栈底箱子的顶部叫做栈顶先进后出，后进先出
Java实现栈
使用数组实现的叫静态栈使用链表实现的叫动态栈
节点定义
pulic
class Node{
protected int data
;
projected Node next
;
public Node(int newdata
){
this.data
= data
;
this.next
= null
;
}
public Node(){
}
}
栈定义
public class Stack {
public Node stackTop
;
public Node stackBottom
;
public Stack(Node stackTop
, Node stackBottom
) {
this.stackTop
= stackTop
;
this.stackBottom
= stackBottom
;
}
public Stack() {
}
}
进栈操作
将原本栈顶指向的节点交由新节点来指向，栈顶指向新加入的节点
public static void pushStack(Stack stack
, int value
) {
Node newNode
= new Node(value
);
newNode
.next
= stack
.stackTop
;
stack
.stackTop
= newNode
;
}
遍历栈
只要栈顶元素的指针不指向栈底，那么就一直输出遍历结果
/**
* 遍历栈
* @param stack
*/
public static void traverse(Stack stack) {
Node stackTop = stack.stackTop;
//栈顶元素的指针不指向栈底，那么就一直输出遍历结果
while (stackTop != stack.stackBottom) {
System.out.println("栈数据：" + stackTop.data);
stackTop = stackTop.next;
}
}
出栈操作
在出栈之前看看该栈是否为空，不为空才出栈 将栈顶的元素的指针(指向下一个节点)赋值给栈顶指针(完成出栈)
/**
* 出栈(将栈顶的指针指向下一个节点)
* @param stack
*/
public static void popStack(Stack stack) {
// 栈不为空才能出栈
if (stack.stackTop != stack.stackBottom) {
//栈顶元素
Node top = stack.stackTop;
// 栈顶指针指向下一个节点
stack.stackTop = top.next;
System.out.println("栈数据：" + top.data);
}
}
队列
区别于栈，队列 先进先出，后进后出使用数组实现的叫静态队列使用链表实现的叫动态队列
Java实现队列
队列定义
public class Queue{
private Node front
;
private Node rear
;
private int size
;
public Queue(Node front
, Node rear
){
this.front
= front
;
this.rear
= rear
;
}
public Queue
{
}
}
//数组静态实现
public class Queue<E> {
private Object[] data=null;
private int maxSize; //队列容量
private int front; //队列头，允许删除
private int rear; //队列尾，允许插入
//构造函数
public Queue(){
this(5);
}
public Queue(int initialSize){
if(initialSize >=0){
this.maxSize = initialSize;
data = new Object[initialSize];
front = rear =0;
}else{
throw new RuntimeException("初始化大小不能小于0：" + initialSize);
}
}
//判空
public boolean empty(){
return rear==front?true:false;
}
//入队
public boolean add(E e){
if(rear== maxSize){
throw new RuntimeException("队列已满，无法插入新的元素！");
}else{
data[rear++]=e;
return true;
}
}
//出队
public E poll(){
if(empty()){
throw new RuntimeException("空队列异常！");
}else{
E value = (E) data[front]; //保留队列的front端的元素的值
data[front++] = null; //释放队列的front端的元素
return value;
}
}
//队列长度
public int length(){
return rear-front;
}
/**
* 遍历队列
* @param queue
*
*/
public static void traverseQueue(Queue queue) {
// front的位置
int i = queue.front;
while (i != queue.rear) {
System.out.println("队列值：" + queue.data[i]);
//移动front
i = (i + 1) % queue.data.length;
}
}
}
