devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【Java数据结构】栈和队列（概念+练题）_java实现栈和队列数据结构练习题

作者：小丑西瓜9 | 2024-06-03 18:04:41

赞

踩

java实现栈和队列数据结构练习题

目录

1. 实现栈（数组）

MyStack.java

2. 实现队列（链式）

MyQueueLinked.java

3. 实现循环队列

MyCircularQueue.java

4. LeetCode习题

4.1 括号匹配问题

4.2 用队列实现栈

4.3 用栈实现队列

4.4 实现一个最小栈

  • 栈：先进后出
  • 队列：先进先出

1. 实现栈（数组）

MyStack.java

  1. public class MyStack {
  2.     public int[] elem;
  3.     public int usedSize;
  4.  
  5.     public MyStack() {
  6.         this.elem = new int[10];
  7.     }
  8.  
  9.     //判断是否栈满
  10.     public boolean isFull() {
  11.         if (this.usedSize == this.elem.length) {
  12.             return true;
  13.         }
  14.         return false;
  15.     }
  16.     //push
  17.     public void push(int item) {
  18.         if(isFull()) {
  19.             //扩容
  20.             this.elem = Arrays.copyOf(this.elem,2*2*this.elem.length);
  21.         }
  22.         this.elem[this.usedSize] = item;
  23.         this.usedSize++;
  24.     }
  25.  
  26.     //pop
  27.     public int pop() {
  28.         if(empty()) {
  29.             throw new RuntimeException("栈空了！");
  30.         }
  31.         int val = this.elem[this.usedSize-1];
  32.         this.usedSize--;
  33.         return val;
  34.     }
  35.  
  36.     //peek
  37.     public int peek() {
  38.         if(empty()) {
  39.             throw new RuntimeException("栈空了！");
  40.         }
  41.         return this.elem[this.usedSize-1];
  42.     }
  43.  
  44.     //判断为空
  45.     public boolean empty() {
  46.         if(this.usedSize == 0) return true;
  47.         return false;
  48.     }
  49. }

2. 实现队列（链式）

MyQueueLinked.java

  1. class Node {
  2.     public int data;
  3.     public Node next;
  4.  
  5.     public Node(int data) {
  6.         this.data = data;
  7.     }
  8. }
  9. public class MyQueueLinked {
  10.     private Node front;
  11.     private Node rear;
  12.     private int usedSize = 0;
  13.  
  14.     //入队列
  15.     public void offer(int val) {
  16.         Node node = new Node(val);
  17.         if (this.front == null) {
  18.             this.front = node;
  19.             this.rear = node;
  20.         } else {
  21.             this.rear.next = node;
  22.             this.rear = node;
  23.         }
  24.         this.usedSize++;
  25.     }
  26.     //出队头元素
  27.     public int poll() {
  28.         if(isEmpty()) {
  29.             throw new RuntimeException("队列为空！");
  30.         }
  31.         int val = this.front.data;
  32.         if(this.front.next == null) {
  33.             //只有一个结点
  34.             this.front = null;
  35.             this.rear = null;
  36.         } else {
  37.             this.front = this.front.next;
  38.         }
  39.         this.usedSize--;
  40.         return val;
  41.     }
  42.  
  43.     //得到队头元素
  44.     public int peek() {
  45.         if(isEmpty()) {
  46.             throw new RuntimeException("队列为空！");
  47.         }
  48.         return this.front.data;
  49.     }
  50.     public boolean isEmpty() {
  51.         return this.usedSize == 0;
  52.     }
  53.     public int size() {
  54.         return this.usedSize;
  55.     }
  56. }

3. 实现循环队列

MyCircularQueue.java

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

4. LeetCode习题

4.1 括号匹配问题

20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)

思路：先判断是否为空、s.length()是否为0或奇数。

然后变量字符串，如果为左括号，则push进栈，如果为右括号，则与pop栈中的对比。

  1. class Solution {
  2.     public boolean isValid(String s) {
  3.         if(s == null || s.length() == 0) return true;
  4.         Stack<Character> stack = new Stack<>();
  5.         for (int i = 0; i < s.length(); i++) {
  6.             char ch = s.charAt(i);
  7.             if(ch == '{' ||ch == '(' ||ch == '[' ) {
  8.                 stack.push(ch);
  9.             } else {
  10.                 if (stack.empty()) return false;
  11.                 //栈不为空
  12.                 char tmp = stack.peek();
  13.                 if(ch == '}' && tmp == '{' ||ch == ')' && tmp == '(' ||ch == ']' && tmp == '[') {
  14.                     stack.pop();
  15.                 } else {
  16.                     return false;
  17.                 }
  18.             }
  19.         } 
  20.         if (!stack.empty()) return false;
  21.         return true;
  22.     }
  23. }

