devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java数据结构与算法第五课——栈和队列_栈与队列java

作者：我家自动化 | 2024-05-30 22:55:19

赞

踩

栈与队列java

目录

一：栈

1.栈的定义

2.栈的模拟实现

3.栈的使用

二：队列

1.队列的定义

 2.队列的模拟实现

 3.循环队列

3.1循环队列的引入

3.2循环队列的实现

三：面试题

3.1用队列实现栈

3.2用栈实现队列

3.3实现最小栈

一：栈

1.栈的定义

        栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

  • 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
  • 出栈：栈的删除操作叫做出栈。出数据在栈顶。

2.栈的模拟实现

        从上图中可以看到，Stack继承了Vector。Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。值得注意的是，现如今Vector几乎已经被淘汰，所以我们只介绍Stack。

        我们先简单看一下java中封装好的栈Stack。它的操作很简单，我们可以根据下表所示的功能，进行栈的模拟实现。

         我们只需用一个数组存储栈中的所有元素，为了使栈可以存放任意类型的数据元素，我们在此使用泛型。栈的模拟实现比较简单，在此仅将代码展示如下：

MyStack.java

  1. package MyStack;
  2.  
  3.  
  4. import java.util.Arrays;
  5.  
  6. public class MyStack<E> {
  7.  
  8.     public E[] elem;
  9.     public int usedSize;
  10.  
  11.     public MyStack() {
  12.         this.elem = (E[])new Object[2];
  13.     }
  14.  
  15.     /**
  16.      * 入栈
  17.      * @param val
  18.      */
  19.     public void push(E val) {
  20.         if(isFull()){
  21.             this.elem = Arrays.copyOf(this.elem,2*elem.length);
  22.         }
  23.         elem[usedSize] = val;
  24.         usedSize++;
  25.  
  26.     }
  27.  
  28.     /**
  29.      * 判断当前栈是否为满
  30.      * @return
  31.      */
  32.     public boolean isFull() {
  33.         return usedSize == elem.length;
  34.     }
  35.  
  36.     /**
  37.      * 出栈
  38.      * @return
  39.      */
  40.     public E pop() {
  41.         if(empty()){
  42.             System.out.println("当前栈已空！");
  43.             return null;
  44.         } else {
  45.             E tmp = elem[usedSize-1];
  46.             elem[usedSize-1] = null;
  47.             usedSize--;
  48.             return tmp;
  49.         }
  50.     }
  51.  
  52.     public boolean empty() {
  53.         return usedSize==0;
  54.     }
  55.  
  56.     /**
  57.      * 获取栈顶元素 不删除！
  58.      * @return
  59.      */
  60.     public E peek() {
  61.         if(empty()){
  62.             System.out.println("当前栈已空！");
  63.             return null;
  64.         } else {
  65.             E tmp = elem[usedSize-1];
  66.             return tmp;
  67.         }
  68.     }
  69.  
  70.     /**
  71.      * 获取大小
  72.      * @return
  73.      */
  74.     public int getUsedSize() {
  75.         return usedSize;
  76.     }
  77.  
  78. }

Test.java

  1. package MyStack;
  2.  
  3. public class Test {
  4.     public static void main(String[] args) {
  5.         MyStack myStack = new MyStack();
  6.         myStack.push(1);
  7.         myStack.push(2);
  8.         myStack.push(3);
  9.         myStack.push(4);
  10.         myStack.push(5);
  11.         int tmp = (int) myStack.pop();
  12.         System.out.println(tmp);
  13.         int tmp2 = (int)myStack.pop();
  14.         System.out.println(tmp2);
  15.         int tmp3 = (int)myStack.peek();
  16.         System.out.println(tmp3);
  17.         int tmp4 = (int)myStack.pop();
  18.         System.out.println(tmp4);
  19.     }
  20. }

