一.基本概念

定义

栈 (Stack) 是只允许在一端进行插入和删除的线性表。(后进先出)

栈分为顺序栈和链栈。

术语

  • 栈顶 :允许进行插入、删除操作的一端称为栈顶 (top) 。
  • 栈底 :表的另一端
  • 进栈、入栈 :栈的插入操作通常称为进栈或入栈 (push)。
  • 退栈、出栈 :栈的删除操作通常称为退栈或出栈 (pop)。

二.顺序栈

1.定义顺序栈的结构体

数组+栈顶指针(存放栈顶元素的下标)即可。

typedef struct {
    ElemType data[MaxSize];	//存放栈中的数据元素
    int top;	//栈顶指针,即栈顶元素在data数组中的下标
} SqStack;

注:

  • 因为top指向的是栈顶在数组中的下标,所以当只有一个元素data[0]时,top为0。空栈的时候top自然就为-1
  • 栈满时:top == MaxSize - 1

2.初始化顺序栈

注意初始化时,top = -1 而不是0

void InitStack(SqStack *&s) {
    s = (SqStack *) malloc(sizeof(SqStack));
    s -> top = -1;
}

3.销毁顺序栈

void DestroyStack(SqStack *&s) {
    free(s);
}

4.判断栈是否为空

顺序栈s为空的条件:s->top==-1

bool StackEmpty(SqStack *s) {  
    return(s->top==-1);
}

5.进栈

注:栈满条件时top == MaxSize - 1

bool Push(SqStack *&s, ElemType e) {
    if (s->top==MaxSize-1) 	//溢出栈返回false
        return false;
    s->top++;		   	//栈顶指针增1
    s->data[s->top]=e;	   	//元素e放在栈顶指针处
    return true;
}

6.出栈

bool Pop(SqStack *&s, ElemType &e) {
    if (s->top==-1) 		//溢出栈返回false
        return false;
    e=s->data[s->top];	   	//将栈顶元素赋给e
    s->top--;			//栈顶指针减1
    return true;
}

7.取栈顶元素

bool GetTop(SqStack *s, ElemType &e) {
    if (s->top==-1) 		//栈满的情况,即栈上溢出
        return false;
    e=s->data[s->top];	   	//将栈顶元素赋给e
    return true;
}

三.链栈

这里采用带头结点的单链表来实现。

1.定义链栈的结构体

数据域+指针域

typedef struct linknode {
    ElemType data;		//数据域
    struct linknode *next;	//指针域
} LinkStNode;

注:

  • 栈空:s->next == NULL
  • 栈满:不用考虑栈满
  • 进栈:将结点插入头结点后面
  • 出栈:取出头结点的后一个结点并删除

2.初始化链栈

void InitStack(LinkStNode *&s) {
    s=(LinkStNode *)malloc(sizeof(LinkStNode));
    s->next=NULL;
}

3.销毁链栈

void DestroyStack(LinkStNode *&s) {
    LinkStNode *p=s->next;
    while (p!=NULL) {
        s->next=p->next;
        free(p);
        p=s->next;
    }
    free(s);
}

4.判断栈是否为空

bool StackEmpty(LinkStNode *s) {
    return (s->next==NULL);
}

5.进栈

void Push(LinkStNode *&s, ElemType e) {
    LinkStNode *p = (LinkStNode *)malloc(sizeof(LinkStNode));
    p->data=e;		//新建元素e对应的结点p
    p->next=s->next;	//插入p结点作为开始结点
    s->next=p;
}

6.出栈

bool Pop(LinkStNode *&s, ElemType &e) {
    LinkStNode *p;
    if (s->next==NULL)	//栈空的情况
        return false;
    p=s->next;		//p指向开始结点
    e=p->data;
    s->next=p->next;	//删除p结点
    free(p);		//释放p结点
    return true;
}

7.取栈顶元素

bool GetTop(LinkStNode *s, ElemType &e) {
    if (s->next==NULL)		//栈空的情况
        return false;
    e=s->next->data;		//p指向开始结点
    return true;
}

