数据结构学习笔记（2）——栈与队列

墨蓝 2022-10-11 03:42 242阅读 0赞

# 栈与队列 #

## 结构体定义 ##

1.  顺序栈定义

typedef struct{
        
        int data[maxSize];
        int top;
    }SqStack;

1.  链栈结点定义

typedef struct LNode{
        
        int data;
        struct LNode *next;
    }LNode;

1.  顺序队列定义

typedef struct{
        
        int data[maxSize];
        int front;
        int rear;
    }SqQueue;

1.  链队定义

![在这里插入图片描述][20210703204401512.png]

//队结点类型定义
    typedef struct QNode{
        
        int data;
        struct QNode *next;
    }QNode;

//链队类型定义
    typedef struct{
        
        QNode *front;
        QNode *rear;
    }LiQueue;

## 栈的应用 ##

### 顺序栈的应用 ###

1.  C语言里算术表达式中的括号只有小括号。编写算法，判断一 个表达式中的括号是否正确配对，表达式已经存入字符数组a\[\]中，表达式中的字符个数为n。

> 分析：遍历算数表达式的字符数组，遇到左括号就入栈，遇到右括号就出栈。如果遍历完后栈非空或者出栈时发现栈空，则说明不匹配。

int match(char a[],int n){
        
        //初始化栈,规定top为-1时栈空
        char stack[maxsize];
        int top=-1;
        //遍历数组
        for(int i=0;i<n;++i){
        
            //碰到左括号就入栈
            if(a[i]=='(')	stack[++top]='(';
            //碰到右括号就出栈
            if(a[i]==')'){
        
                //出栈时栈空就说明不匹配
                if(top==-1){
        
                    return 0;
                }else{
        
                    top--;	//出栈
                }
            }	
        }
        //遍历结束，栈空，则说明左括号和右括号数目相等
        if(top==-1){
        
            return 1;
        }else{
        
            return 0;
        }
    }

思考：什么样的问题适合用栈解决？

答：在解决问题的过程中，如果碰到一个子问题，根据现有的条件没有办法解决，就可以先把它记下来，等到以后可以解决时再返回来解决。**栈具有记忆的功能，这是其FILO（先进后出）的特性决定的**。

1.  前缀表达式、中缀表达式、后缀表达式

> 1.中缀表达式就是常见的运算表达式，如 (3+4)×5-6
> 
> 2.**前缀表达式**又称波兰式，前缀表达式的运算符位于操作数之前 比如:**- × + 3 4 5 6**
> 
> 前缀表达式的计算机求值：**从右至左**扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（**栈顶元素 op 次顶元素**），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
> 
> 3.**后缀表达式**又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后
> 
> 后缀表达式计算机求值：与前缀表达式类似，只是顺序是**从左至右**，比如**3 4 + 5 × 6 -**

编写一 个函数，求后缀式的数值，其中后缀式存于一 个字符数组a中，a中最后一 个字符为"\\0", 作为结束符，并且假设后缀式中的数字都只有一 位。本题中所出现的除法运算，皆为整除运算，如2/3结果为0、3/2结果为1。

> 分析：从左到右扫描a，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数（连续出栈两次），用运算符对它们做相应的计算（**次顶元素 op 栈顶元素** ），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

//op函数用来运算：栈顶元素a Op 次顶元素b
    int op(int a,char Op,int b){
        
        if(Op=='+') return a+b;
        if(Op=='-') return a-b;
        if(Op=='*') return a*b;
        if(Op=='/'){
        
            //除数为0，输入错误
            if(b==0){
        
                printf("error\n");
                return 0;
            }else 
                return a/b;
        }
    }
    //后缀式计算
    int com(char a[]){
        
        //a,b为每次运算时的数字，c用来保存结果
        int a,b,c;	
        // 注意元素类型必须为整型，不能为char型，虽然操作数只有一位，但是在运算的过程中会产生多位数
        int stack[maxSize];	//初始化栈
        int top=-1;
        //从左往右遍历数组，遇到'\0'时结束
        for(int i=0;a[i]!='\0';i++){
        
            //字符是数字，入栈
            if( a[i]>='0' && a[i]<=9){
        
                //a[i]-'0'将字符型转换为整型
                stack[++top]=a[i]-'0';
            //字符是运算符号，连续出栈两次并计算
            }else{
        
            	//注意第二个在入栈时后入栈，即栈顶元素是第二个操作数，次顶元素是第一个操作数
                b=stack[top--];
                a=stack[top--];
                //运算并将结果入栈
                c=op(a,a[i],b)
                stack[++top]=c;
            }
        }
    }

*  **0~9**的整型a和字符型的相互转换，比如：