3.栈的使用

        掌握了栈的模拟实现，栈的使用自然不在话下了。示例代码如下：

  1. public static void main(String[] args) {
  2.         Stack myStack = new Stack();
  3.         myStack.push(1);
  4.         myStack.push(2);
  5.         myStack.push(3);
  6.         myStack.push(4);
  7.         myStack.push(5);
  8.         int tmp = (int) myStack.pop();
  9.         System.out.println(tmp);
  10.         int tmp2 = (int)myStack.pop();
  11.         System.out.println(tmp2);
  12.         int tmp3 = (int)myStack.peek();
  13.         System.out.println(tmp3);
  14.         int tmp4 = (int)myStack.pop();
  15.         System.out.println(tmp4);
  16.  
  17.         int size = myStack.size();
  18.         System.out.println("栈中元素个数为"+size);
  19.  
  20.         boolean isempty = myStack.empty();
  21.         if(isempty == false){
  22.             System.out.println("当前栈不为空！");
  23.         }else{
  24.             System.out.println("当前栈为空！");
  25.         }
  26.     }

运行结果如下：

二：队列

1.队列的定义

        队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，具有先进先出FIFO(FirstIn First Out)的特点。

  1. 入队列：进行插入操作的一端称为队尾（Tail/Rear）
  2. 出队列：进行删除操作的一端称为队头（Head/Front）

 2.队列的模拟实现

        在Java中，Queue是个接口，底层是通过链表实现的。 

        我们先简单看一下Java中封装好的队列Queue。它的操作很简单，我们可以根据下表所示的功能，进行队列的模拟实现。需要注意的是，队列底层是通过链表实现的。

MyLInkedList.java 

  1. package MyQueue;
  2.  
  3. import java.util.Queue;
  4.  
  5. public class MyLinkedList {
  6.  
  7.     class Node {
  8.         public int val;
  9.         public Node next;
  10.         public Node(int val) {
  11.             this.val = val;
  12.         }
  13.     }
  14.  
  15.     public int usedSize;
  16.     public Node head;
  17.     public Node last;
  18.  
  19.     /**
  20.      * 入队
  21.      * @param val
  22.      */
  23.     public void offer(int val) {
  24.         Node node = new Node(val);
  25.         if(head == null){
  26.             head = node;
  27.             last = node;
  28.         } else {
  29.             last.next = node;
  30.             last = node;
  31.         }
  32.         usedSize++;
  33.  
  34.     }
  35.  
  36.     /**
  37.      * 出队
  38.      * @return
  39.      */
  40.     public int poll() {
  41.         if(isEmpty()){
  42.             throw new RuntimeException("当前队列为空！");
  43.         }else{
  44.             int ret = head.val;
  45.             head = head.next;
  46.             usedSize--;
  47.             return ret;
  48.         }
  49.     }
  50.     /**
  51.      * 出队 但是不删除
  52.      * @return
  53.      */
  54.     public int peek() {
  55.         if(isEmpty()){
  56.             throw new RuntimeException("当前队列为空！");
  57.         }else{
  58.             int ret = head.val;
  59.             return ret;
  60.         }
  61.  
  62.     }
  63.     public int size() {
  64.         return usedSize;
  65.     }
  66.     public boolean isEmpty() {
  67.         return usedSize == 0;
  68.     }
  69. }

Test.java

  1. package MyQueue;
  2.  
  3. public class Test {
  4.     public static void main(String[] args) {
  5.         MyLinkedList myLinkedList = new MyLinkedList();
  6.         myLinkedList.offer(12);
  7.         myLinkedList.offer(23);
  8.         myLinkedList.offer(34);
  9.         myLinkedList.offer(45);
  10.         myLinkedList.offer(56);
  11.         System.out.println(myLinkedList.poll());
  12.         System.out.println(myLinkedList.poll());
  13.         System.out.println(myLinkedList.peek());
  14.         System.out.println("当前队列的长度为："+myLinkedList.size());
  15.     }
  16.  
  17. }

 运行结果如下：

 3.循环队列

