• [java]快速入门栈和队列,手撕相关面试题

    专栏简介 :java语法及数据结构

    题目来源:leetcode,牛客,剑指offer

    创作目标:从java语法角度实现底层相关数据结构,达到手撕各类题目的水平.

    希望在提升自己的同时,帮助他人,与大家一起共同进步,互相成长.

    学历代表过去,能力代表现在,学习能力代表未来!

    目录

    前言

    一.栈的定义与实现

    1)栈的定义:

     2)栈常见操作方法:

     3)栈的实现:

    二.栈相关题目

    1)逆波兰数

    2)不可能的入栈方式

    3)有效括号

    4)最小栈

    三.队列的实现

    1)单链表实现队列

    2)循环队列

    四.队列相关题目

    1)用栈实现队列 

    2)用队列实现栈

    总结

    前言

            Hello!大家好!我是Node_Hao,今天给大家带来的是栈和队列的底层实现及其构造方法,旨在熟练掌握栈和队列的使用以后,可以手撕各类栈相关的题目.希望我的文章能对你有所帮助与启发!

    一.栈的定义与实现

    1)栈的定义:

          栈是一种数据结构特点是"先进后出",基于这一特点栈不管是push()(压入元素)还是pop()(弹出栈顶元素),时间复杂度都是O(1).而java虚拟机栈只是JVM中的一块内存,用来存放局部变量..... 调用函数时我们会在java虚拟机栈中开辟一块内存叫栈帧.

     

      

     2)栈常见操作方法:

    1.stack.empty().判断栈是否为空,为空就返回false,否则返回true.

    2.stack.push().将元素压入栈底.

    3.stack.pop().将栈顶元素弹出栈.

    4.satck.peek().peek有窥视的意思,顾名思义作用就是查看栈顶元素,但不弹出.

     3)栈的实现:

            栈的底层实现既可以用顺序表也可以使用双向链表,二者实现方式大同小异,而我们使用的是顺序表.基本配置只需要一个数组来存放元素和一个usedSize记录顺序表元素的个数.构造方法初始化时我们可以将栈的大小初始化为5,后续不够再扩容.扩容使用Arrays.copyof()方法.

    1. class My_stack{
    2.     int[] elem;
    3.     int usedSize;
    4.  
    5.     public My_stack(int[] elem, int usedSize) {
    6.         this.elem = new int[5];
    7.         this.usedSize = usedSize;
    8.     }
    9.     public void push(int val){
    10.         if (usedSize==elem.length){//如果满了就扩容
    11.             Arrays.copyOf(elem,elem.length*2);
    12.         }
    13.         elem[usedSize] = val;
    14.         usedSize++;
    15.     }
    16.     public int pop(){
    17.         if (isEmpty()){
    18.             throw new RuntimeException("栈为空");
    19.         }
    20.         return elem[usedSize--];
    21.     }
    22.     public int peek(){
    23.         if (isEmpty()){
    24.             throw new RuntimeException("栈为空");
    25.         }
    26.         return elem[usedSize-1];
    27.     }
    28.     public boolean isEmpty(){
    29.         return usedSize==0;
    30.     }
    31. }

    二.栈相关题目

    1)逆波兰数

            逆波兰数也叫后缀表达式,早年计算机并没有用括号来规定四则运算的计算顺序,那么如果计算9+(3-1)x3+10/2总不能直接输9+3-1x3+10/2吧,于是睿智的科学家通过栈解决了这个难题,栈中存放的只能是数字,所以只要遇到数字就压栈,遇到运算符号就从栈顶弹出两个数字,最顶部的在操作符右边,下一个在操作符左边,运算完后将结果压栈,继续重复上述操作.

            在此题的基础上我们拓展中缀表达式转后缀表达式,首先按四则运算的优先级给表达式加上相应的括号((9+((3-1)x3))+(10/2))然后将每个括号中对应的操作符移到该括号之外:

    (((9((31)-3)x)+)10 2)/)+去掉括号后得:931-3x+102/+.

     

    1. class Solution {
    2.     public int evalRPN(String[] tokens) {
    3.         Stack str = new Stack<>();
    4.         for(int i = 0;i
    5.             String s = tokens[i];
    6.             if(!isoperation(s)){
    7.                 str.push(Integer.parseInt(s));//将数字压栈
    8.             }else{
    9.                 int num2 = str.pop();
    10.                 int num1 = str.pop();
    11.                 switch(s){
    12.                     case "+":
    13.                         str.push(num1+num2);
    14.                         break;
    15.                      case "-":
    16.                         str.push(num1-num2);
    17.                         break;
    18.                      case "*":
    19.                         str.push(num1*num2);
    20.                         break;
    21.                     case "/":
    22.                         str.push(num1/num2);
    23.                         break;
    24.                 }
    25.             }
    26.         }
    27.         return str.pop();
    28.     }
    29.     public boolean isoperation(String s){
    30.         if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
    31.             return true;
    32.         }
    33.         return false;
    34.     }
    35. }

    2)不可能的入栈方式

             根据栈"先进后出"的原理我们可以将pushed数组,每压入一个元素就与popped数组的栈顶元素相比较,如果相同就弹出压入数组的元素,然后访问popped数组的下一个元素继续比较.如果不相同,pushed数组继续压栈,重复上述操作.当pushed数组全部压入后,如果此时栈为空,那么符合出栈方式,如果不为空则不符合.

     

    1. class Solution {
    2.     public boolean validateStackSequences(int[] pushed, int[] popped) {
    3.         Stack stack = new Stack();
    4.          int j = 0;
    5.         for(int i = 0;i
    6.             stack.push(pushed[i]);
    7.             while(!stack.empty()&&i
    8.                 stack.pop();
    9.                 j++;
    10.             }
    11.         }
    12.         if(!stack.empty()){
    13.             return false;
    14.         }
    15.         return true;
    16.     }
    17. }

    3)有效括号

             通过了解题目大致有四种情况,1.左边括号多( ( ( ) 2.右边括号多( ( ) ) ) ) 3.左右括号不匹配{ ) [ } 4.左右括号匹配( ) { } .那么根据栈的特点,我们可以遇到左边的括号就压入栈中,遇到右边的括号便和栈顶的元素比较是否匹配,如果不匹配返回false.但要注意两点:1. 如果我们在比较的过程中发现栈为空,那么就是右边括号多,返回fasle.2.如果我们比较完毕,栈不为空,说明左边括号多,返回false.如果没有以上情形我们就可以返回true.

     

    1. class Solution {
    2.     public boolean isValid(String s) {
    3.         Stack stack = new Stack<>();
    4.         for(int i = 0;i
    5.             char ch = s.charAt(i);
    6.             if(ch=='('||ch=='['||ch=='{'){
    7.                 stack.push(ch);
    8.             }else{
    9.                 if(stack.empty()){//右边括号多
    10.                     return false;
    11.                 }
    12.                 char top = stack.peek();
    13.                 if((top=='('&&ch==')')||(top=='['&&ch==']')||(top=='{'&&ch=='}')){
    14.                     stack.pop();
    15.                 }else{
    16.                     return false;//左右括号不匹配
    17.                 }
    18.             }
    19.         }
    20.         if(!stack.empty()){//左面括号多
    21.             return false;
    22.         }
    23.     return true;
    24.     }
    25. }

    4)最小栈

            要想实现在常数时间内检索到最小元素的栈,那么一定不可能一个栈,因为根据栈的特点检索元素的时间复杂度必然是O(N),所以如果我们可以把栈的最小元素单独保存起来,那么当我们需要时查找最小元素时间复杂度必然是O(1).按照上述思路,首先我们创建两个栈,第一个栈中存放元素,第二个栈中存放最小值.其次压入元素时,如果是第一次压入,两个栈都压.否则判断要压入的元素是否小于第二个栈栈顶的元素,如果小于就压入第二个栈,否则就不压入.重复上述操作,无论任何时候我们都能按O(1)的时间复杂度取出第二个栈栈顶的元素,也就是最小的元素.

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

    三.队列的实现

            队列是只允许在一端进行插入另一端进行删除的线性表,与栈正好相反.简要概括为:"尾进头出",同样队列的实现底层既可以用顺序表也可以用链表.首先我们用单链表来实现,为了使入队和出队的时间复杂度都为O(1),我们需要记录单链表的头结点和尾结点,入队时尾插,出队时删除头结点即可.

    1)单链表实现队列

    1. class Node1{
    2.     public Node1 next;
    3.     public int val;
    4.  
    5.     public Node1(int val) {
    6.         this.val = val;
    7.     }
    8. }
    9. class My_queue{
    10.     public Node1 head;
    11.     public Node1 last;
    12.  
    13.     public void offer(int val){//入队
    14.         Node1 node1 = new Node1(val);
    15.         if (head==null){
    16.             head = node1;
    17.             last = node1;
    18.         }else {
    19.             last.next = node1;
    20.             last = last.next;
    21.         }
    22.     }
    23.     public int poll(){//出队
    24.         if (isEmpty()){
    25.             throw new RuntimeException("队列为空");
    26.         }
    27.         int pollVal = head.val;
    28.         head = head.next;
    29.         return pollVal;
    30.     }
    31.     public int peek(){
    32.         if (isEmpty()){
    33.             throw new RuntimeException("队列为空");
    34.         }
    35.         return head.val;
    36.     }
    37.     public boolean isEmpty(){
    38.         return head==null;
    39.     }
    40.  
    41. }

    2)循环队列

            循环队列的底层为顺序表,为了使出队和入队的时间复杂度都是O(1),我们必须记录顺序表元素的首尾,rear为队尾控制元素入队,front为队首控制元素出队. 为了使顺序表达到循环的效果,我们需要借助公式(rear+1)%elem.length,front也同样借助这个公式.基于顺序表的特点,删除元素时只需后移front,增加元素只需在rear下标增加元素,之后后移rear即可.

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

    四.队列相关题目

    1)用栈实现队列 

            一个栈必定无法实现队列,那么我们可以考虑用两个栈,入队时把要入队元素压入stack1中,出队时先把所有stack1中元素压入stack2中,然后弹出stack2的栈顶元素即可. 

    1. class MyQueue {
    2.  public Stack stack1;
    3.     public Stack stack2;
    4.  
    5.     public MyQueue() {
    6.         stack1 = new Stack<>();
    7.         stack2 = new Stack<>();
    8.     }
    9.  
    10.     public void push(int x) {
    11.         stack1.push(x);
    12.     }
    13.  
    14.     public int pop() {
    15.         if(empty()){
    16.             return -1;
    17.         }
    18.         if(stack2.empty()) {
    19.             int size = stack1.size();
    20.             for (int i = 0; i < size; i++) {
    21.                 stack2.push(stack1.pop());
    22.             }
    23.         }
    24.          return stack2.pop();
    25.     }
    26.     public int peek() {
    27.         if(empty()){
    28.             return -1;
    29.         }
    30.         if(stack2.empty()) {
    31.             int size = stack1.size();
    32.             for (int i = 0; i < size; i++) {
    33.                 stack2.push(stack1.pop());
    34.             }
    35.         }
    36.          return stack2.peek();
    37.     }
    38.  
    39.     public boolean empty() {
    40.         return stack1.empty()&&stack2.empty();
    41.     }
    42. }

    2)用队列实现栈

            同样一个队列也无法实现栈,可以考虑使用两个队列,入队时哪个队列为空入哪个 ,如果都为空就入que1.但是与栈不同的是队列的出队顺序,我们不能把que1中的元素全部放入que2再出que2中的元素,而是移size-1个到que2,出que1.假设入队都在que1中,那么出队时只需将que1中的size-1个元素移到que2中,然后弹出que1中的元素即可.

    1. class MyStack {
    2.  
    3.      public Queue que1;
    4.     public Queue que2;
    5.  
    6.     public MyStack() {
    7.         que1 = new LinkedList<>();
    8.         que2 = new LinkedList<>();
    9.     }
    10.     public void push(int x) {
    11.         if (!que1.isEmpty()){
    12.             que1.offer(x);
    13.         }else if (!que2.isEmpty()){
    14.             que2.offer(x);
    15.         }else {
    16.             que1.offer(x);
    17.         }
    18.     }
    19.  
    20.     public int pop() {
    21.         if (empty()){
    22.             return -1;
    23.         }
    24.         if (!que1.isEmpty()){
    25.             int size = que1.size();
    26.             for (int i = 0; i 1 ; i++) {
    27.                 que2.offer(que1.poll());
    28.             }
    29.             return que1.poll();
    30.         }
    31.         if (!que2.isEmpty()){
    32.             int size = que2.size();
    33.             for (int i = 0; i 1 ; i++) {
    34.                 que1.offer(que2.poll());
    35.             }
    36.             return que2.poll();
    37.         }
    38.         return -1;
    39.     }
    40.  
    41.     public int top() {
    42.         if (empty()){
    43.             return -1;
    44.         }
    45.         if (!que1.isEmpty()){
    46.             int size = que1.size();
    47.             int val = -1;
    48.             for (int i = 0; i 
    49.                 val = que1.poll();
    50.                 que2.offer(val);
    51.             }
    52.             return val;
    53.         }
    54.         if (!que2.isEmpty()){
    55.             int size = que2.size();
    56.             int val = -1;
    57.             for (int i = 0; i 
    58.                 val = que2.poll();
    59.                 que1.offer(val);
    60.             }
    61.             return val;
    62.         }
    63.         return -1;
    64.     }
    65.  
    66.     public boolean empty() {
    67.         return que1.isEmpty()&&que2.isEmpty();
    68.     }
    69. }

    总结

            以上就是快速入门栈和队列的全部内容了,在了解栈和队列的各种实现并手撕相关习题,相信我们已经熟练掌握了栈和队列,如果我的文章对你有亿点点帮助和启发,麻烦不要忘记三连哦!

  • 相关阅读:
    UNCTF-日常训练-reverse-easyMaze
    spring cloud 小试牛刀
    【头歌-Python】8.3 政府工作报告数据提取(project)-第4关
    7 款好用的 PDF 密码删除工具
    R语言生物群落数据统计分析
    计算机网络期末知识点（第二章-物理层）
    Qt 在linux上检测内存泄漏，用valgrind的问题
    AirServer最新Win64位个人版投屏软件
    浅析“代码可视化” | 京东云技术团队
    ros 常用是命令
  • 原文地址：https://blog.csdn.net/liu_xuixui/article/details/126091883