`char b='5'; int a=b-'0';`那么此时`a=5;`;  
`int a=1 ; char b=a+'0';`那么此时`b='1';`

### 链栈的应用 ###

用不带头结点的单链表存储链栈，设计初始化栈，判空，进出栈等算法。

1.  初始化

void initStack(LNode *&lst){
        
        lst = NULL;
    }

1.  判空

int isEmpty(LNode *lst){
        
        if(lst==NULL) return 1;
        else return 0;
    }

1.  进栈

void push(LNode *&lst,int x){
        
        //申请新的结点空间并赋值
        LNode *p=(LNode*)malloc(sizeod(LNode));
        p->next=NULL;
        p->data=x;
        //头插法插入无头结点的链表
        p->next=lst;
        lst=p;
    }

1.  出栈

//出栈，用x记录其值
    int pop(LNode *&lst,int &x){
        
        if(lst==NULL) return 0;
        LNode *p=lst;
        x=p->data;
        lst=p->next;
        free(p);
        return 1;
    }

## 顺序队与循环队列 ##

*  顺序队列的结构体定义

typedef struct{
        
        int data[maxSize];
        int front;
        int rear;
    }SqQueue;

1.  循环队列的由来
    
    > 在顺序队中，通常让**队尾指针rear指向刚进队的元素位置**，让**队首指针front指向刚出队的元素位置**。因此，元素进队的时候，rear要向后移动；元素出队的时候，front也要向后移动。这样经过一 系列的出队和进队操作以后，两个指针最终会达到数组末端maxSize-1处。虽然队中已经没有元素，但仍然无法让元素进队，这就是所谓的“**假溢出**“。要解决这个问题，可以把数组弄成一 个环，让 rear和 front沿着环走，这样就永远不会出现两者来到数组尽头无法继续往下走的情况，这样就产生了循环队列。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjM4MTQy_size_16_color_FFFFFF_t_70]

（1）**front指向队首元素的前一个位置**（上一此出队的元素位置）；

**rear指向队尾元素**。指针的移动：

*  出队，移动队首指针：`front=(front+1)%maxSize`（maxSize是数组长度）
 *  入队，移动队尾指针：`rear=(rear+1)% maxSize`

（2）队空：`qu.rear==qu.front`

（3）队满：`(qu.rear+1)%maxSize==qu.front`（循环队列必须损失一个存储空间，用来区分队空与队满）

如果不想损失存储空间，可另外设置一个t

（4）x入队：

qu.rear=(qu.rear+1)% maxSize;
    qu.data[qu.rear]=x;

（5）x出队：

qu.front=(qu.front+1)% maxSize;
    x=qu.data[qu.front];

（6）元素个数：`(rear - front + maxSize) % maxSize`

1.  循环队列初始化
    
        void initQueue(SqQueue &qu){
              
        	qu.front=qu.rear=0;
        }
2.  循环队列的判空
    
        int isQueueEmpty(SqQueue qu){
              
            if(qu.front==qu.rear){
              	//循环队列的判空条件：首尾指针重合
                return 1;
            }else{
              
                return 0;
            }
        }
3.  循环队列的进队算法
    
        int enQueue(SqQueue &qu,int x){
              
            if((qu.rear+1)%maxSize==qu.front) //队满
                return 0;
            //队未满，先动指针再存值
            qu.rear=(qu.rear+1)% maxSize;
        	qu.data[qu.rear]=x;
        }
4.  循环队列的进队算法
    
        int deQueue(SqQueue &qu,int &x){
              
            if(qu.rear==qu.front) //队空
                return 0;
             //队非空，先动指针再取值
            qu.front=(qu.front+1)% maxSize;
        	x=qu.data[qu.front];	
            return 1;
        }

（2）循环队列补充知识点

1.  当从队尾插入新元素以及从对头删除新元素时，我们都知道对应的rear与front是顺时针转的，对应的语句是：
    
    `q.rear=(q.rear+1)%maxSize`或者`q.front=(q.front+1)%maxSize`；
    
    如果我们规定队首也可以插入新元素，队尾也可以删除元素，那么对应的front和rear就是逆时针转的，这个时候对应的语句就应该是：
    
    `q.rear=(q.rear-1+maxSize)%maxSize`或者`q.front=(q.front-1+maxSize)%maxSize`。
    
    二者的效果刚好相反，这是关于循环队列最重要的语句。
