2022年考研数据结构_3 栈和队列

叁歲伎倆 2022-12-31 05:22 265阅读 0赞

https://gitee.com/fakerlove/Data-Structure

### 文章目录 ###

*  3. 栈和队列
 *   *  3.1 栈
     *   *  3.1.1 栈的定义
         *  3.1.2 栈的实现
         *  3.1.3 栈的应用
         *   *  (1)递归
             *  (2)四则运算表达式求解
             *   *  ①中缀表达式转后缀表达式
                 *  ②后缀表达式的计算
     *  3.2 队列
     *   *  3.2.1 队列的定义
         *  3.2.2 队列的实现
         *  3.2.2 队列的应用
     *  3. 3 应用
     *   *  3.3.1 表达式
         *   *  语言表示1--中缀转后缀
             *  语言表述2--中缀转后缀
             *  优先级
             *  代码--中缀转后缀

# 3. 栈和队列 #

## 3.1 栈 ##

### 3.1.1 栈的定义 ###

栈是限定仅在表尾进行插入和删除操作的线性表。把允许插入的一端称为栈顶，另一端称为栈底，不含任何元素的栈称为空栈。栈是**后进先出的线性表**。

### 3.1.2 栈的实现 ###

栈的实现有数组和链表两种方式。其中，数组方式很简单，就是定义一个数组，然后用一个int类型的变量用来标识栈顶，每次入栈的时候将新元素插入到数组尾处，这里就不实现了。因为在[链表][Link 1]一节中已经实现了单链表，以及在其尾部插入（相当于入栈操作）的算法，我们这里直接就继承我们实现的单链表，增加栈的弹栈、是否为空的判断两个方法。实现代码如下：

*  **Java**

public class LinkStack<T> extends LinkList<T> { 
        public boolean isEmpty(){ 
            return length==0;
        }
    
        /** * 弹栈 * @return */
        public T pop(){ 
            if (this.head!=null){ 
                return remove(this.length-1);
            }
            return null;
        }
    }
    
    1234567891011121314151617

上述代码中，LinkList的实现见[链表][Link 1]一节。使用示例如下：

LinkStack<String> stack=new LinkStack<>();
            stack.pushBack("0");
            stack.pushBack("1");
            stack.pushBack("2");
            System.out.println(stack);
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
    12345678

此处的链表是使用的**尾插法**，但是这样其实**在弹栈以及入栈的时候性能并不好，因为每次入栈和弹栈都需要遍历链表，所以应该使用头插法**，此处就需要重写单链表中的pushBack方法。重写后的链式存储栈的代码如下：

public class LinkStack<T> extends LinkList<T> { 
        public boolean isEmpty(){ 
            return length==0;
        }
    
        /** * 弹栈 * @return */
        public T pop(){ 
            if (this.head!=null){ 
                return remove(0);
            }
            return null;
        }
         /** * 获取栈尾元素，但并不弹出 * @return */
        public T peek(){ 
            if (this.head!=null){ 
                return get(0);
            }
            return null;
        }
        
        /** * 重写pushback方法，使用头插法，每次将节点插入到链表的头部 * @param data */
        @Override
        public void pushBack(T data) { 
            insert(0,data);
        }
    
        /** * 重写toString方法，从后往前输出 * @return */
        @Override
        public String toString() { 
            String result="";
            Node node=head;
            while (node!=null){ 
                result=node.getData()+","+result;
                node=node.getNext();
            }
            return result;
        }
    }
    1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950

在重写pushBack和pop方法的同时，还要重写toString，让输出是从后往前输出。使用头插法以后，这个链式栈的性能就好多了。同理，我们用C++来实现头插法的链式栈。其中父类LinkList的实现仍见[链表][Link 1]一节。

*  **C++**

