05、数据结构与算法---栈与队列

多调试代码调试才能自己发现各种问题一、栈的理解与实现1、理解栈的存放数据形式比较像弹夹2、实现package structure; import java.util.Arrays; import java.util.Stack; public class MyStack { public int[] array1; public int count; public MyStack(){ this.array1 new int[2]; } public void push(int val){ if(isFull()){ array1 Arrays.copyOf(array1,array1.length * 2); } array1[count] val; count; } public boolean isFull(){ return count array1.length; } public boolean isEmpty(){ return count 0; } public int pop(){ if (isEmpty()){ return -1; } count--; return array1[count]; } public int peek(){ if (isEmpty()){ return -1; } return array1[count-1]; } public int size(){ return count; } public static void main(String[] args) { MyStack s new MyStack(); s.push(1); s.push(2); s.push(3); s.push(4); s.push(5); System.out.println(s.peek()); System.out.println(s.pop()); System.out.println(s.peek()); System.out.println(s.count); } }二、栈的练习题目1、验证栈序列1、主要逻辑①在栈中放入pushed里的元素同时判断栈顶元素跟j下标元素是否一样一样则弹出栈顶元素j继续往下走②如果不一样观察pushed数组中是否还有元素有则继续放无则不是可能的出栈序列此时栈有元素③注意栈s不能为空以及极端情况下j poped.length的情况2、图解3、代码演示//验证栈序列 public boolean validateStackSequences(int[] pushed, int[] popped) { StackInteger s new Stack(); int i 0; int j 0; for(;i pushed.length;i){ s.push(pushed[i]); //栈为空则下次可能调用peek失败 while(!s.empty() j popped.length s.peek() popped[j]){ s.pop(); j; } } return s.empty(); } public static void main(String[] args) { MyStack s new MyStack(); System.out.println(s.validateStackSequences(new int[]{1,2,3,4,5},new int[]{4,5,3,2,1})); } }2、有效的括号1、主要逻辑将字符串一个个分开将左括号放入栈空的直接判false不是左括号则开始peek验证是否对应对应的话就将放进去的左括号pop出去否则就是右括号没有对应的左括号最后栈中仍有元素依旧为false2、图解3、代码演示//括号匹配 public boolean isValid(String s) { StackCharacter s2 new Stack(); for (int i 0; i s.length(); i) { //接收字符串i下标的字符 char ch1 s.charAt(i); //压入左括号 if (ch1 ( || ch1 [ || ch1 {){ s2.push(ch1); }else if(s2.empty()){ return false; }else { char ch2 s2.peek(); if (ch2 ( ch1 ) || ch2 [ ch1 ] || ch2 { ch1 }) { s2.pop(); }else { return false; } } } return s2.empty(); } public static void main(String[] args) { MyStack s new MyStack(); System.out.println(s.isValid(([]))); System.out.println(s.isValid(])); System.out.println(s.isValid((]))); }3、逆波兰表达式1、主要逻辑判断是否为运算符是则压入栈不是直接弹出俩元素进行运算注意①这俩元素的次序不能乱应当为下图一右一左的顺序②进行完运算后再弹回栈最后返回栈顶元素即为最终运算结果2、图解3、代码演示//逆波兰表达式 public int evalRPN(String[] tokens) { StackInteger stack new Stack(); for (String s : tokens) { //不是运算符就压入到栈 if (!isOperation(s)) { int x Integer.parseInt(s); stack.push(x); } else { int num2 stack.pop(); int num1 stack.pop(); //结果返回到栈 switch (s) { case : stack.push(num1 num2); break; case -: stack.push(num1 - num2); break; case *: stack.push(num1 * num2); break; case /: stack.push(num1 / num2); break; } } } //返回栈顶元素 return stack.peek(); } //判断是否为运算符方法 public boolean isOperation(String s) { if (s.equals() || s.equals(-) || s.equals(*) || s.equals(/)) { return true; } return false; }4、最小栈1、主要逻辑我们需要两个栈一个普通栈一个最小栈普通栈不断push输入的元素最小栈为空时将第一个元素在两个栈各push一次将要push的元素与最小栈第一个元素比较如果前者更小则push到最小栈否则最小栈push自己栈内当前最小的元素注意pop时为了不影响次序两个栈同时pop2、图解3、代码演示package structure; import java.util.Stack; class MinStack { private StackInteger stack; private StackInteger minStack; public MinStack() { this.stack new Stack(); this.minStack new Stack(); } public void push(int x) { stack.push(x); if(minStack.empty()){ minStack.push(x); } else if(x minStack.peek()){ minStack.push(x); }else {//否则push当前的最小值 minStack.push(minStack.peek()); } } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } public static void main(String[] args) { MinStack m new MinStack(); m.push(-2); m.push(0); m.push(-3); System.out.println(m.getMin()); m.pop(); System.out.println(m.getMin()); } }三、队列的理解与实现1、理解队列像是一个管道尾进头出也就是先进去的先出2、第一种实现双向链表模式public class MyQueue { private Node head; private Node last; private int size; //结点类 private static class Node{ private int val; private Node next; private Node prev; public Node(){ } public Node(int val){ this.val val; } } // 1、入队在尾部添加元素 public void enqueue(int val) { // 调用双向链表的 addLast() Node n new Node(val); if(head null){ head n; last n; }else { last.next n; n.prev last; last last.next; } size; } // 2、出队移除并返回头部元素的值 public int dequeue() { // 调用双向链表的 removeFirst() // 空队列时抛出异常或返回-1 if (head null){ return -1; } //存储头结点的值,要不然删完head就空了 int headVal head.val; if(head.next null){ head null; last null; }else { head head.next; head.prev null; } size--; return headVal; } // 3. 查看队首只返回不删除 public int peek() { // 调用双向链表的 getFirst() 或 first.element // 空队列时返回-1 if (head null){ return -1; } return head.val; } // 4、判断是否为空 public boolean isEmpty() { // 调用双向链表的 size() 0 return size 0; } // 5、获取队列大小 public int size() { // 调用双向链表的 size() return size; } // 6、清空队列 public void clear() { // 调用双向链表的 clear() head null; last null; size 0; } public static void main(String[] args) { MyQueue m new MyQueue(); } }3、第二种实现数组实现的循环队列模式5、实现循环队列class MyCircularQueue { public int rear; public int[] array; public int front; // 构造方法初始化一个容量为 k1 的循环队列 public MyCircularQueue(int k) { //保留一个位置 this.array new int[k1]; } // 入队操作将一个元素添加到队尾 public boolean enQueue(int value) { if(isFull()){ return false; }else { array[rear] value; //循环写法实现空间利用 rear (rear1) % array.length; return true; } } // 出队操作移除队首元素 public boolean deQueue() { if (isEmpty()){ return false; } //同理 front (front1) % array.length; return true; } // 获取队首元素的值不删除 public int Front() { if (isEmpty()){ return -1; } return array[front]; } // 获取队尾元素的值不删除 public int Rear() { if (isEmpty()){ return -1; } //直接去写rear-1rear为0时可能就错了 int index (rear0)?array.length-1:rear-1; return array[index]; } // 判断队列是否为空 public boolean isEmpty() { return rear front; } // 判断队列是否已满 public boolean isFull() { if ((rear1)%array.length front){ return true; }else { return false; } } }四、队列的练习题目6、用队列实现栈package structure; import java.util.LinkedList; import java.util.Queue; //使用两个队列实现栈 public class MyQStack { private QueueInteger q1; private QueueInteger q2; public MyQStack() { this.q1 new LinkedList(); this.q2 new LinkedList(); } public void push(int x) { if(!q1.isEmpty()){ q1.offer(x); } else if(!q2.isEmpty()){ q2.offer(x); } else { q1.offer(x); } } public int pop() { if(empty()) { return -1; } if (!q1.isEmpty()) { int size q1.size(); while (size -1 ! 0) { q2.offer(q1.poll()); size--; } //取出并且删除 return q1.poll(); } else if (!q2.isEmpty()) { int size q2.size(); while (size - 1 ! 0) { q1.offer(q2.poll()); size--; } //取出并且删除 return q2.poll(); } //走不到这里的 return -1; } public int top() { if(empty()) { return -1; } if (!q1.isEmpty()) { int size q1.size(); while (size -1 ! 0) { q2.offer(q1.poll()); size--; } //取出后放到q2 int tmp q1.poll(); q2.offer(tmp); return tmp; } else if (!q2.isEmpty()) { int size q2.size(); while (size -1 ! 0) { q1.offer(q2.poll()); size--; } //取出后放到q1 int tmp q2.poll(); q1.offer(tmp); return tmp; } //走不到这里的 return -1; } public boolean empty() { return q1.isEmpty()q2.isEmpty(); } public static void main(String[] args) { MyQStack stack new MyQStack(); stack.push(1); stack.push(2); System.out.println(stack.top()); // 2 System.out.println(stack.pop()); // 2 System.out.println(stack.empty()); // false } }7、用栈实现队列这个就很简单了package structure; import java.util.Deque; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; //用栈实现队列 public class MySQueue { //建议使用Deque,官方推荐 private DequeInteger s1; private DequeInteger s2; public MySQueue() { this.s1 new LinkedList(); this.s2 new LinkedList(); } public void push(int x) { s1.push(x); } public int pop() { if (empty()){ return -1; } if(s2.isEmpty()){ // int size s1.size(); // while (size ! 0 ){ // s2.push(s1.pop()); // size--; // } while (!s1.isEmpty()){ s2.push(s1.pop()); } } return s2.pop(); } public int peek() { if(empty()){ return -1; } if(s2.isEmpty()){ // int size s1.size(); // while (size ! 0 ){ // s2.push(s1.pop()); // size--; // } //上面写法太冗杂 while (!s1.isEmpty()){ s2.push(s1.pop()); } } return s2.peek(); } public boolean empty() { return s1.isEmpty() s2.isEmpty(); } public static void main(String[] args) { MySQueue queue new MySQueue(); queue.push(1); queue.push(2); System.out.println(queue.peek()); // 1 System.out.println(queue.pop()); // 1 System.out.println(queue.empty()); // false } }本章完