拨开荷叶行，寻梦已然成。仙女莲花里，翩翩白鹭情。
IMG-LOGO
    拨开荷叶行，寻梦已然成。仙女莲花里，翩翩白鹭情
主页 文章列表 堆栈和队列及其背后的资料结构

堆栈和队列及其背后的资料结构

白鹭 - 2022-03-03 2362 0 0


文章目录

  • 一、堆栈(Stack)


    • 例一：不可能的输出序列

    • 例二：中缀表达式转后缀表达式

    • 例三：有效的括号

    • 例四：最小堆栈

    • 1.堆栈的基本概念

    • 2.用顺序表实作堆栈

    • 3.用链表实作堆栈

    • 4.有关堆栈的相关面试题


  • 二、队列(Queue)


    • 例一：用队列实作堆栈

    • 例二：用堆栈实作队列

    • 例三：设计回圈队列

    • 1.队列的基本概念

    • 2.用链表实作队列

    • 3.有关队列的面试题



<hr color="#000000" size="1"">

一、堆栈(Stack)

1.堆栈的基本概念

堆栈：一种特殊的线性表，其只允许在固定的一端进行插入和洗掉元素操作，进行资料插入和洗掉操作的一端称为堆栈顶，另一端称为堆栈底，堆栈中的资料元素遵守后进先出LIFO（Last In First Out）的原则，

压堆栈：堆栈的插入操作叫做进堆栈/压堆栈/入堆栈，入资料在堆栈顶，
出堆栈：堆栈的洗掉操作叫做出堆栈，出资料在堆栈顶，

堆栈顶指标：顾名思义，堆栈顶指标是指向堆栈顶的一个指标，但Java当中没有指标这一说法，因此也可以当作下标来进行处理，

需要注意的是：堆栈顶指标指向的是可以存放元素的堆栈的位置，一旦有元素放入后它再加1，

在这里插入图片描述
Stack中的方法有：
在这里插入图片描述
push为压堆栈，pop为出堆栈（回传值为出堆栈的值），peek为堆栈顶元素，empty为判断堆栈是否为空，search为找出某个元素在堆栈中的第几个位置，回传下标，

2.用顺序表实作堆栈

用顺序表实作的堆栈称为顺序堆栈，只是该顺序表的实际操作也是一样要遵循堆栈的基本操作——先进后出，

public class MyStack {
    private int[] elem ;
    private int top = 0 ;

    public MyStack() {
        this.elem = new int[3];
    }

    public void push(int item) {
        if(top==elem.length) {
            Arrays.copyOf(elem,5);
            return;
        }
        elem[top]=item;
        top++;
    }
    public int pop() {
        if(top==0) {
            throw new UnsupportedOperationException("堆栈为空");
        }
        top--;
        int ret = this.elem[top];
        return ret;
    }
    public int peek() {
        if(top==0) {
            throw new UnsupportedOperationException("堆栈为空");
        }
        return this.elem[top-1];
    }
    public int search(int item) {
        return 0;
    }}


3.用链表实作堆栈

**用链表实作堆栈要注意一个点：因为堆栈遵循的是先进后出，因此我们在入堆栈时的操作为单链表的头插法，出堆栈时的操作为洗掉单链表的头结点，并使得头结点指向下一结点，**只有这样用单链表实作堆栈才能做到时间复杂度为O(1)，

class Node{
    public int val;
    public Node next;