四.栈的应用

1.括号匹配

2.简单表达式求值

3.用栈求解迷宫问题

队列

一.基本概念

定义

队列是只允许在一端插入,在另一端删除的线性表。(先进先出)

队列分为顺序对和链队

术语

  • 队尾:允许插入的一端
  • 队头:允许删除的一端
  • 进队、入队:向队列中插入新元素(新元素进队后就成为新的队尾元素)
  • 出队、离队:从队列中删除元素(元素出队后,其后继元素就成为队首元素)

二.顺序队

1.定义顺序队的结构体

数组 + 队头、队尾指针

typedef struct {
    ElemType data[MaxSize];    //存放队列中的数据元素
    int front, rear;        //队头和队尾指针
} SqQueue;

注:

  • 队空:front和rear都是-1
  • 队满:rear == MaxSize - 1
  • 进队:rear ++
  • 出队:front ++

例:

2.初始化顺序队

将front和rear指针设成-1

void InitQueue(SqQueue *&q) {
    q=(SqQueue *)malloc(sizeof(SqQueue));
    q->front=q->rear=-1;
}

3.销毁顺序队

void DestroyQueue(SqQueue *&q) {
    free(q);
}

4.判断队列是否为空

队空:front == rear

(不能用是否等于-1去判断队空,看上面那个图,全部出队时也是队空,此时front==rear==4,而不是-1)

bool QueueEmpty(SqQueue *q) {
    return (q->front==q->rear);
}

5.进队

bool enQueue(SqQueue *&q, ElemType e) {
    if (q->rear==MaxSize-1)	//队满上溢出
        return false;
    q->rear++;
    q->data[q->rear]=e;
    return true;
}

6.出队

bool deQueue(SqQueue *&q, ElemType &e) {
    if (q->front==q->rear)	//队空
        return false;
    q->front++;
    e=q->data[q->front];
    return true;
}

三.环形(顺序)队列

上述顺序队列有个问题,当出队后,front++,那么front之前的空间就浪费了,如图,还有空间,但却无法继续进队。

而环形队列就是 把数组的两端连接起来,形成一个环。

环形队列的重点在于:实际的内存空间不可能是环形的,需要通过逻辑的方式来实现环形队列

  • rear=(rear+1)%MaxSize
  • front=(front+1)%MaxSize

比如:MaxSize=5,若rear = 7,则运算后rear在3的位置。

环形队列的各种情况

从第一幅图和最后一幅图可以看到,此时有一个问题,普通的顺序队的队空条件是front=rear,而循环顺序队列队空和队满时,都是front=rear,那么要如何区分队空和队满呢?

方案一:(rear+1)%MaxSize=front 为队满条件。、

比如MaxSize=5,front=0时,rear==4为队满。

少用一个元素空间,最多只能放MaxSize-1个元素。

此时有:

  • 队空:front = rear
  • 队满:(rear+1)%MaxSize = front
  • 进队:rear=(rear+1)%MaxSize;
  • 出队:front=(front+1)%MaxSize;

方案二:定义结构体时用队列元素数量代替尾指针

顺序存储,尾指针可以用front+count算出来。

typedef struct {
    ElemType data[MaxSize];
    int front;	//头指针
    int count;	//队列中元素个数
} QuType;

此时有:

  • 队空:count== 0;
  • 队满:count == MaxSize;
  • 进队:rear=(rear+1)%MaxSize; count++;
  • 出队:front=(front+1)%MaxSize; count--;

四.链队

采用的是不含头结点的单链表。

也就是说,头指针直接指向的是第一个元素结点(首结点),没有头结点则空和非空要分开讨论

1.定义链队结构体

在单链表结构体的基础上,再定义一个含队首和队尾指针的结构体,指向该单链表的首结点和尾结点。

typedef struct qnode {  //单链表结构体——针对每个结点
    ElemType data;	
    struct qnode *next;
} DataNode;