2.  上面提到，要想分辨队空还是队满，我们需要损失一个存储空间，使得队空与队满得以分清：
    
    队空：`qu.rear==qu.front`
    
    队满：`(qu.rear+1)%maxSize==qu.front`
    
    这是因为仅仅依靠`q.rear==q.front`我们无法判断队空和队满，主要原因是我们没法判断最后一次操作时到底是入队还是出队。如果最后一次操作是入队，那么当rear和front重合时，必然是队满，反之队空。对此，可以设立一个tag，当`q.rear==q.front`时，规定tag为0时为队空，tag为1时为队满。tag初始值为0，每次入队时，我们就把tag设为1，每次出队时就把tag设为0，这样就可以在不损失存储空间的情况下来判断队空和队满了。
    
    队空：`qu.rear==qu.front && tag==0`
    
    队满：`qu.rear==qu.front && tag==1`

## 链队 ##

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LAxeT1NB-1624983506505)(C:\\Users\\76583\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210625234951443.png)\]

//队结点类型定义
    typedef struct QNode{
        
        int data;
        struct QNode *next;
    }QNode;

//链队类型定义
    typedef struct{
        
        QNode *front;
        QNode *rear;
    }LiQueue;

*  队空：`lqu->rear==NULL`或`lqu->front==NULL`
 *  队满：在内存无限大情况下不存在队满的情况
 *  元素进队：
    
        lqu->rear->next=p;
        lqu->rear=p;
 *  元素出队：
    
        p=lqu->front;
        lqu->front=p->next;
        x=p->data;
        free(p);

1.  链队的初始化算法

void initQueue(LiQueue *&lqu){
        
        lqu=(LiQueue*)malloc(sizeof(QNode));
        lqu->front=lqu->rear=NULL;
    }

1.  链队的判空算法

void isQueueEmpty(LiQueue *lqu){
        
        if(lqu->rear==NULL||lqu->front==NULL)
            return 1;
        else
            return 0;
    }

1.  链队的入队算法

void enQueue(LiQueue *lqu,int x){
        
        QNode *p=(QNode*)malloc(sizeof(QNode));
        p->data=x;
        p->next=NULL;
        if(lqu->rear==NULL){
        	//入队时，如果队空，需要特殊处理
            luq->front=lqu->rear=p;
        }else{
        
            lqu->rear->next=p;
            lqu->rear=p;
        }
        
    }

1.  链队的出队算法

void deQueue(LiQueue *lqu,int x){
        
        if(lqu->rear==NULL) return 0;
        QNode *p=lqu->front;
        if(lqu->front==lqu->rear){
        	//出队时如果队中只剩一个元素，需要特殊处理
            lqu->front=lqu->rear=NULL;
        }else{
        
            luq->front=p->next;
            x=p->data;
            free(p);
            return 1;
        }
    }

## 共享栈与双端队列 ##

1.  共享栈
    
    为了提高内存空间的利用率、减少溢出的可能性，使用两个栈共享一片连续的内存空间，则这两个栈的栈底分别位于存储空间的两端（因为顺序栈的栈底是不会变的），那么两个栈的栈顶则一定位于存储空间内，当两栈顶相遇时，则说明存储空间已满。
2.  双端队列
    
    双端队列是一种插入和删除操作在两端均可以进行的线性表。可以把它看做是栈底连在一起的两个栈，两个栈顶则向两端延伸。

### 共享栈的实现 ###

共享栈的初始状态：规定s0的栈底在左侧`0`处，s1的栈底在右侧`(maxSize-1)`处，栈顶在`0~maxSize-1`之间变动；

s0栈顶的初始值为-1，s1栈顶的初始值为maxSize，栈内元素个数0；top\[0\]为s0栈顶，top\[1\]s1栈顶；

当s0栈顶与s1栈顶相遇时，栈满：`top[0]+1==top[1]`；栈空：`top[0]==-1 && top[1]==maxSize`。

//共享栈的结构体定义
    typedef struct{
        
        int elem[maxSize];
        int top[2];	//top[0]为s0栈顶，top[1]s1栈顶
    }SqStack;

//入栈
    int push(SqStack &st,int stNo,int x){
        	//stNo表示入栈的编号，x是要入栈的值
        if(st.top[0]+1<st.top[2]){
        	//先判断是否栈满
            if(stNo==0){
        	//从栈顶s0处入栈
                ++(st.top[0]);
                st.elem[st.top[0]]=x;
                return 1;
            }else if(stNo==1){
        	//从栈顶s1处入栈,注意此处入栈栈顶是自减，因为它的栈底是在右侧
                --(st.top[1]);
                st.elem[st.top[1]]=x;
                return 1;
            }else
                return -1;	//stNo的值不是0、1，输入错误
        }else
            return 0;	//栈满，插入失败
    }