#include "../LinkList/LinkedList.h"
    template<class T>
    class LinkStack:LinkList<T>
    { 
    public:
    	/* * 重写插入方法，使用头插法 */
    	void pushBack(T data)
    	{ 
    		insert(0, data);
    	}
    	T peek(){ 
            if (this->head!=null){ 
                return get(0);
            }
            return NULL;
        }
    	
    	T pop()
    	{ 
    		if(this->head)
    		{ 
    			return remove(0);
    		}
    		return NULL;
    	}
    };
    
    1234567891011121314151617181920212223242526272829

使用示例为：

LinkStack<string> link_stack;
    	link_stack.pushBack("0");
    	link_stack.pushBack("1");
    	link_stack.pushBack("2");
    	cout << link_stack.pop()<<",";
    	cout << link_stack.pop()<<",";
    	cout << link_stack.pop()<<",";
    1234567

### 3.1.3 栈的应用 ###

栈最最常见的应该是平时软件中用到的撤销或者回退了吧。除此之外，栈还有很多的应用，下面介绍几个应用。

#### (1)递归 ####

函数自己调用自己，就是递归。递归的调用需要栈的辅助，在每次调用自己之前，都要将当前的变量压栈存储起来，以便回退时恢复。  
在这里，我想说一个以前没有搞清楚的应该使用递归解决的例子。

*  **问题描述：** 求0—n-1这n个数的全排列
 *  **样例：** 输入3，输出012,021,102,120,210,201。
 *  **分析：** 求1—n-1的全排列，过程应是这样的：先将第一个数固定，然后求剩下的n-1个数的全排列。求n-1个数的全排列的时候，还是一样，将第一个数固定，求n-2个数的全排列。直到剩下一个数，那他的全排列就是自己。那这个固定的数字应该有多种取值，比如求0,1,2三个数的全排列，固定的第一个数，应有0,1,2三种取值对吧，当固定第一个数，比如固定了0，那剩下1,2两个数，再固定一个数，这个数有1和2两种取值，有没有发现什么？我们发现，这个固定的数的取值，不就是将固定的位置的数和剩下的数字不断交换的过程么。理解了这个，来写代码看看（此处只写java代码，因为我这里每个例子都是用内部类定义的，所以class前面都有public和static关键字）。
 *  **Java实现**

public static class FullArrange{ //全排列
    
            /** * 将list中，下标为i和下标为j的两个元素交换 * @param list * @param i * @param j */
            public void swap(int[] list,int i,int j){ 
                int tmp=list[i];
                list[i]=list[j];
                list[j]=tmp;
            }
    
            public void perm(int[] list,int start,int end){ 
                if (start==end-1){ 
                    String tmp="";
                    for (int i=0;i<end;i++)
                       tmp+=list[i]+",";
                    System.out.println(tmp);
                }else { 
                    for (int i=start;i<end;i++){ 
                        swap(list,start,i);
                        perm(list,start+1,end);
                        swap(list,start,i);
                    }
                }
            }
    
            /** * 测试函数，输出0——n的全排列 * @param n */
            public void test(int n){ 
                int[] list=new int[n];
                for (int i=0;i<n;i++)
                    list[i]=i;
                perm(list,0,n);
            }
        }
    12345678910111213141516171819202122232425262728293031323334353637383940

上述代码，其他的都很好理解，关键在于下面这三句代码：

swap(list,start,i);
    perm(list,start+1,end);
    swap(list,start,i);
    123

其中，第一句很好理解，就是那个固定的数的所有取值，第二句也好理解，就是求当一个数字固定后，剩下的数的全排列（这里就是递归），那第三句是干啥的呢？其实也比较好理解，第三句的作用是**将第一句元素交换后的数组还原**，你在第一句代码中将数组中的元素交换过了，求过递归以后，应该把数组还原，不然数组就和原来的不一样了。  
使用示例：

FullArrange arrange=new FullArrange();
     arrange.test(3);
    12

输出结果

0,1,2,
    0,2,1,
    1,0,2,
    1,2,0,
    2,1,0,
    2,0,1,
    123456

#### (2)四则运算表达式求解 ####