    public Node(int val) {
        this.val = val;
    }}public class MyLinkedStack {
    public Node head;
    public void push(int data) {
        Node node = new Node(data);
        if(head==null) {
            head=node;
        } else {
            node.next=head;
            head=node;
        }
    }
    public int pop() {
        int ret = head.val;
        head=head.next;
        return ret;
    }
    public void display() {
        Node cur = head;
        while(cur!=null) {
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    }}


4.有关堆栈的相关面试题

例一：不可能的输出序列

题目：一个堆栈的入堆栈序列是a,b,c,d,e则堆栈的不可能的输出序列是：（）
A edcbd B decba C dceab D abcde

解：答案为C，一定要时刻注意堆栈的特点：先进后出，分析B选项，因为第一个出堆栈为d，则直接入堆栈到d后停止，d出堆栈，还剩a,b,c；第二个出堆栈为c，则还剩a，b；第三个出堆栈为e，则我们可以令e入堆栈后再出，此时还是剩a，b；再将b，a出堆栈则为b选项，D选项则是每一个进堆栈后直接先出，

例二：中缀表达式转后缀表达式

题目：将中缀表达式转为后缀表达式，如中缀表达式X = a+b * c-d，则其后缀表达式为？

解：因为是一个表达式，先用括号将整体括起来(X = a+b * c-d)，又因为从左到右运算时，先运算的是乘，将b * c用括号括起来，则为(X=a+(b * c)-d)；接着是用bc的结果去加a，将a与它用括号括起来，则为(X=(a+(bc))-d)；最后再计算减d，结果为(X=((a+(b * c))-d))，再将运算子移到相应右括号的外面再将括号去掉，最终得后缀表达式为Xabc * +d-= ，

例三：有效的括号

对应leetcode题

思路：因为题目的要求是括号是否匹配，将左括号（包括左大括号、左中括号、左小括号）压入堆栈中，如果不是左括号，则与堆栈顶的左括号进行匹配，‘(‘ 对应 ‘)’；‘[’d对应’]’；‘{’对应‘}’，否则回传false，

此题有四种情况：
1.左括号和右括号相等的情况下，左括号与右括号出现了不匹配的情况，回传false，
2.左括号多于右括号不可能匹配成功，现象为遍历字符串结束后堆栈中还有元素，
3.右括号多于左括号也不可能匹配成功，现象为当遍历到右括号时堆栈中没有元素跟其进行配对，
4.左括号与右括号都配对成功，并且遍历完字符串后堆栈中没有元素，

例如"{[]}"字符串，首先初始化一个堆栈，将‘{’压入堆栈中，下一个为‘[’，是左括号压入堆栈中，下一个为‘]’，与堆栈中的第一个元素进行配对，发现为‘[’，则将堆栈顶元素出堆栈，下一个为‘}’，与堆栈中的元素‘{’匹配成功，最后字符串遍历完成并堆栈中没有元素，回传true，

class Solution {
    public boolean isValid(String s) {
        Stack stack = new Stack<>();
        int i = 0;
        while(i<s.length()) {
            if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='[') {
                stack.push(s.charAt(i));
            }else {
                char ch = s.charAt(i);
                if(ch==')') {
                    if(!stack.empty()&&stack.peek()=='(') {
                        stack.pop();
                    } else {
                        return false;
                    }
                } else if(ch=='}') {
                    if(!stack.empty()&&stack.peek()=='{') {
                        stack.pop();
                    }else {
                        return false;
                    }
                } else if(ch==']') {
                    if(!stack.empty()&&stack.peek()=='[') {
                        stack.pop();
                    }else {
                        return false;
                    }
                }
            }
            i++;
        }
        if(stack.empty()) {
            return true;
        }
        return false;
    }}


例四：最小堆栈

对应leetcode题

思路：初始化两个堆栈，一个为stack普通堆栈，另一个为minStack专门用来存放每次压入堆栈stack中的最小值，
1、当一个元素要压入stack中（push方法），则minStack是否要压入堆栈有两种情况：(1)当minStack为空时，直接将该元素压入minStack中即可，(2)当minStack不为空，则需要与minStack中的堆栈顶元素进行比较，如果小于或等于minStack堆栈顶元素，则压入minStack中；否则无需压入minStack，
2、当一个元素要从stack中出堆栈（pop方法），则minStack对应的处理：如果stack中出堆栈的元素与minStack的堆栈顶元素相同，它们对应堆栈中的最小值，minStack中的堆栈顶元素也要出堆栈，
3、minStack中的堆栈顶元素就是stack中全部元素的最小值，

class MinStack {
    private Stack stack ;
    private Stack minStack;
    public MinStack() {
        stack=new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()) {
            minStack.push(val);
        }else {
            int top = minStack.peek();
            if(top>=val) {
                minStack.push(val);
            }
        }
    }
    
    public void pop() {
        if(stack.empty()) {
            return;
        }
        int top = stack.pop();
        if(top==minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        if(stack.empty()) {
            return -1;
        }
        return stack.peek();
    }
    
    public int getMin() {
        if(minStack.empty()) {
            return -1;
        }
        return minStack.peek();
    }}


二、队列(Queue)

1.队列的基本概念

只允许在一端进行插入资料操作，在另一端进行洗掉资料操作的特殊线性表，队列具有先进先出FIFO(First In First Out) ，入队列：进行插入操作的一端称为队尾（Tail/Rear） ，出队列：进行洗掉操作的一端称为队头（Head/Front），
在这里插入图片描述
Queue界面中的方法：
在这里插入图片描述
add和offer方法没什么大致的区别，都是入队操作，remove为洗掉某一个元素（但是它不太符合队列的特点，因此比较少用），poll为出队操作，并且回传的是出队时的元素，element和peek都为获得队头的元素，但对对头不进行操作，

Queue

错误处理抛出例外回传特殊值
入队列add(e)offer(e)
出队列remove()poll()
队首元素element()peek()

Deque(双端队列)其实也是用链表实作，操作不同
在这里插入图片描述

2.用链表实作队列

为何不用顺序表实作队列是因为用队列是遵循先进先出原则的，这样的话在顺序表当中很容易造成“假的”满队列，即队列当中没有任何元素并且front和rear都指向了顺序表的最后一个位置就不能再放入元素，为了避免这种情况发生，顺序表只能在每次模仿队列的出队时，表头元素出顺序表则后面的元素都要向前挪一个单位，这样时间复杂度就达到了O(n)，

链表来实作队列能做到入队和出队的时间复杂度为O(1)，即出队操作：在表尾处设定last结点，当有元素入队时last结点指向该新结点，再将last结点改为新结点处，入队操作：在表头处设定head结点，当有元素出队时head指向它的下一个结点，

图解：
1、初始链表
在这里插入图片描述

2、入队
在这里插入图片描述
3、出队
在这里插入图片描述
代码：

class Node {
    public int val;
    public Node next;

    public Node(int val) {
        this.val = val;
    }}public class MyLinkedQueue {
    public Node first;
    public Node last;

    public void offer(int data) {
        Node node = new Node(data);
        if(first==null) {
            first=node;
            last=node;
            return;
        }
        last.next=node;
        last=node;
    }
    public int poll() {
        if(first==null) {
            throw new UnsupportedOperationException("队列为空");
        }
        int ret = first.val;
        first=first.next;
        return ret;
    }
    public boolean isEmpty() {
        if(first==null) {
            return true;
        }
        return false;
    }
    public int remove() {
        if(first==null) {
            return -1;
        }
        int ret = first.val;
        first=first.next;
        return ret;
    }
    public int peak() {
        if(first==null) {
            throw new UnsupportedOperationException("队列为空");
        }
        int ret = first.val;
        return ret;
    }}


3.有关队列的面试题

例一：用队列实作堆栈

对应leetcode题

思路：题目给出要用两个队列实作堆栈，因此我们可以先初始化两个队列que1和que2，重点和难点是要在两个队列的出队或入队的操作中实作堆栈的先进后出原则，

1、push方法：如果是一开始两个队列均为空，则入队的元素任选一个队入队即可；当不是第一次入队，则入队的元素选择在不为空的队当中入，则结果肯定是有一个队有元素，而另一个队为空队，
2、pop方法：因为堆栈的特点是后进先出，即后入队的要先出队，则我们可以把有元素的队的队长减1个元素直接入队到另一条队中，还剩下的那一个元素不再入队，直接poll即可，
3、top方法：跟pop的操作方法类似，只是将一个队当中的全部元素入到另一个队当中，并且回传的是最后一个入队的元素，
4.empty方法：如果两个队列均为空，则堆栈为空，回传true，

图解：
1、初始化两个队列
在这里插入图片描述
2、入堆栈（假设入12、33和45）
在这里插入图片描述

3、出堆栈（假设出45）
在这里插入图片描述
4、入堆栈（入67）
在这里插入图片描述
大概的操作就这幺多，以此类推，

class MyStack {
    private Queue que1;
    private Queue que2;
    public MyStack() {
        que1=new LinkedList<>();
        que2=new LinkedList<>();
    }
    
    public void push(int x) {
        if(!que1.isEmpty()) {
            que1.offer(x);
        }else if(!que2.isEmpty()) {
            que2.offer(x);
        }else {
            que1.offer(x);
        }
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }else {
            if(!que1.isEmpty()) {
                int size = que1.size();
                int i=0;
                while(i<size-1) {
                    que2.offer(que1.poll());
                    i++;
                }
                return que1.poll();
            }else{
                int size = que2.size();
                int i=0;
                while(i<size-1) {
                    que1.offer(que2.poll());
                    i++;
                }
                return que2.poll();
            }
        }
    }
    
    public int top() {
        if(empty()) {
            return -1;
        }else {
            if(!que1.isEmpty()) {
                int size = que1.size();
                int i=0;
                int x=-1;
                while(i<size) {
                    x = que1.poll();
                    que2.offer(x);
                    i++;
                }
                return x;
            }else{
                int size = que2.size();
                int i=0;
                int x = -1;
                while(i<size) {
                    x=que2.poll();
                    que1.offer(x);
                    i++;
                }
                return x;
            }
        }
    }
    
    public boolean empty() {
        return que1.isEmpty()&&que2.isEmpty();
    }}


注意：Queue是一个界面，不可以直接初始化，它的界面内部没有size方法，但它是继承与Collection的（Collection界面有size方法），并且此处参考的是子类LinkedList物件，则重写了size方法，

例二：用堆栈实作队列

对应leetcode题

思路：题目要求用两个堆栈来实作队列，即要用堆栈来实作先进先出原则，先初始化两个堆栈stack1和stack2，一个堆栈只能进行push，另一个只能进行pop，

1、push方法：只能在其中一个堆栈当中入堆栈，此处令stack1只能进行入堆栈操作，则当有元素要push时直接压入stack1中，
2、pop方法：此处令stack2只能进行出堆栈操作，如果stack1和stack2为空则无法再出堆栈，若stack1有元素而stack2为空，则将stack1中的元素全部压入stack2中，再将stack2中的堆栈顶元素出堆栈，则能够模仿出队操作，若stack2已经不为空了，则直接将堆栈顶元素出堆栈即可，
3、peek方法：stack2当中的堆栈顶元素等同于队列的队头元素，若stack2为空则同为pop方法的操作将stack1中的堆栈元素全部压入stack2中，再取stack2中的堆栈顶元素，
4、empty方法：若两个堆栈都为空，则模仿的队列为空，回传true，

图解：
1、压队（先将12，33，45入队）
在这里插入图片描述
2、出队（将12出队）
在这里插入图片描述
3、取队头元素：就是stack2中的堆栈顶元素，

class MyQueue {
    Stack stack1 ;
    Stack stack2 ;
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(stack2.empty()){
            while(!stack1.empty()) {
                int x = stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.pop();
    }
    
    public int peek() {
        if(empty()) {
            return -1;
        }
        if(stack2.empty()){
            while(!stack1.empty()) {
                int x = stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.peek();
    }
    
    public boolean <s
标签:
上一个
将多个影像的大小调整为特定的正方形比例而不进...
下一个
假设一下，如果我们所有中国人都不买瑞士表后，...

0 评论

发表评论

您的电子邮件地址不会被公开。 必填的字段已做标记 *

  • 最新文章

  • 随机推荐

    • 热门分类

    热门标签

    人生 坛凛沙 EBOD-836 佐佐木明希 竹内美涼 今田光 豊中アリス 樱乃莉乃 纱希 肉体