3.1循环队列的引入

        现在我们来思考一个问题。既然栈的实现使用了数组，那为什么队列的实现没有使用数组，而是使用了链表呢？如下图所示为一个数组，假设我们用它来实现队列，那么，你是否能知道队头和队尾分别在哪呢？

        显然，随着队列中元素的入队和出队，队头和队尾也在不断发生变化。

         显然，如果使用数组实现队列，会造成极大的空间浪费。那么如何才能解决这一问题呢？答案是：把这个数组“卷”起来；当队尾指针来到数组最末端时，不让其指向null，而是指向数组中的第一个元素。这就是我们接下来要谈的“循环队列”。

                最终，队列就变成了这个样子：

         一开始，head == last，说明该循环队列为空。

        各就位，现在开始入队：

         Full or not full, this is a question。当循环队列中元素已满时，head == null也成立，那么当这一条件成立时，如何判断当前队列是满还是空呢？以下给出三种方法：

1.通过添加usedSize属性记录；

2.使用标记；

3.保留一个位置。

        前两种方法，我们容易理解。添加usedSize属性，判断其等于0还是与数组大小相等即可；使用标记，通过判断last和head的相遇时机，调整标记状态即可。最后一种方法的意思是，当数组中仅有一个位置为空时，我们就认为该数组已满。图解如下：

         这里还有一点小问题，那就是在判断队列为满时，last+1=7+1=8，而此时head=0，这二者并不相等。为使数组下标也能循环起来，需要做出这样的调整：

index = (index + 1) % array.length。     

3.2循环队列的实现

保留一个位置表示满时：

  1. class MyCircularQueue {
  2.     private int[] elem;
  3.     private int front;//表示队头下标
  4.     private int rear;//表示队尾下标
  5.  
  6.     public MyCircularQueue(int k) {
  7.         elem = new int[k];
  8.     }
  9.  
  10.     //入队
  11.     public boolean enQueue(int value) {
  12.         if (!isFull()) {
  13.             elem[rear] = value;
  14.             rear = (rear + 1) % (elem.length);
  15.             return true;
  16.         }
  17.         return false;
  18.     }
  19.  
  20.     //出队
  21.     public boolean deQueue() {
  22.         if (!isEmpty()) {
  23.             front = (front + 1) % elem.length;
  24.             return true;
  25.         }
  26.         return false;
  27.  
  28.     }
  29.  
  30.     //获取队头元素
  31.     public int Front() {
  32.         if(isEmpty()){
  33.             return -1;
  34.         }
  35.         return elem[front];
  36.  
  37.     }
  38.  
  39.     //获取队尾元素
  40.     public int Rear() {
  41.         if(isEmpty()){
  42.             return -1;
  43.         }
  44.         int index =(rear ==0 ) ? elem.length-1 : rear-1;
  45.         return elem[index];
  46.     }
  47.  
  48.     public boolean isEmpty() {
  49.         return rear == front;
  50.     }
  51.  
  52.     /*
  53.     浪费一个空间表示满
  54.      */
  55.     public boolean isFull() {
  56.         return (rear + 1) % elem.length == front;
  57.     }
  58. }

用usedSize做标记时：

  1. class MyCircularQueue {
  2.     private int[] elem;
  3.     private int front;//表示队头下标
  4.     private int rear;//表示队尾下标
  5.     private int usedSize;
  6.  
  7.     public MyCircularQueue(int k) {
  8.         elem = new int[k];
  9.         usedSize = 0;
  10.     }
  11.  
  12.     //入队
  13.     public boolean enQueue(int value) {
  14.         if (!isFull()) {
  15.             elem[rear] = value;
  16.             rear = (rear + 1) % (elem.length);
  17.             usedSize++;
  18.             return true;
  19.         }
  20.         return false;
  21.     }
  22.  
  23.     //出队
  24.     public boolean deQueue() {
  25.         if (!isEmpty()) {
  26.             front = (front + 1) % elem.length;
  27.             usedSize--;
  28.             return true;
  29.         }
  30.         return false;
  31.  
  32.     }
  33.  
  34.     //获取队头元素
  35.     public int Front() {
  36.         if(isEmpty()){
  37.             return -1;
  38.         }
  39.         return elem[front];
  40.  
  41.     }
  42.  
  43.     //获取队尾元素
  44.     public int Rear() {
  45.         if(isEmpty()){
  46.             return -1;
  47.         }
  48.         int index =(rear ==0 ) ? elem.length-1 : rear-1;
  49.         return elem[index];
  50.     }
  51.  
  52.     public boolean isEmpty() {
  53.         return usedSize == 0;
  54.     }
  55.  
  56.     public boolean isFull() {
  57.         return usedSize == elem.length;
  58.     }
  59. }