四则运算表达式应该是栈的一个最常见的应用了。对于一个四则运算表达式“9+(3-1)×3+10÷2”，要计算其值，首先应该把这个中缀表达式转换为后缀表达式，然后再对后缀表达式进行求解。

##### ①中缀表达式转后缀表达式 #####

有关什么是中缀表达式，什么是后缀表达式我这里就不赘述了，大家自行百度。中缀表达式转后缀表达式的规则为：

*  1)读取到数字，直接输出
 *  2)当读取到左括号"("时，直接压栈，当读取到运算符时，分两种情况讨论  
    a.当运算符栈为空或者栈顶操作符的优先级小于当前运算符优先级时(如+和-的优先级低于 \* 和 /)，直接入栈  
    b.当运算符不为空时且栈顶操作符的优先级大于或等于当前运算符优先级时，循环执行出栈操作并输出，直到遇到优先级小于当前运算符的元素为止。循环执行完后再将当前运算符压栈。另外需要注意的是，只有遇到右括号时，左括号才出栈
 *  3)当遇到右括号")"时，循环执行出栈操作并加入到list中，直到遇到左括号为止。并将左括号弹出，但不加入list中
 *  4)表达式的值读取完后，将操作符栈中的所有元素弹出并输出

如“9+(3-1)×3+10÷2”，先输出9；加号进栈；左括号进栈；输出3；减号进栈；输出1；遇到右括号，一直输出栈顶元素直到遇到左括号，所以减号和左括号输出；×进栈；输出3；遇到加号，×和-出栈，+入栈；输出10；÷入栈；输出2；栈中元素全部出栈，得到最后结果：9 3 1 - 3 × + 10 2 ÷ +。

##### ②后缀表达式的计算 #####

后缀表达式也会用到栈，其具体规则为：**从左到右遍历后缀表达式的每个数字和符号，遇到数字就进栈，遇到符号，就将处于栈顶的两个数字出栈，进行运算，并将运算结果进栈，一直到最终获得结果**。  
下面仍然用Java来实现中缀表达式转后缀表达式以及后缀表达式的求解（因为我这里每个例子都是用内部类定义的，所以class前面都有public和static关键字），C++的过程和此类似，我这里就不写了。

*  **Java**

public static class CalculateMathExpression{ //四则运算表达式求解
    
            /** * 将输入的中缀表达式转换成后缀表达式 * @param inString 中缀表达式的字符串 * @return 分离得到的后缀表达式 */
            public static List<String> inTransPost(String inString) throws Exception { 
                ArrayList<String> result=new ArrayList<>();
                LinkStack<String> stack=new LinkStack<>();
                for (int i=0;i<inString.length();i++){ 
                    char item=inString.charAt(i);
                    if ((item>='0'&&item<='9')||item=='.'){ //如果是数字加入到输出队列
                        //此处进行两位数的处理
                        String tmp=String.valueOf(item);
                        int j=i+1;
                        while (j<inString.length()){ 
                            char item2=inString.charAt(j);
                            if ((item2>='0'&&item2<='9')||item2=='.')
                            { 
                                tmp+=String.valueOf(item2);
                                j++;
                            }
                            else
                                break;
                        }
                        result.add(tmp);
                        if (j!=i+1)//数字是一位数
                            i=j-1;
                        continue;
                    }
                    else if (item=='(')
                    { 
                        stack.pushBack(String.valueOf('('));
                        continue;
                    }
                    else if (item=='+'||item=='-'){ 
                        while (!stack.isEmpty()&&!stack.peek().equals("("))
                            result.add(stack.pop());
                        stack.pushBack(String.valueOf(item));
                        continue;
                    }
                    else if (item=='*'||item=='/'){ 
                        while (!stack.isEmpty()&&(stack.peek().equals("*")||stack.peek().equals("/")))
                            result.add(stack.pop());
                        stack.pushBack(String.valueOf(item));
                        continue;
                    }
                    else if (item==')'){ 
                        while (!stack.isEmpty()&&!stack.peek().equals("("))
                            result.add(stack.pop());
                        stack.pop();
                        continue;
                    }else
                        throw new Exception("遇到未知操作符");
                }
                while (!stack.isEmpty())
                    result.add(stack.pop());
                return result;
            }
    
