Uncategorized

数据结构——栈与队列

栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表

我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。

首先栈是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指栈顶,而不是栈底。

它的特殊之处就在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。这也就使得:栈底是固定的,最先进栈的只能在栈底。

栈的插入操作,叫做进栈,也称压栈,入栈。

栈的删除操作,叫做出栈,也有的叫做弹栈。

进栈出栈变化形式

最先进栈的元素,是不是就只能是最后出栈呢?

答案显然是不一定的,因为栈对元素进出的时间没有进行限制。

1,2,3依次进栈,有多少可能呢?

321,123,213,132,231

那么有没有可能312呢?

肯定不会,因为3先出栈,就意味着,3曾经进栈,既然3已经进栈了,那么1和2也已经进栈了,此时,2一定是在1的上面,那么只有可能是321.

栈的抽象数据类型

对于栈来讲,线性表的操作它都具备,但由于特殊性,所以操作也会有所变化。特别是插入和删除操作,我们改名为push和pop,一般叫进栈和出栈。

ADT 栈(stack)
Data
	同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。
Operation
	InitStack(*S):初始化操作,建立一个空栈S
	DestroyStack(*S):若栈存在,则销毁它
	ClearStack(*S):将栈清空
	StackEmpty(s):若栈为空,返回true,否则返回false
	GetTop(S,*e):若栈存在且非空,用e返回S的栈顶元素
	Push(*S,e):若栈S存在,插入新元素e到栈S中并成为栈顶元素
	Pop(*S,e):删除栈S中栈顶元素,并用e返回其值
	StackLength(S):返回栈S的元素个数
endADT

栈本身就是一个线性表,所以线性表的顺序存储和链式存储,对于栈来说,同样适用。

栈的顺序存储结构及实现

栈的顺序存储结构

我们通常将下标为0的一端作为栈底,因为首元素都存在栈底,变化最小,所以让它作栈底。我们定义一个top变量来指示栈顶元素在数组中的元素,若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时,top等于0。通常把空栈的判定条件定为top = -1。

typedef int SElemType;  /*SElemType类型根据实际情况而定,这里假设为int*/
typedef struct
{
    SElemType data[MAXSIZE];
    int top;  /*用于栈顶指针*/
}SqStack;

若现在有一个栈,栈有两个元素,top=1;空栈,top=-1;栈满,top=4

进栈操作

/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S,SElemType e)
{
    if(S->top==MAXSIZE-1)  /*栈满*/
        return ERROR;
    S->top++;			/*栈顶指针增加一*/
    S->data[S->top]=e;  /*将新插入元素赋值给栈顶空间*/
    return OK;
}

出栈操作

/*若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR*/
Status Pop(SqStack *S, SElemType *e)
{
    if(S->top==-1)
        return ERROR;
    *e = S->data[S->top];		/*将要删除的栈顶元素赋值给e*/
    S->top--;		/*栈顶指针减一*/
    return OK;
}

两栈共享空间

栈只准栈顶进出元素,所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷,就是必须事先确定数组存储空间大小。如果我们有两个相同类型的栈,我们为它们各自开辟了数组空间,极有可能时第一个栈已经满了,再进栈就溢出了,而另一个栈还有很多存储空间空闲。所以我们可以用一个数组来存储两个栈。

数组有两个端点,两个栈有两个栈底,让一个栈的栈底为数组的始端,即下标为0处,另一个栈为栈的末端,即下标为数组长度n-1处。这样,两个栈如果增加元素,就是两端点向中间延伸。

top1和top2是栈1和栈2的栈顶指针,只要它们俩不见面,两个栈就可以一直使用。

栈1为空时,top1=-1,栈2为空时,top2=n

当两个栈见面之时,也就是两个指针之间相差为1时,即top+1==top2为栈满。

两栈共享空间结构代码如下:

/*两栈共享空间结构*/
typedef struct
{
    SElemType data[MAXSIZE];
    int top1;
    int top2;
}SqDoubleStack;

对于两栈共享空间的push方法,我们除了要插入元素值参数之外,还需要有一个判断是栈1还是栈2的栈号参数stackNumber。