typedef struct {        //链队结构体——针对总的链表
    DataNode *front;	//指向队头结点
    DataNode *rear; 	//指向队尾结点
} LinkQuNode;

注:

  • 队空:front=rear=NULL(front=NULL或rear=NULL)
  • 队满:不考虑
  • 进队:将包含e的结点插入到单链表表尾
  • 出队:删除单链表首元素结点

2.初始化链队

创建一个链队头结点,其front和rear域均置为NULL。

void InitQueue(LinkQuNode *&q) {
    q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
    q->front=q->rear=NULL;
}

3.销毁链队

void DestroyQueue(LinkQuNode *&q) {
    DataNode *p = q->front, *r;    //p指向队头数据结点
    while (p != NULL) {
        r = p->next;
        free(p);
        p = r;
    }
}

4.判断队列是否为空

队空条件:front=rear=NULL,但是判断是否为空,只要判断其中一个即可。

bool QueueEmpty(LinkQuNode *q) {
    return(q->rear==NULL);
}

5.进队

两种情况:

  • 队列为空 :q->front=q->rear=p;
  • 队列不为空:q->rear->next=p ; q->rear=p
void enQueue(LinkQuNode *&q, ElemType e) {
    DataNode *p=(DataNode *)malloc(sizeof(DataNode));
    p->data=e;
    p->next=NULL;
    if (q->rear==NULL)		//若链队为空
        q->front=q->rear=p;	//新结点是队首结点又是队尾结点
    else {				//若链队非空
        q->rear->next=p;		//将新结点链到队尾
        q->rear=p;			//并将rear指向它
    }
}

6.出队

由于没有头结点,空和非空时要分开讨论,因此有三种情况:

  • 队列为空
  • 队列有一个结点(出队后就为空了)
  • 队列有大于一个结点
bool deQueue(LinkQuNode *&q, ElemType &e) {
    DataNode *t;
    if (q->rear==NULL)		//队列为空
        return false;
    t=q->front;		   	//t指向第一个数据结点
    if (q->front==q->rear)  	//队列中只有一个结点时
        q->front=q->rear=NULL;
    else			   	//队列中有多个结点时
        q->front=q->front->next;
    e=t->data;
    free(t);
    return true;
}

五.环形(链)队列

这里介绍只带尾指针rear的循环单链表存储队列。

链表要形成环,只要尾结点指向首结点即可。如图:

注:

  • 队空:rear==NULL
  • 队满:不考虑
  • 进队:将包含e的结点插入到单链表表尾
  • 出队:删除单链表首结点

1.入队

void enQueue(LinkNode *&rear, ElemType e) {
    LinkNode *p;
    p=(LinkNode *)malloc(sizeof(LinkNode));    //创建新结点
    p->data=e;
    if (rear==NULL) {		//原链队为空
        p->next=p;		//构成循环链表
        rear=p;
    }
    else {			//原链队非空
        p->next=rear->next;	//将p结点插入到rear结点之后
        rear->next=p;
        rear=p;			//让rear指向这个新插入的结点
    }
}

2.出队

bool deQueue(LinkNode *&rear, ElemType &e) { 
    if (rear==NULL) 		        //队空
        return false;
    else if (rear->next==rear) {	//原队中只有一个结点
        e=rear->data;
        free(rear);
        rear=NULL;			//变为空队列
    }
    else {				//原队中有两个或以上的结点
        LinkNode *t=rear->next;
        e=t->data;
        rear->next=t->next;
        free(t);
    }
    return true;
}

六.队列的应用

1.报数问题

2.杨辉三角

3.使用队列求解迷宫问题

学习目标

  • 理解栈和队列的特性。
  • 掌握顺序栈和链栈中基本运算的实现。
  • 掌握顺序队和链队中基本运算的实现。
  • 掌握环形队列的实现方式。
  • 理解栈和队列的差异,知道在何时使用哪一种数据结构。
  • 能够灵活运用栈和队列进行算法设计,解决实际问题。