            /** * 计算中缀表达式的值 * @param inString * @return */
            public static float calcExpressionValue(String inString){ 
                List<String> postStr=null;
                try { 
                    postStr=inTransPost(inString);
                }catch (Exception e){ 
                    System.out.println("输入数据中有未知字符！");
                    return Float.NaN;
                }
                if (postStr!=null){ 
                    String outStr="输入的中缀表达式转换成后缀表达式为：";
                    LinkStack<Float> stack=new LinkStack<>();
                    for (String str:postStr)
                    { 
                        outStr+=str+" ";
                        try { 
                            if (str.equals("+")||str.equals("-")||str.equals("*")||str.equals("/")){ //如果遇到操作符，则弹出两个操作数，将计算结果压栈
                                Float val2=stack.pop();
                                Float val1=stack.pop();
                                float result=operate(val1,val2,str);
                                stack.pushBack(result);
    
                            }else { //如果遇到数字直接压栈
                                Float val=Float.valueOf(str);
                                stack.pushBack(val);
                            }
                        }
                        catch (NumberFormatException e){ //捕获字符串转数字时出现异常
                            System.out.println("字符串转换成数字出错！");
                            return Float.NaN;
                        }
                    }
                    System.out.println(outStr);
                    return stack.pop();
                }
                return Float.NaN;
            }
    
            /** * 根据操作符计算两个数的值 * @param val1 第一个操作数 * @param val2 第二个操作数 * @param operator 操作符，+ - * /中的一个 * @return */
            private static float operate(Float val1,Float val2,String operator){ 
                if (operator.equals("+"))
                    return val1+val2;
                else if (operator.equals("-"))
                    return val1-val2;
                else if (operator.equals("*"))
                    return val1*val2;
                else
                    return (float) (val1*1.0/val2);
            }
        }
    123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121

上面的例子支持多位数的加减运算，且支持小数。其中，用到的**LinkStack**类就是本文章上面实现的链式栈。使用示例：

System.out.println(CalculateMathExpression.calcExpressionValue("10.2+((2+3)*4)-5"));
    1

输出结果为：

输入的中缀表达式转换成后缀表达式为：10.2 2 3 + 4 * + 5 - 
    25.2
    12

## 3.2 队列 ##

### 3.2.1 队列的定义 ###

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。是一种**先进先出**的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。

### 3.2.2 队列的实现 ###

同理，队列的实现方式也有顺序表和链表两种方式。

*  顺序表：用顺序表实现队列，就是用一个数组和一个指针来实现。每次入队的时插入到数组尾，出队的时将数组第一个元素移除，然后后面的元素整体后移。但是这样效率很低，为了提高效率，可以设置两个指针，一个指针front指向队头，一个指针rear指向队尾，这样**队头就不一定在数组下标为0的位置了**。使用此种方式时，应该解决**假溢出**的问题。解决假溢出的方式是使用循环队列，即当队尾满了时，插入到队头。  
    **循环队列**当队空和队满时，都是front和rear相等，为了解决此问题，当队满时，我们留一个元素。如下所示：  
    ![循环队列][55aff0b26b75e0fb3df968d129596944.png]  
    此时，  
    **队满的条件为**：  
    (rear+1)%QueueSize==front  
    **计算队长的公式为**：  
    (rear-front+QueueSize)%QueueSize
 *  **链式结构**  
    队列的链式存储结构，就是在链表的基础上，限制数据的插入和弹出：将链表头部当成队首，尾部当成队尾。因为经常需要在队尾进行入队操作，为了减少链表的遍历次数，提高性能，此处我们的队列的**Java代码实现基于双向循环链表实现，而C++结构则基于单链表实现（C++的双向循环链表太懒了没实现，只能用单链表了hhh）**。有关双向循环链表的实现，见[上一篇博客][Link 1]。具体实现如下：
 *  **Java实现**