/*插入元素e为新的栈顶元素*/
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
    if(S->top1+1==S->top2)  /*栈已满,不能再push新元素了*/
        return ERROR;
    if(StackNumber==1)  /*栈1有元素进栈*/
        S->data[++S->top1]=e;
    else if(StackNumber==2)
        S->data[--S->top2]=e;
    return OK;
}

对于两栈共享空间的pop方法,参数就只是判断栈1栈2的参数StackNumber;

Status Pop(SqDoubleStack *S,SElemType *e,int StackNumber)
{
    if(StackNumber ==1)
    {
        if(S->=top1==-1)
            return ERROR
        *e = S->data[S->top1--]; /*将栈1的栈顶元素出栈*/
    }
    else if(stackNumber ==2)
    {
        if(S->top2==MAXSIZE)
            return ERROR;
        *e = S->data[S->top2++]
    }
    return OK;
}

栈的链式存储结构及其实现

栈的链式存储结构

栈的链式存储结构,又称为链栈。

通常把栈顶放在单链表的头部,通常对于栈链来说,是不需要头结点的。

typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

进栈操作

假设元素值为e的新结点是s,top为栈顶指针

/*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S,SElemType e)
{
    LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
    s->data = e;
    s->next = S->top;  /*将当前的栈顶元素赋值给新结点的直接后继*/
    S->top =s;       /*将新的结点s赋值给栈顶指针*/
    s->count++;
    return OK;
}

出栈操作

假设变量p用来存储要删除的栈顶结点,将栈顶指针下移一位,最后释放p即可。

/*若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR*/
Status Pop(LinkStack *S,SElemType *e)
{
    LinkStackPtr p;
    if(StackEmpty(*S))
        return ERROR;
    *e=S->top-data;
    p = S->top; /*将栈顶结点赋值给p*/
    S->top = S->top->next;	/*使得栈顶指针下移以为,指向后一结点*/
    free(p);
    S->count--;
    return OK;
}

栈的应用–递归

斐波那契数列实现

1 1 2 3 5 8 13….

首先假设我们需要打印出前40位的斐波那契数

int main(void)
{
    int i;
    int a[40];
    a[0] = 0;
    a[1] = 1;
    printf("%d ",a[0]);
    printf("%d",a[1]);
    for(i=2;i<40;i++)
    {
        a[i]=a[i-1]+a[i-2];
        printf("%d ",a[i]);
    }
    return 0;
}

如果用递归来实现,可以更简单

int Fbi(int n)
{
    if(i<2)
        return i==0?0:1;
    return Fbi(i-1)+Fbi(i-2);
}
int main(void)
{
    int i;
    for(i=0;i<40;i++)
        printf("%d ",Fbi(i));
    return 0;
}

递归定义

我们把一个直接调用自己或通过一系列的调用语句间接地调用自己地函数,称作递归函数

那么递归和栈有什么关系呢?简单地说,就是在前行阶段,对于每一层递归,函数的局部变量,参数值以及返回地址都被压入栈中。在退回阶段,位于栈顶的局部变量,参数值和返回地址被弹出,处于返回调用层次中执行代码的其余部分,也就是恢复了调用的状态。

栈的应用——四则运算表达式求值

后缀表示法定义

对于多重括号,最终也是完全嵌套匹配的。这用栈结构正好合适,只有碰到左括号,就将此左括号进栈,不管表达式有多少重括号,反正遇到左括号就进栈,而后面出现右括号时,就让栈顶的左括号出栈,期间让数字运算,这样,最终有括号的表达式从左到右巡查一遍,栈应该是由空到有元素。

因此,波兰逻辑学家提出了不需要括号的后缀表达法,我们也把它称为逆波兰表示。

例如,对于”9+(3-1)*3+10/2″可以用后缀表达式表达为”9 3 1 – 3 * + 10 2 / +”

后缀表达式计算结果

为了解释后缀表达式的好处,我们来看看计算机如何用后缀表达式计算出最后结果

后缀表达式:9 3 1 – 3 * + 10 2 / +