//出栈
    int pop(SqStack &st,int stNo,int &x){
        
        if(stNo==0){
        
            if(st.top[0]!=-1){
        	//st0不为空，可以出栈
                x=st.elem[st.top[0]];
                --(st.top[0]);
                return 1;
            }else return 0;//st0为空，出栈失败
        }else if(stNo==1){
        
            if(st.top[1]!=maxSize){
        	//st1不为空，可以出栈
                x=st.elem[top[1]];
                ++(st.top[1]);
                return 1;
            }else 
                return 0;//st1为空，出栈失败
        }else 
            return -1;//stNo不为0、1，输入错误

### 用两个栈模拟队列 ###

栈的特点是后进先出，队列的特点是先进先出。所以，当用两个栈s1和s2模拟一个队列时，s1作为输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中， s1中最先入栈的元素在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。只有栈s2为空且s1也为空时，才算是队列空。

*  入队

//入队，将新元素x压入s1
    int enQueue(SqStack &s1, SqStack &s2, int x) {
        
    	int y;	//临时变量，用来在s1和s2之间传值 
    	//如果s1不是满的，直接把元素压入即可
    	if (s1.top != maxSize - 1) {
        
    		push(s1, x);
    		return 1;
    	}
    	//s1满，可以尝试把元素放到s2中，再从s1入栈，不过要先判断s2中是否还有剩余的未pop的元素
    	else {
        
            //这里要尤其注意：
            //s1满，s2非空，此时不能入栈，必须要等s2中的元素都出栈，才能继续往s2中压入新元素
            //此时就是队满的状态，虽然s2中还有剩余的存储空间
            //此时如果将s1中的元素压入s2，则后进的元素反而跑到先进的元素前面出，这就不符合先进先出的原则
    		if (!isEmpty(s2)) {
        
    			return 0;
    		}
            //只有在s1满，s2空的情况下，才能把s1元素压入s2中
    		else if (isEmpty(s2)) {
        	
                //s1出栈，s2入栈，直到s1空，s2满
                //最先入s1的元素此时在s2的栈顶
    			while (!isEmpty(s1)) {
        
    				pop(s1, y);
    				push(s2, y);
    			}
    			//到这里，s2此时是栈满的状态，s1此时是栈空的状态
    			//把新元素压入s1
    			push(s1, y);
    			return 1;
    		}
        }	
    }

*  出队

//出队，s2的栈顶元素退栈，x接收出队元素
    int deQueue(SqStack &s2, SqStack &s1, int x) {
        
    	int y;
    	//如果s2非空，直接出栈
    	if (!isEmpty(s2)) {
        
    		pop(s2, x);
    		return 1;
    	}
        //如果s2是空的，就将s1中的所有元素挨个出栈再压入到s2中
    	else {
        	
            //s2空，s1空，则队空，出队失败
    		if (isEmpty(s1)) {
        
    			return 0;
    		}
    		else {
        
                //s2空，s1非空，s1出栈，s2入栈，直到s1空，此时s2不一定是满的,这取决于s1中转移前的元素个数
    			while (!isEmpty(s1)) {
        
    				pop(s1, y);
    				push(s2, y);
    			}
    			//此时s1是空的，最先入s1的元素此时在s2的栈顶，出栈
    			pop(s2, x);
    			return 1;
    		}
    	}
    }

*  判空

int isQueueEmpty(SqStack s1, SqStack s2) {
        
        //s1和s2都为空，则队空
    	if (isEmpty(s1) && isEmpty(s2)) return 1;
    	else return 0;
    }

*  队满

int isQueueFull(SqStack s1, SqStack s2) {
        
        //s1满，去看s2
    	if (s1.top == maxSize - 1) {
        
            //s1满，s2非空，则队满（因为此时不能将s1中的元素压入s2来腾出空间给新元素）
    		if (!isEmpty(s2))return 1;
            //s1满，s2空，则队未满
    		else return 0;
    	}
        //s1未满，则队未满
    	else
    		return 0;
    }

## 十进制转化二进制 ##

1.  编写一个算法，将一个非负的十进制整数N转换为一个二进制数。

分析：十进制转换二进制，方法是"除2取余，逆序排列"，这里可以使用栈来解决。

int baseTrans(int N) {
        
    	int result = 0;
    	int stack[maxSize];
    	int top = -1;
    	int i;
    	while (N!=0)
    	{
        
    		i = N % 2;	//N除以2取余得到二进制数，入栈
    		N = N / 2;	//N自身除以2取整，准备下一次运算
    		stack[++top] = i;
    	}
    	while (top!=-1)
    	{
        	
    		//出栈，将得到的余数逆序输出
    		i = stack[top--];
    		result = result * 10 + i;
    	}
    }

[20210703204401512.png]: /images/20221005/db16dc98c12d43678313afd419fb4965.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjM4MTQy_size_16_color_FFFFFF_t_70]: /images/20221005/9a2012ca96944b09aa6eeb072f13f992.png