public class LinkQueue<T> extends DoublyLinkedList<T> { 
        /** * 入队操作 * @param data */
        public void enQueue(T data){ 
            insert(this.length,data);
        }
    
        /** * 出队操作 * @return */
        public T deQueue(){ 
            if (!isEmpty())
                return remove(0);
            return null;
        }
    
        /** * 判断队列是否为空 * @return 空返回true，非空返回false */
        public boolean isEmpty(){ 
            return this.length==0;
        }
    }
    123456789101112131415161718192021222324252627

其中，DoublyLinkedList双向循环链表的实现见[上一篇博客][Link 1]。使用示例如下：

LinkQueue<String> queue=new LinkQueue<>();
            queue.enQueue("0");
            queue.enQueue("1");
            queue.enQueue("2");
            System.out.println(queue);
            System.out.println(queue.deQueue());
            System.out.println(queue.deQueue());
            System.out.println(queue.deQueue());
    12345678

输出结果为：

0,1,2,
    0
    1
    2
    1234

*  **C++实现**

template<class T>
    class LinkQueue:LinkList<T>
    { 
    public:
    	/** * 入队操作 */
    	void enQueue(T data)
    	{ 
    		insert(length, data);
    	}
    
    	/** * 出队操作 */
    	T deQueue()
    	{ 
    		if (!isEmpty())
    		{ 
    			return this->remove(0);
    		}
    		return NULL;
    	}
    
    	bool isEmpty()
    	{ 
    		return this->length == 0;
    	}
    };
    1234567891011121314151617181920212223242526272829

同理，LinkList的定义见[上一篇博客][Link 1]。此处因为使用的是单链表，频繁出队入队的话，效率应该不是很高。使用示例如下：

LinkQueue<string> queue;
    	queue.enQueue("0");
    	queue.enQueue("1");
    	queue.enQueue("2");
    	cout << queue.deQueue() << endl;
    	cout << queue.deQueue() << endl;
    	cout << queue.deQueue() << endl;
    1234567

输出结果为：

0
    1
    2
    123

### 3.2.2 队列的应用 ###

队列也有很多应用，比如各种排队系统，特别是在网络请求的时候，当有多个请求任务时，不能一下子全部请求，需要排队请求。还有就是树的层次遍历中会用到队列，这个等写到树的时候再详细介绍。

## 3. 3 应用 ##

### 3.3.1 表达式 ###

> 表达式一般分为前缀表达式，中缀表达式和后缀表达式。
> 
> 其中我们最为熟悉的是中缀表达式，也就是书本上最常用的表示形式。中缀表达式是将运算符放在两个操作数的中间。

#### 语言表示1–中缀转后缀 ####

> **1.从左到右进行遍历**  
> **2.运算数**,直接输出.  
> **3.左括号**,直接压入堆栈,(括号是最高优先级,无需比较)(**入栈后优先级降到最低**,确保其他符号正常入栈)  
> **4.右括号**,(意味着括号已结束)不断弹出栈顶运算符并输出直到遇到左括号(弹出但不输出)  
> **5.运算符**,将该运算符与栈顶运算符**进行比较**,  
> 如果**优先级高于栈顶运算符**则压入堆栈(该部分运算还不能进行),  
> 如果**优先级低于等于栈顶运算符**则将栈顶运算符弹出并输出,然后比较新的栈顶运算符.  
> (低于弹出意味着前面部分可以运算,先输出的一定是高优先级运算符,等于弹出是因为同等优先级,从左到右运算)  
> 直到优先级大于栈顶运算符或者栈空,再将该运算符入栈.  
> **6.如果对象处理完毕**,则按顺序弹出并输出栈中所有运算符.

#### 语言表述2–中缀转后缀 ####

