Java 栈和队列

栈

1. 先进后出的方式组织数据

模拟实现栈

1. 数组组织栈

package Stack;import java.util.Arrays;public class MyStack implements IStack{private int[] elem;private int usedSize;private static final int DEFAULT_CAPACITY = 10;public MyStack(){elem = new int[DEFAULT_CAPACITY];}public boolean full(){if(usedSize == elem.length){return true;}return false;}@Overridepublic void push(int x) {if(full()){elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize++] = x;}@Overridepublic int pop() {if(empty()){// 抛异常throw new EmptyException("栈空了");}int k = usedSize;usedSize--;// 相当于删除// 如果是引用类型// elem[usedSize] = null;return elem[k-1];}@Overridepublic int peek() {if(empty()){throw new EmptyException("栈为空");}return elem[usedSize - 1];}@Overridepublic int size() {return usedSize;}@Overridepublic boolean empty() {return usedSize == 0;}
}

2. 用链表实现栈
   可以用双向链表实现栈
   

面试题

逆波兰表达式
有效的括号
栈的压入，弹出序列
最小栈

栈，虚拟机栈，栈桢

1. 栈：是一种数据结构
2. 虚拟机栈：是JVM开辟的一块内存
3. 栈桢：是函数调用时在虚拟机中给这个方法开辟的一块内存

队列

1. 队列：组织数据的方式是先进先出，队尾入数据，队头出数据
   

2. add和offer都是入队，remove和poll都是删除元素，element和peek都是获取队头元素
   

模拟实现队列

1. 使用双向链表模拟实现队列
2. 入栈，出栈，获取栈顶元素，获取栈的大小，判空

package queuedemo;public class MyLinkQueue {static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val = val;}}public int usedSize;public ListNode head;public ListNode last;// 链表的尾插法public boolean offer(int val){ListNode node = new ListNode(val);if(head == null){head = node;last = node;}else{last.next = node;node.prev = last;last = node;}usedSize++;return true;}// 头删public int poll(){ListNode node;if(!isEmpty()){node = head;head = head.next;if(head != null){head.prev = null;}else{last = null;}}else{throw new NullIndexException("队列为空");}usedSize--;return node.val;}// 获取队头元素public int peek(){if(head == null){return -1;}return head.val;}public boolean isEmpty(){return head == null;}public int size(){return usedSize;}
}

循环队列

1. 数组可以实现队列吗？

循环队列

2. rear是可以存放数组元素的下标

3. 如何判断队列是空和满？
浪费一个空间来表示满
如果front == rear，那么就是空
如果front的下一个空间是rear，那么就是满

使用usedSize来记录是否满了

使用标记
第一次相遇标记一下，第二次相遇再标记一下，证明是满了

rear =（rear + 1）% len 表示下一个位置的下标
rear + 1 == front 表示满
front = (front + 1) % len

4. rear如何从7下标来到0下标？

循环队列

class MyCircularQueue {public int[] elem;public int front;// 队头public int rear;// 队尾public MyCircularQueue(int k) {// 我们有一个空间要浪费掉elem = new int[k + 1];}// 入队public boolean enQueue(int value) {if(isFull()){return false;}elem[rear] = value;rear = (rear + 1) % elem.length;return true;}// 出队public boolean deQueue() {if(isEmpty()){return false;}// 出队,front++front = (front + 1) % elem.length;return true;}// 获取队头元素public int Front() {if(!isEmpty()){return elem[front];}return -1;}// 获取队尾元素public int Rear() {// rear - 1// (rear + elem.length - 1) % elem.length;if(!isEmpty()){int k = (rear + elem.length - 1) % elem.length;// int k = (rear == 0) ? elem.length - 1 : rear - 1;  return elem[k];}return -1;}public boolean isEmpty() {return front == rear;}public boolean isFull() {int k = (rear + 1) % elem.length;return k == front;       }
}

双端队列

1. 可以从头进，从头出，从尾入，从尾出
2. 不仅可以当做队列和栈还可以当做链表

// 链表的双端队列
Deque<Integer> deque = new LinkedList<>();
// (顺序的)数组双端队列
Deque<Integer> deque1 = new ArrayDeque<>();

面试题

用队列实现栈

用栈实现队列