数据结构-栈、队列

栈

先进后出(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;

}

}

动态队列

链表实现