> 如何将中缀转后缀思路： 假如表达式是一个字符串
> 
> 创建一个符号栈和一个字符串队列
> 
> 遍历各个字符信息
> 
> 判断该字符是 运算符、括号、数值
> 
>  *  **运算符**
>     
>     判断当前字符优先级是否小于等于栈顶字符优先级，此时栈顶元素中的左括号(，优先级最小
>     
>      *  小于等于 将符号栈栈顶内容弹出且存入到字符串队列中,将当前字符存入到符号栈中
>      *  大于将当前字符存入到符号栈中
>  *  **括号**
>     
>      *  左括号存入到符号栈中
>      *  右括号 依次将符号栈中的运算符弹出进入到字符串队列中直到在符号栈中弹出出现左括号停止弹栈 数值 直接进入到字符串队列中
>  *  **数值**
>     
>     直接输出
> 
> 遍历结束后 判断符号栈中是否有元素

#### 优先级 ####

#### 代码–中缀转后缀 ####

#include <iostream>
    #include <algorithm>
    #include <queue>
    #include <set>
    #include <stack>
    #include <string>
    #include <vector>
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    using namespace std;
    #define MAX 1000
    char *change(char data[]);
    bool compare(char a, char b);
    int priority(char a);
    // (40  括号在算术上优先级最高，但是在 栈的优先级是最低的，为了其他符号正常入栈 优先级最低
    //  /* 优先级最高 , +- 优先级最低
    
    // true 的情况 只有a 是*/ b是+-的情况
    int priority(char a)
    {
        if (a == '(')
        {
            return  0;
        }
        else if (a == '+' || a == '-')
        {
            return  1;
        }
        else
        {
            return  2;
        }
    }
    // 比较优先级 ,a 的优先级比b 高，就返回true
    bool compare(char a, char b)
    {
        return  priority(a) > priority(b);
    }
    // 中缀表达式--> 后缀表达式(逆波兰表达式)
    // 返回字符串数组
    char *change(char data[])
    {
    
        char *hou = (char *)malloc(MAX * sizeof(char));
        stack<char> s;
        int index = 0; // 后缀表达式的长度
        int length = strlen(data);
        // 1. 判断类型
        for (int i = 0; i < length; i++)
        {
            // 如果是运算数，直接输出，
            if (data[i] >= '0' && data[i] <= '9')
            {
                hou[index] = data[i];
                index++;
            }
            else if (data[i] == ')')
            {
                // 不断的弹出栈元素并输出直到遇到左括号结束
                while (!s.empty() && s.top() != '(')
                {
                    hou[index] = s.top();
                    index++;
                    s.pop();
                }
                s.pop(); //退出左括号
            }else if(data[i]=='('){
                 s.push(data[i]);
            }
            else
            {
                // 表示 运算符优先级小于等于 栈顶元素,就退出栈顶元素，并输出
                // 包含情况data[i]='(',compare 返回false
                
                while (!s.empty() && !compare(data[i], s.top()))
                {
                    printf("%c %c %d\n",data[i],s.top(),compare(data[i], s.top()));
                    hou[index] = s.top();
                    index++;
                    s.pop();
                }
                s.push(data[i]);
            }
            printf("此时输出内容 %-20s \t参加运算的符号 %c  \t\t栈的元素个数%d \n", hou, data[i], s.size());
        }
    
        // 输出栈内所有元素
        while (!s.empty())
        {
            hou[index] = s.top();
            index++;
            s.pop();
        }
        return  hou;
    }
    
    // 后缀表达式的计算
    int main(int argc, char const *argv[])
    {
        // 样例 2*(9+6/3-5)+4
        // 结果 2963/+5-*4+
        char s[MAX] = "2*2*2*2+2";
        char *result;
        result = change(s);
        printf("%s\n", result);
        return  0;
    }

![981a62762b56ffef583f69aed27ec327.png][]

[Link 1]: https://blog.csdn.net/qq_31709249/article/details/102964210
[55aff0b26b75e0fb3df968d129596944.png]: /images/20221120/d229940aeab5413c818eb2579a129551.png
[981a62762b56ffef583f69aed27ec327.png]: /images/20221120/242fec15ad5e4f559d5d6e186bf5afe2.png