欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言数据结构基础学习笔记——栈和队列

程序员文章站 2022-04-09 18:52:50
之前我们学过了普通的线性表,接下来我们来了解一下两种特殊的线性表——栈和队列。 栈是只允许在一端进行插入或删除的线性表。 栈的顺序存储结构也叫作顺序栈,对于栈顶指针top,当栈为空栈时,top=-1;当栈为满栈时,top=MaxSize-1。顺序栈的定义为: 顺序栈的入栈操作为: 顺序栈的出栈操作为 ......

之前我们学过了普通的线性表,接下来我们来了解一下两种特殊的线性表——栈和队列。

栈是只允许在一端进行插入或删除的线性表。

栈的顺序存储结构也叫作顺序栈,对于栈顶指针top,当栈为空栈时,top=-1;当栈为满栈时,top=maxsize-1。顺序栈的定义为:

#define maxsize 50                            //定义栈中元素的最大个数 
typedef struct{                                
    elemtype data[maxsize];                   //存放栈中元素 
    int top;                                  //栈顶指针 
}sqstack;                                     //顺序栈的简写

顺序栈的入栈操作为:

bool push(sqstack &s,elemtype x){
    if(s.top==maxsize-1) return false;
    s.data[++s.top]=x; return true;
} 

顺序栈的出栈操作为:

bool pop(sqstack &s,elemtype &x){
    if(s.top==-1) return false;
    x=s.data[s.top--];      
    return true;
} 

顺序栈读取栈顶元素为:

bool gettop(sqstack s,elemtype &x){
    if(s.top==-1) return false;
    x=s.data[s.top];
    return true;
} 

顺序栈读取栈顶元素与出栈操作对比,注意读取栈顶元素时栈顶指针没有自减。

对于一个数组,如果只从数组头部开始入栈,并没有达到很高的空间利用率,因此我们引入共享栈的概念。共享栈是两个栈共用同一个数组,分别从数组头部和数组尾部开始开始入栈。其定义为:

#define maxsize 100                            //定义栈中元素的最大个数 
typedef struct{                                
    elemtype data[maxsize];                    //存放栈中元素 
    int top1;                                  //栈1顶指针 
    int top2;                                  //栈2顶指针 
}sqdoublestack;                                //共享栈的简写
bool push(sqstack &s,elemtype x,int stacknum){
    if(s.top1+1==s.top2) return false;
    if(stacknum==1) s.data[++s.top1]=x; 
    else if(stacknum==2) s.data[--s.top2]=x;
    return true;
} 

共享栈的满栈条件是top1+1=top2。

同时,栈也有链式存储结构,叫作链栈,它空栈时top=null,一般不会满栈。链栈的定义为:

typedef struct snode{                
    elemtype data;                     //数据域
    struct snode *next;                //指针域 
}snode,*slink;                         //链式栈的结点
typedef struct linkstack{
    slink top;                         //栈顶指针 
    int count;                         //链式栈结点数 
}linkstack; 

栈有着丰富的应用场景,比较经典的题目有括号的匹配以及后缀表达式的求值。

①括号的匹配:给你一串杂乱的大,中,小括号的序列,让你判断这里的括号序列满不满足数学计算的规律(括号套括号)。主要思路是将所有的左括号依次入栈,碰到右括号出栈匹配,若是不同种的括号返回false,若是同一种括号则继续以上操作,直到空栈并且数组中的字符串遍历完成,返回true。

②后缀表达式的计算:后缀表达式是计算机最喜欢的一种表达式方式,例如(5+10+1*13)/14这个中缀表达式,它的后缀表达式为5 10 + 1 13 * + 14 /,其将每一步计算的运算符号置后。利用栈计算后缀表达式的主要思路是:①将数字5入栈,再将数字10入栈;②当指针碰到运算符+时,将栈中的前两个元素出栈进行计算(后出栈的数在前位),结果入栈,如本例值15入栈;③同上一步,计算1*13得13入栈,此时栈底值15,栈顶值13;④同上一步,指针碰到运算符+,将15与13求和,得值28入栈;⑤再同上一步,计算28/14=2入栈;⑥此时字符串数组遍历完毕,栈中的唯一值2则为表达式的结果。

栈思想的最重要的一个应用便是递归,递归是指在一个函数、过程或数据结构中的定义中又应用了它自身的编程思想。理解递归的一个基础方法便是找到递归式和递归边界,我们来看两个例子:

①用递归求n的阶乘:

int f(int n){
    if(n==0) return 1;                //递归边界 
    else return n*f(n-1);             //递归式 
} 

②求斐波那契数列的第n项:

int fib(int n){
    if(n==0) return 0;                 //递归边界
    else if(n==1) return 1;            //递归边界
    else return fib(n-1)+fib(n-2);     //递归式 
}

递归式是每一次递归过程的计算核心,而递归边界就是每一次递归的结束标志。

另一种特殊的线性表是队列,队列的定义是只允许在一端进行插入,而在另一端进行删除的线性表。

队列的顺序存储结构是顺序队列,其定义为:

#define maxsize 50                             //定义队列中元素的最大个数 
typedef struct{                                
    elemtype data[maxsize];                    //存放队列中元素 
    int front,rear;                            //队头指针和队尾指针 
}sqqueue;         

但对于一个数组队列来说,每一次入队和出队都会浪费一个数组位置,于是我们引入循环队列的概念,队尾指针rear在指到队尾后会回到下标为0的位置(利用取余来实现),即每一次rear和front的更新基于以下操作:rear=(rear+1)%maxsize,front=(front+1)%maxsize。

但是这样又产生了新的问题,rear=front到底是队空还是队满无法判断。这样的问题有以下两种解决办法:①设一个frag,作为标志位,当队满时frag=1;②牺牲一个数组位置,保留一个空余单元,此时队满的判断标准变成了(rear+1)%maxsize=front,队列中的元素数计算方法为:(rear-front+maxsize)%maxsize。

循环队列的入队操作为:

bool enqueue(sqqueue &q,elemtype x){
    if((q.rear+1)%maxsize==q.front) return false;    //队满
    q.data[q.rear]=x;
    q.rear=(q.rear+1)%maxsize;
    return true; 
} 

循环队列的出队操作为:

bool dequeue(sqqueue &q,elemtype &x){
    if(q.rear==q.front) return false;     //队空
    x=q.data[q.front];
    q.front=(q.front+1)%maxsize;
    return true;
} 

队列链式存储的定义为:

typedef struct{                
    elemtype data;                    //数据域
    struct linknode *next;            //指针域 
}linknode;                            //链式队列的结点
typedef struct{
    linknode *front,*rear;            //队头和队尾指针 
}linkqueue;

链式队列的入队和出队类似于链表的相应操作。