栈和队列及其背后的数据结构

文章目录

一、栈(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 voidpush(int item){if(top==elem.length){
            Arrays.copyOf(elem,5);return;}
        elem[top]=item;
        top++;}
    public intpop(){if(top==0){
            throw new UnsupportedOperationException("栈为空");}
        top--;int ret = this.elem[top];return ret;}
    public intpeek(){if(top==0){
            throw new UnsupportedOperationException("栈为空");}return this.elem[top-1];}
    public intsearch(int item){return0;}}

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 voidpush(int data){
        Node node = new Node(data);if(head==null){
            head=node;}else{
            node.next=head;
            head=node;}}
    public intpop(){int ret = head.val;
        head=head.next;return ret;}
    public voiddisplay(){
        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<Character> 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;}}elseif(ch=='}'){if(!stack.empty()&&stack.peek()=='{'){
                        stack.pop();}else{return false;}}elseif(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<Integer> stack ;
    private Stack<Integer> minStack;
    public MinStack(){
        stack=new Stack<>();
        minStack = new Stack<>();}
    
    public voidpush(int val){
        stack.push(val);if(minStack.empty()){
            minStack.push(val);}else{int top = minStack.peek();if(top>=val){
                minStack.push(val);}}}
    
    public voidpop(){if(stack.empty()){return;}int top = stack.pop();if(top==minStack.peek()){
            minStack.pop();}}
    
    public inttop(){if(stack.empty()){return-1;}return stack.peek();}
    
    public intgetMin(){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 voidoffer(int data){
        Node node = new Node(data);if(first==null){
            first=node;
            last=node;return;}
        last.next=node;
        last=node;}
    public intpoll(){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 intremove(){if(first==null){return-1;}int ret = first.val;
        first=first.next;return ret;}
    public intpeak(){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<Integer> que1;
    private Queue<Integer> que2;
    public MyStack(){
        que1=new LinkedList<>();
        que2=new LinkedList<>();}
    
    public voidpush(int x){if(!que1.isEmpty()){
            que1.offer(x);}elseif(!que2.isEmpty()){
            que2.offer(x);}else{
            que1.offer(x);}}
    
    public intpop(){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 inttop(){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<Integer> stack1 ;
    Stack<Integer> stack2 ;
    public MyQueue(){
        stack1=new Stack<>();
        stack2=new Stack<>();}
    
    public voidpush(int x){
        stack1.push(x);}
    
    public intpop(){if(empty()){return-1;}if(stack2.empty()){while(!stack1.empty()){int x = stack1.pop();
                stack2.push(x);}}return stack2.pop();}
    
    public intpeek(){if(empty()){return-1;}if(stack2.empty()){while(!stack1.empty()){int x = stack1.pop();
                stack2.push(x);}}return stack2.peek();}
    
    public boolean empty(){return stack1.empty()&&stack2.empty();}}

例三：设计循环队列

对应leetcode题

思路：队列的底层是一个数组,设其为elem，设计循环队列能够避免队列的"假满"情况，我们可以设置front（指向队头元素）和rear（指向在队尾可以放的元素）两个坐标来操作循环链表。

设计循环链表需要的知识：
1、front和rear初始化的值都为0，代表循环队列为空。

2、front和rear每当有元素出队或有元素入队时的下一个下标为

front=(front+1)%elem.length

或

rear=(rear+1)%elem.length

。

3、front和rear开始的时候都置为0，但是会有一种情况出现。我们假设elem数组的长度为8，则最后一个下标为7。假设没有任何元素出队，则front一直指向0下标。当rear指向下标为7的元素时，该元素再入队后经公式计算得rear指向的下标为0，此时front和rear相等，那么队满和队空的判断条件就冲突了。因此我们可以浪费最后一个元素的位置来判断队空还是队满。

4、当我们取队尾元素的时候，不能想当然地直接去取rear-1的元素。因为rear也有可能会在下标为0的位置出。因此只要判断rear是否在0位置处，如果是则直接返回的是elem.length-1的下标位置，否则就可以指向rear-1的下标的元素。

5、因为我们要浪费最后一个下标的空间来判断循环队列是满还是空，因此假设数组的长度为k，我们只能放k-1个元素，但是leetcode中的循环队列要求你初始化多长的数组就要放多少个元素。则在初始化数组的时候加个1即可。

代码：

class MyCircularQueue {
    private int[] elem ;
    private int front ;
    private int rear;
    public MyCircularQueue(int k){
        elem=new int[k+1];
        front=0;
        rear=0;}
    
    public boolean enQueue(int value){if(isFull()){return false;}
        elem[rear]=value;
        rear=(rear+1)%elem.length;return true;}
    
    public boolean deQueue(){if(isEmpty()){return false;}
        front=(front+1)%elem.length;return true;}
    
    public intFront(){if(isEmpty()){return-1;}return elem[front];}
    
    public intRear(){if(isEmpty()){return-1;}int index =(rear==0)?elem.length-1:rear-1;return elem[index];}
    
    public boolean isEmpty(){if(rear==front){return true;}return false;}
    
    public boolean isFull(){if((rear+1)%elem.length==front){return true;}return false;}}

如果觉得这篇文章对你受益匪浅，麻烦点个赞支持一下谢谢！