栈
先进后出(LIFO, Last In First Out)
静态栈
数组 栈大小固定
动态栈
链表 栈大小不固定
public class Node {
//数据域
public int data;
//指针域，指向下一个节点
public Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
public class Stack {
public Node stackTop;//栈顶
public Node stackBottom;//栈底
public Stack(Node stackTop, Node stackBottom) {
this.stackTop = stackTop;
this.stackBottom = stackBottom;
}
public Stack() {
}
}
/**
* 进栈
*
* @param stack 栈
* @param value 要进栈的元素
*/
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("关注公众号：Java3y：" + stackTop.data);
stackTop = stackTop.next;
}
}
/**
* 判断该栈是否为空
*
* @param stack
*/
public static void isEmpty(Stack stack) {
if (stack.stackTop == stack.stackBottom) {
System.out.println("关注公众号：Java3y---->该栈为空");
} else {
System.out.println("关注公众号：Java3y---->该栈不为空");
}
}
/**
* 出栈(将栈顶的指针指向下一个节点)
* @param stack
*/
public static void popStack(Stack stack) {
// 栈不为空才能出栈
if (!isEmpty(stack)) {
//栈顶元素
Node top = stack.stackTop;
// 栈顶指针指向下一个节点
stack.stackTop = top.next;
System.out.println("关注公众号：Java3y---->出栈的元素是：" + top.data);
}
}
/**
* 清空栈
* @param stack
*/
public static void clearStack(Stack stack) {
stack.stackTop = null;
stack.stackBottom = stack.stackTop;
}
队列
先进先出(LILO, Last In Last Out)
静态队列
数组实现循环队列，节省内存资源
public class Queue {
//数组
public int [] arrays;
//指向第一个有效的元素
public int front = 0;
//指向有效数据的下一个元素(即指向无效的数据)
public int rear = 0;
}
/**
* 入队
*
* @param queue
*/
public static void enQueue(Queue queue,int value) {
// 不是满的队列才能入队
if (!isFull(queue)) {
// 将新的元素插入到队尾中
queue.arrays[queue.rear] = value;
// rear节点移动到新的无效元素位置上
queue.rear = (queue.rear + 1) % queue.arrays.length;
}
}
/**
* 出队
*
* @param queue
*/
public static void outQueue(Queue queue) {
//判断该队列是否为null
if (!isEmpty(queue)) {
//不为空才出队
int value = queue.arrays[queue.front];
System.out.println("关注公众号：Java3y--->出队的元素是：" + value);
// front指针往后面移
queue.front = (queue.front + 1) % queue.arrays.length;
}
}
/**
* 判断队列是否空，front和rear指针相等，就是空了
* @param queue
* @return
*/
public static boolean isEmpty(Queue queue) {
if (queue.rear == queue.front) {
System.out.println("关注公众号：Java3y--->此时队列空的！");
return true;
} else {
System.out.println("关注公众号：Java3y--->此时队列非空！");
return false;
}
}
/**
* 判断队列是否满了，front和rear指针紧挨着，就是满了
* @param queue
* @return
*/
public static boolean isFull(Queue queue) {
if ((queue.rear + 1) % queue.arrays.length == queue.front) {
System.out.println("关注公众号：Java3y--->此时队列满了！");
return true;
} else {
System.out.println("关注公众号：Java3y--->此时队列没满了！");
return false;
}
}
/**
* 遍历队列
* @param queue
*
*/
public static void traverseQueue(Queue queue) {
// front的位置
int i = queue.front;
while (i != queue.rear) {
System.out.println("关注公众号：Java3y--->" + queue.arrays[i]);
//移动front
i = (i + 1) % queue.arrays.length;
}
}
动态队列
链表实现