规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到获得最终结果

  • 初始化一个空栈。此栈用来对要运算的数字进出使用。
  • 后缀表达式中前3个都是数字,所以9,3,1依次进栈
  • 接下来是”-“,所以将栈中的1出栈作为减数,3出栈作为被减数,并运算3-1得到2,再将2进栈,此时栈内为9(栈底) 2
  • 接着是数字3进栈,此时栈内为9 (栈底) 2 3
  • 后面是”*”,也就意味着3和2出栈,2与3相乘,得到6,并将6进栈
  • 下面是”+“,所以6和9出栈,9+6得到15,15进栈
  • 接着是10与2两数字进栈,此时栈内为15(栈底) 10 2
  • 然后是”/“,10与2相除,得到5,将5进栈,此时栈内为 15(栈底) 5
  • 最后是”+“,15+5得到20
  • 得到最后结果 20

可以看到后缀表达式计算很简单,那么怎么将中缀表达式转换为后缀表达式呢

中缀表达式转后缀表达式

中缀表达式”9+(3-1)*3+10/2″转化为后缀表达式”9 3 1 – 3 * + 10 2 / +”

规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即称为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号,则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式

  • 初始化一空栈
  • 第一个字符是数字9,输出9,后面是符号”+“,进栈
  • 第三个字符是”(“,依然是符号,因其只是左括号,还未配对,故进栈 此时栈内为+(栈底) (
  • 第四个字符是数字3,输出,表达式为9 3,接着是”-“,进栈,此时栈内为 +(栈底) ( –
  • 接下来是数字1,输出,总表达式是9 3 1,后面是符号”)“,此时,我们需要匹配此前的”(“,所以栈顶依次出栈,直到”(“出栈为止。因此输出”-“,此时从表达式为9 3 1 -,栈内只有+
  • 接着是数字3,输出,总表达式为9 3 1 – 3,接着是符号” * “,因为此时栈顶符号为”+“,优先级低于”*”,因此不输出,“ *“进栈。
  • 之后是”+“,因为栈中元素没有比”+“号更低的优先级,所以全部出栈。总输出表达式为9 3 1 – 3 * +。
  • 接着是数字10,输出,然后是符号”/“,所以”/“进栈
  • 最后数字2,输出,总的表达式为9 3 1 – 3 * + 10 2
  • 因为已经到了最后,所以将栈中符号全部出栈并输出,最后结果为9 3 1 – 3 * + 10 2 / +

所以计算机处理我们通常的中缀表达式的能力,最重要的就是两步:

  • 将中缀表达式转化为后缀表达式
  • 将后缀表达式进行运算得出结果

队列

队列的定义

队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表

队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。

假设队列q=(a1,a2…,an),那么a1就是队头元素,an是队尾元素。这样我们就可以删除时,总是从a1开始,而插入时,列在最后。

队列的抽象数据类型

ADT 队列(Queue)
Data
	同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系
Operation
	InitQueue(*Q):初始化操作,建立一个空队列Q
	DestroyQueue(*Q):若队列Q存在,则销毁它
	ClearQueue(*Q):将队列Q清空
	QueueEmpty(*Q):若队列Q为空,返回True,否则返回false
	GetHead(*Q):若队列Q存在且非空,用e返回队列Q的队头元素
	EnQueue(*Q,e):若队列Q存在,插入新元素e到队列Q中并成为队尾元素
	DeQueue(*Q,*e):删除队列Q中队头元素,并用e返回其值
	QueueLength(Q):返回队列Q的元素个数
endADT

 

循环队列

队列作为一种特殊的线性表,同样有顺序存储和链式存储这两种存储方式。

队列顺序存储的不足

我们假设一个队列有n个元素,则顺序存储的队列需建立一个大于n的数组,并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端即使队头。所谓的入队列操作,其实就是在队尾追加一个元素,不需要移动任何元素。

与栈不同的是,队列元素的出列是在队头,即下标为0的位置,那也就意味着队列中的所有元素都得向前移动,以保证队列的队头也就是下标为0的位置不为空。

当然,队头不需要一定在下标为0的位置。我们引入两个指针,front指针指向队头元素,rear指针指向队尾元素的下一个位置。这样当front=rear时,此队列就是一个空队列。

假设a1,a2出队,这时候接着入队的话,由于数组末尾元素已经被占用,再向后加会产生数组越界,但实际上,下标为0和1的位置还是空闲的。我们把这种现象叫做”假溢出“

循环队列定义

为了解决假溢出的现象,我们建立一个头尾相接的顺序存储结构队列,这种队列就叫做循环队列。

那么问题来了,我们刚才说空队列时,front=rear,那么当队列满时,front也等于rear,如何判断呢?

办法设置一个flag变量,当front=rear且flag=0时队列空,为1时队列满。

另外一个办法就是当队列空时,条件是front=rear,队列满时,我们修改其条件,保留一个元素空间。也就是说,队列满时,数组中还有一个空闲单位。

我们来讨论第二种办法,由于rear可能比front大,也可能比front小。

所以若队列的最大尺寸为QueueSize,那么队列满的条件是

(rear+1)%Queuesize ==front

比如一个尺寸为5的队列,front = 0 , rear = 4 ,(4+1)%5=0,所以此时队列满

如此来看,实现循环队列的代码也就不难

typedef int QElemType; /*QElemType类型根据实际情况而定*/
/*循环队列的顺序存储结构*/
typedef struct
{
    QElemType data[MAXSIZE];
    int front;   /*头指针*/
    int rear;	 /*尾指针,若队列不空,指向队列尾元素的下一个位置*/
}SqQueue;

循环队列的初始化代码

/*初始化一个空队列Q*/
Status InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

循环队列求队列长度代码

/*返回Q的元素个数,也就是队列的当前长度*/
int QueueLength(SqQueue Q)
{
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

循环队列的入队列操作

/*若队列未满,则插入元素e为Q新的队尾元素*/
Status EnQueue(SqQueue *Q,QElemType e)
{
    if((Q->rear+1)%MAXSIZE==Q->front) /*队列满的判断*/
        return ERROR;
    Q->data[Q->rear]=e;  /*将元素e赋值个队尾*/
    Q->rear = (Q->rear+1)%MAXSIZE;  /*rear指针向后移一位置*/
    						/*若到最后则转到数组头部*/
    return OK;
}

循环队列的出队列操作

/*若队列不空,则删除Q中队头元素,用e返回其值*/
Status DeQueue(SqQueue *Q,QElemType *e)
{
    if(Q->front==Q->rear)  /*队列空的判断*/
        return ERROR;
    *e = Q->data[Q->front];
    Q->front = (Q->front+1)%MAXSIZE;	/*front指针向后移一位置*/
    									/*若到最后则转到数组头部*/
    return OK;
}

队列的链式存储结构

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。为了操作上的方便,我们将队头指针指向链队列的头结点,而队尾指针指向终端结点。

空队列时,front和rear都指向头结点。

链队列的结构为:

typedef int QElemType;   

typedef struct QNode  /*结点结构*/
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
    QueuePtr front,rear;  /*队头,队尾指针*/
}LinkQueue;

入队操作

/*插入元素e为Q的新的队尾元素*/
Status EnQueue(LinkQueue *Q,QElemType e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if(!a)
        exit(OVERLOW);
    s->data = e;
    s->next = null;
    Q->rear->next = s;		/*把拥有元素e新结点s赋值给原队尾结点的后继*/
    Q->rear = s;  /*把当前的s设置为队尾结点,rear指向s*/
    return 	OK;
}

出队操作

/*若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/
Status DeQueue(LinkQueue *Q,QElemType *e)
{
    QueuePtr p;
    if(Q->front==Q->rear)
        return ERROR;
    p = Q->front->next;  /*将欲删除的队头结点暂存给p*/
    *e = p->data;  /*将欲删除的对头结点的值赋给e*/
    Q->front->next=p->next;   /*将原队头结点后继p->next赋值给头结点后继*/
    if(Q->rear == p) 		/*若队头是队尾,则删除后将rear指向头结点*/
        Q->rear=Q->front;
    free(p);
    return OK;
}

总结

  • 栈是限定仅在表尾进行插入和删除操作的线性表
  • 队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表

发表评论

电子邮件地址不会被公开。 必填项已用*标注