三：面试题

3.1用队列实现栈

链接：

力扣https://leetcode.cn/problems/implement-stack-using-queues/

1.题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

2.解题

        一个队列，只能实现先进先出，没法实现栈，所以至少需要两个队列。在入队时，永远入到不为空的队列；在出队时，从有元素的队列弹出size-1个元素，放到空的那个队列中，然后再将最后一个元素出队。图解如下：

 具体代码如下：

  1. class MyStack {
  2.         private Queue<Integer> qu1;
  3.         private Queue<Integer> qu2;
  4.  
  5.     public MyStack() {
  6.         qu1 = new LinkedList<>();
  7.         qu2 = new LinkedList<>();
  8.     }
  9.     
  10.     //入到不为空队列中
  11.     //都为空，入到qu1
  12.     public void push(int x) {
  13.             if(!qu1.isEmpty()){
  14.                 qu1.offer(x);
  15.             }else if(!qu2.isEmpty()){
  16.                 qu2.offer(x);
  17.             }else{
  18.                 qu1.offer(x);
  19.             }
  20.     }
  21.     
  22.     public int pop() {
  23.         if(empty()){
  24.             return -1;
  25.         }
  26.         if(!qu1.isEmpty()){
  27.             int size = qu1.size();
  28.             for(int i = 0;i<size-1;i++){
  29.                 qu2.offer(qu1.poll());
  30.             }
  31.             return qu1.poll();
  32.         }else{
  33.             int size = qu2.size();
  34.             for(int i = 0;i<size-1;i++){
  35.                 qu1.offer(qu2.poll());
  36.             }
  37.             return qu2.poll();            
  38.         }
  39.     }
  40.     
  41.     public int top() {
  42.              if(empty()){
  43.             return -1;
  44.         }
  45.         int tmp = -1;
  46.         if(!qu1.isEmpty()){
  47.             int size = qu1.size();   
  48.             for(int i = 0;i<size;i++){
  49.                  tmp = qu1.poll();
  50.                  qu2.offer(tmp);
  51.             }
  52.             return tmp;
  53.         }else{
  54.         int size = qu2.size();
  55.         for(int i = 0;i<size;i++){
  56.             tmp = qu2.poll();
  57.             qu1.offer(tmp);
  58.         }
  59.         return tmp;            
  60.         }
  61.     }
  62.     
  63.     public boolean empty() {
  64.        if(qu1.isEmpty() &&qu2.isEmpty()){
  65.            return true;
  66.        }
  67.        return false;
  68.     }
  69. }
  70.  
  71. /**
  72.  * Your MyStack object will be instantiated and called as such:
  73.  * MyStack obj = new MyStack();
  74.  * obj.push(x);
  75.  * int param_2 = obj.pop();
  76.  * int param_3 = obj.top();
  77.  * boolean param_4 = obj.empty();
  78.  */

        要解决这个问题，一定要熟悉队列的操作方法。

3.2用栈实现队列

链接：

力扣https://leetcode.cn/problems/implement-queue-using-stacks/

1.题目：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