4.2 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)

  1. class MyStack {
  2.  
  3.     private Queue<Integer> qu1 = new LinkedList<>();
  4.     private Queue<Integer> qu2 = new LinkedList<>();
  5.     public MyStack() {
  6.         
  7.     }
  8.     
  9.     //入栈
  10.     public void push(int x) {
  11.         if(!qu1.isEmpty()) {
  12.             qu1.offer(x);
  13.         } else if (!qu2.isEmpty()){
  14.             qu2.offer(x);
  15.         } else {
  16.             qu1.offer(x);
  17.         }
  18.     }
  19.     //出栈
  20.     public int pop() {
  21.         if(empty()) return -1;
  22.         int e = -1;
  23.         if (!qu1.isEmpty()) {
  24.             int size = qu1.size();
  25.             for (int i = 0; i < size -1; i++) {
  26.                 e = qu1.poll();
  27.                 qu2.offer(e);
  28.             }
  29.             e = qu1.poll();
  30.         } else {
  31.             int size = qu2.size();
  32.             for (int i = 0; i < size -1; i++) {
  33.                 e = qu2.poll();
  34.                 qu1.offer(e);
  35.             }
  36.             e = qu2.poll();
  37.         }
  38.         return e;
  39.     }
  40.     //得到栈顶元素，不删除
  41.     public int top() {
  42.         if(empty()) return -1;
  43.         int e = -1;
  44.         if (!qu1.isEmpty()) {
  45.             int size = qu1.size();
  46.             for (int i = 0; i < size; i++) {
  47.                 e = qu1.poll();
  48.                 qu2.offer(e);
  49.             }
  50.         } else {
  51.             int size = qu2.size();
  52.             for (int i = 0; i < size; i++) {
  53.                 e = qu2.poll();
  54.                 qu1.offer(e);
  55.             }
  56.         }
  57.         return e;
  58.     }
  59.     //是否为空
  60.     public boolean empty() {
  61.         return qu1.isEmpty() && qu2.isEmpty();
  62.     }
  63. }

4.3 用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)

一个栈用来入，另一个栈用来出

  1. class MyQueue {
  2.     private Stack<Integer> s1 = new Stack<>();
  3.     private Stack<Integer> s2 = new Stack<>();
  4.  
  5.     public MyQueue() {
  6.  
  7.     }
  8.     
  9.     public void push(int x) {
  10.         s1.push(x);   //指定push到第一个栈
  11.     }
  12.     
  13.     public int pop() {
  14.         if (empty()) return -1;
  15.         if (s2.empty()) {
  16.             while (!s1.empty()) {
  17.                 s2.push(s1.pop());
  18.            }
  19.         }
  20.         return s2.pop();
  21.     }
  22.     
  23.     public int peek() {
  24.         if (empty()) return -1;
  25.         if (s2.empty()) {
  26.             while (!s1.empty()) {
  27.                 s2.push(s1.pop());
  28.            }
  29.         }
  30.         return s2.peek();
  31.     }
  32.     
  33.     public boolean empty() {
  34.         return s1.empty() && s2.empty();
  35.     }
  36. }

4.4 实现一个最小栈

155. 最小栈 - 力扣（LeetCode） (leetcode-cn.com)

两个栈，一个正常栈，另一个栈存储最小值

  1. class MinStack {
  2.     private Stack<Integer> s1 = new Stack<>();
  3.     private Stack<Integer> s2 = new Stack<>();
  4.     public MinStack() {
  5.  
  6.     }
  7.     
  8.     public void push(int val) {
  9.         s1.push(val);
  10.         if (s2.empty() || val <= s2.peek()) {
  11.             s2.push(val);
  12.         }
  13.     }
  14.     
  15.     public void pop() {
  16.         int val = s1.pop();
  17.         if(!s2.empty() && s2.peek()==val) {
  18.             s2.pop();
  19.         }
  20.     }
  21.     
  22.     public int top() {
  23.         if(!s1.empty()) {
  24.             return s1.peek();
  25.         }
  26.         return 0;
  27.     }
  28.     
  29.     public int getMin() {
  30.         if(!s2.empty()) {
  31.             return s2.peek();
  32.         }
  33.         return 0;
  34.     }
  35. }

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

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

  

闽ICP备14008679号