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; } @Override public void push(int x) { if(full()){ elem = Arrays.copyOf(elem,2*elem.length); } elem[usedSize++] = x; } @Override public int pop() { if(empty()){ // 抛异常 throw new EmptyException(\"栈空了\"); } int k = usedSize; usedSize--; // 相当于删除 // 如果是引用类型 // elem[usedSize] = null; return elem[k-1]; } @Override public int peek() { if(empty()){ throw new EmptyException(\"栈为空\"); } return elem[usedSize - 1]; } @Override public int size() { return usedSize; } @Override public 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<>();

面试题

用队列实现栈

用栈实现队列
出队的时候如果两个栈中都有元素，先把第二个栈中的元素出完，再把第一个栈中的元素全部倒入第二个栈中，再出第二个栈中的元素