2.解题

        用两个栈实现队列，基本思路是：入的时候，都入到一个栈中；出的时候，都出第二个栈中的元素。如果第二个栈中没有元素了，就把第一个栈中的元素全部倒过来。图解如下：

 具体代码如下：

  1. class MyQueue {
  2.         Stack<Integer> s1; 
  3.         Stack<Integer> s2; 
  4.     public MyQueue() {
  5.         s1= new Stack<>();
  6.         s2= new Stack<>();
  7.     }
  8.     
  9.     public void push(int x) {
  10.         s1.push(x);
  11.     }
  12.     
  13.     public int pop() {
  14.         if(empty()){
  15.             return -1;
  16.         }
  17.  
  18.         if(s2.isEmpty()){
  19.             while(!s1.empty()){
  20.             s2.push(s1.pop());                
  21.             }
  22.         }
  23.         return s2.pop();
  24.     }
  25.     
  26.     public int peek() {
  27.         if(empty()){
  28.             return -1;
  29.         }
  30.  
  31.         if(s2.isEmpty()){
  32.             while(!s1.empty()){
  33.             s2.push(s1.pop());                
  34.             }
  35.         }
  36.         return s2.peek();
  37.     }
  38.     
  39.     public boolean empty() {
  40.         return s1.empty()&&s2.empty();
  41.     }
  42. }
  43.  
  44. /**
  45.  * Your MyQueue object will be instantiated and called as such:
  46.  * MyQueue obj = new MyQueue();
  47.  * obj.push(x);
  48.  * int param_2 = obj.pop();
  49.  * int param_3 = obj.peek();
  50.  * boolean param_4 = obj.empty();
  51.  */

3.3实现最小栈

链接：

力扣https://leetcode.cn/problems/min-stack/

1.题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

2.解题：

        首先明确什么是最小栈。要求设计一个栈，除提供最基础的push，pop ，top 操作外，还能在O(1)的时间复杂度内检索到栈中的最小元素。

        思路是：使用两个栈，其中一个s为当前栈，另一个minStack栈，用于保存当前栈中的最小元素。有出栈和入栈两种情况：

         当入栈时，比较该元素与minStack栈顶元素的大小，如果该元素小于或等于minStack的栈顶元素，该元素入minStack栈中。这一操作可以保证minStack栈顶元素始终为s栈中最小的元素。

         当有元素出栈时，也要比较该元素与minStack栈顶元素的大小，如果二者相等，则minStack的栈顶元素也要出栈，否则不对minStack进行操作。

具体代码如下：

  1. class MinStack {
  2.  
  3.  
  4.     private Stack<Integer> s1;
  5.     private Stack<Integer> minStack;
  6.  
  7.     public MinStack() {
  8.         s1 = new Stack<>();
  9.         minStack = new Stack<>();
  10.     }
  11.     
  12.     /**
  13.     s1这个栈 一定要放元素的
  14.      */
  15.     public void push(int val) {
  16.         s1.push(val);
  17.         if(minStack.empty()) {
  18.             minStack.push(val);
  19.         }else{
  20.             int x = minStack.peek();
  21.             //这里能不能取等号？？？
  22.             if(val <= x) {
  23.                 minStack.push(val);
  24.             }
  25.         }
  26.     }
  27.     
  28.     public void pop() {
  29.         int x = s1.pop();
  30.         int x2 = minStack.peek();
  31.         if(x == x2) {
  32.             minStack.pop();
  33.         }
  34.     }
  35.     
  36.     //获取当前的栈顶元素不删除 ，不是最小栈的栈顶元素
  37.     public int top() {
  38.         return s1.peek();
  39.     }
  40.     
  41.     public int getMin() {
  42.         return minStack.peek();
  43.     }
  44. }
  45.  
  46.  
  47. /**
  48.  * Your MinStack object will be instantiated and called as such:
  49.  * MinStack obj = new MinStack();
  50.  * obj.push(val);
  51.  * obj.pop();
  52.  * int param_3 = obj.top();
  53.  * int param_4 = obj.getMin();
  54.  */

       本课主要讲解了栈和队列，了解了栈和队列的模拟实现后，关键是灵活使用java集合类中封装好的栈和队列，尤其注意出栈和入栈使用的是push()和pop()操作，出队和入队使用的是offer()和pull()操作；在栈中，判空使用的是empty()方法；在队列中，判空使用的是isEmpty()方法。而获取栈或队列的长度以及获取栈顶元素(队头元素)，其方法名是一致的，为size()和peek()。

        最后，通过用两个栈实现队列，用两个队列实现栈，进一步加深了我们对栈和队列的理解。

        本课内容结束！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/649005
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号