数据结构第三章栈和队列-阿里云开发者社区

栈

栈的定义
栈作为一种限定性线性表，是只允许在同一端进行插入和删除操作的线性表。

栈顶：通常将表中允许进行插入、删除操作的一端称为栈顶 (Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。

栈底：同时表的另一端被称为栈底 (Bottom)。

空栈：当栈中没有元素。

满栈：无法申请到栈区可用空间。

上溢：栈已满仍要入栈。

下溢：栈已空仍要出栈。

栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。具有先进后出（FILO）或后进先出（LIFO）的特点。
栈的示意图

栈的顺序实现

结构定义
用一组连续的存储单元依次存放自栈底到栈顶的数据元素。设一个位置指针top（栈顶指针）动态指示栈顶元素在顺序栈中的位置，当top=-1时，表示空栈。

typedef int datatype;  
# define MAXSIZE 100
typedef struct{    
    datatype  data[MAXSIZE];
    int top; 
    } seqstack; 
seqstack *s;

基本操作

（1）判断栈空

int EMPTY(seqstack *s) {
    return (!s–>top>=0);
}

（2）置空栈

void SETNULL(seqstack *s) {
    s–>top=-1;
}

（3）判断栈满

int FULL(seqstack  *s) {
    return (s–>top==MAXSIZE-1);
}

（4）进栈

seqstack * PUSH(seqstack  *s，datatype x) {
    if (FULL(s)){ 
        printf(“stack overflow”); 
        return NULL; 
    }
    s–>top++; 
    s–>data[s–>top]=x;  
    return s;
}

（5）出栈

datatype POP(seqstack *s) {
    if (EMPTY(s)) { 
        printf(“stack underflow”);
        return NULL;
    }
    s–>top--; 
    return(s–>data[s–>top+1]);
}

（6）取栈顶

datatype TOP(seqstack  *s) {
    if (EMPTY(s)) { 
        printf(“stack is empty”);
        return NULL;
    }
    return (s–>data[s–>top]);
}

两栈共享技术

栈的应用非常广泛，经常会出现在一个程序中需要同时使用多个栈的情况。若使用顺序栈，会因为对栈空间大小难以准确估计，从而产生有的栈溢出、有的栈空间还很空闲的情况。

为了解决这个问题，可以让多个栈共享一个足够大的数组空间，通过利用栈的动态特性来使其存储空间互相补充，这就是多栈共享技术。

在顺序栈的共享技术中最常用的是两个栈的共享技术即双端栈：它主要利用了“栈底位置不变，而栈顶位置动态变化”的特性。

首先为两个栈申请一个共享的一维数组空间S[M]，将两个栈的栈底分别放在一维数组的两端，分别是 0，M-1。由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。

由此可见，两栈共享要比两个栈分别申请M/2的空间利用率要高。

两栈共享的数据结构定义如下：

#define M 100 
typedef struct { 
    StackElementType Stack[M];   
    StackElementType  top[2]; /*top[0]和 top[1]分别为两个栈顶指示器*/
}DqStack;

两个栈共享空间的示意如下图所示:
双端栈

若栈1的底在v[1]，栈2的底在V[N]，则栈满的条件是top[1]+1==top[2]。

（1）初始化操作：

void InitStack(DqStack *S) {
    S->top[0]=-1; 
    S->top[1]=M; 
}

（2）进栈操作：

int Push(DqStack *S, StackElementType x, int i) {
    /*把数据元素 x 压入 i 号堆栈*/  
    if(S->top[0]+1==S->top[1]) /*栈已满*/
           return(FALSE);  
    switch(i)  {  
        case 0:  
            S->top[0]++;
            S->Stack[S->top[0]]=x; 
            break;  
        case 1:   
            S->top[1]--;
            S->Stack[S->top[1]]=x;
            break;    
        default:
            /*参数错误*/             
            return(FALSE)   
    }  return(TRUE); 
}

（3）出栈操作：

int Pop(DqStack *S, StackElementType *x, int i) {
    /* 从 i 号堆栈中弹出栈顶元素并送到 x 中 */  
    switch(i)  {
        case 0:
            if(S->top[0]==-1)
                return(FALSE);
            *x=S->Stack[S->top[0]];
            S->top[0]--;
            break;
        case 1:
            if(S->top[1]==M)
                return(FALSE);    
            *x=S->Stack[S->top[1]];
            S->top[1]++;
            break;
        default:
            return(FALSE);
    }
    return(TRUE);
}

栈的链式实现

链栈即采用链表作为存储结构实现的栈。为便于操作，这里采用带头结点的单链表实现栈。

由于栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针，如下图所示：

在上图中，top为栈顶指针，始终指向当前栈顶元素前面的头结点,它唯一地确定一个链栈。若top->next=NULL，则代表栈空,该链栈为空栈。

链栈中的结点是动态产生的，无需考虑上溢问题。

采用链栈时，栈的各种基本操作的实现与单链表的操作类似，对于链栈，在使用完毕时，应该释放其空间。

结构定义

typedef  int datatype;
typedef struct node{    
    datatype  data;
    struct node * next;
    }linkstack;
linkstack * top;

基本操作

（1）进栈

linkstack *PUSHLSTACK(linkstack *top, datatype x) { 
    linkstack *p;
    p＝(linkstack *)malloc(sizeof(linkstack));
    p->data＝x; 
    p->next＝top;
    return p;  //返回新栈顶指针
}

（2）出栈

linkstack *POPLSTACK(linkstack *top, datatype *datap) { 
    linkstack *p;
    if (top==NULL) { 
        printf(“under flow”);
    }
    datap＝top->data; /*栈顶结点数据存入*datap */
     p=top;
     top＝ top->next;
     free(p);
    return top;  //返回新栈顶指针
 }

队列

队列的概念
队列(Queue)也是一种运算受限的线性表。只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。具有先进先出（FIFO）的特点。

顺序队列
队列的一种顺序存储称为顺序队列。与顺序栈类似，在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队头到队尾的元素，如一维数组data[MAXSIZE]。由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针front和rear。

front:指示队头元素在数组中的位置

rear:指示真实队尾元素相邻的下一个位置

结构定义

#define MAXSIZE 100
typedef  struct{
    datatype data[MAXSIZE];
    int front;
    int rear;
}sequeue;
sequeue * sq;

假溢出
初始化队列时，令front = rear =0；入队时，直接将新元素送入尾指针rear所指的单元，然后尾指针增1；出队时，直接取出队头指针front所指的元素，然后头指针增1。

显然，在非空顺序队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后面的单元。当rear==MAXSIZE时，认为队满。

但此时不一定是真的队满，因为随着部分元素的出队，数组前面会出现一些空单元，如下图(d)所示。由于只能在队尾入队，致使被删除元素的空间永远无法重新利用。

把这种现象称为假溢出，真正队满的条件是rear - front=MAXSIZE。

链式队列

结构定义

typedef struct queuenode{
    datatype  data;
    struct queuenode  *next;
}QueueNode;

typedef struct{
    QueueNode  *front;
    QueueNode  *rear;
}LinkQueue;

基本操作
（1）置空

void InitQueue(LinkQueue  *Q) {
    Q.front=Q.rear=(queuenode*)malloc(sizeof(queuenode )); 
    Q.front->next=Q.rear->next=NULL;}

（2）判断队空

int QueueEmpty(LinkQueue  *Q) {
    return (Q.front->next= =NULL &&Q.rear->next= =NULL);
}

（3）入队

void EnQueue(LinkQueue  *Q, datatype x){    
    QueueNode *p;
    p=(QueueNode * )malloc(sizeof(QueueNode));
    p–>data=x;
    p–>next=NULL;
    Q->rear–>next=p;
    Q->rear=p;
}

（4）出队

DeQueue(linkqueue *Q) {
    linkqueue  *p;
    datatype x;
    if (EMPTY(Q))    
        return NULL;
    p = Q->front->next;      
    Q->front->next = p–>next;
    if (p->next==NULL) 
        Q->rear = Q->front;  
    x = p->data;
    free(p);
    return x;
}

循环队列

为了解决假溢出问题，引入了循环队列的概念。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界( MaxSize-1 )时，其加1操作的结果是指向向量的下界0。

判断栈满
入队时：尾指针向前追赶头指针，出队时：头指针向前追赶尾指针，故队空和队满时头尾指针均相等，无法通过sq->front == sq->rear来判断队列“空”还是“满”。
解决此问题的方法至少有两种：

另设一个布尔变量以区别队列的空和满；

少用一个元素空间为代价，入队前，测试尾指针 sq-> rear+1==sq->front ，若相等则认为队满。

基本操作
队空判断： sq->front == sq-> rear

队满判断： sq-> front ==(sq-> rear + 1) % maxSize

入队： sq-> rear = (sq-> rear + 1) % maxSize

出队： sq-> front = (sq-> front + 1) % maxSize

求队长： (sq-> rear - sq-> front+maxSize)%maxSize

（1）入队

检查队列是否已满，若队满，则进行溢出错误处理。

将队尾指针后移一个位置（即加1），指向下一单元。

将新元素赋给队尾指针所指单元。

Status EnQueue (SqQueue *Q, ElemType  e){    
    if ( (Q->rear+1)%MAXQSIZE == Q->front )  
        return(ERROR);   //队满上溢
    Q->rear=(Q->rear+1)%MAXQSIZE;
    Q->data[Q->rear]=e;
    return(True);   }

（2）出队

检查队列是否为空，若队空，则进行下溢错误处理。

将队首指针后移一个位置（即加1）。

取队首元素的值。

Status DeQueue (SqQueue *Q) { 
    if (Q->rear== Q->front)  
        return(NULL);  //队空下溢
    Q->front=(Q->front+1)%MAXQSIZE;
    return(Q->data[Q->front]);
}

（3）置空队

Q->front=Q->rear= MAXQSIZE-1;

（4）取队头

datatype  GetHead(SqQueue *Q ) { 
    if (Q->front==Q->rear)  
        return(NULL);  //队空
    return (Q->data[(Q->front+1)%MAXQSIZE] );
}

（5）判断队空

int QueueEmpty(SqQueue *Q ){
    if (Q->front==Q->rear) 
        return (True);
    else 
        return (False);  
}

栈和队列的应用

递归函数
递归函数又称为自调用函数，它的特点：在函数内部可以直接或间接地调用函数自己。

C语言描述如下：

int  FACT(int n) { 
    if (n==1) 
        return (1);
     else
        return (n*FACT(n-1));
}

算法表达式求值

计算机系统在处理表达式前，先设置两个栈：操作数栈(OPRD)：存放处理表达式过程中的操作数；运算符栈(OPTR)：存放处理表达式过程中的运算符。开始时，在运算符栈中先在栈底压入一个表达式的结束符“#”。

（1）中缀表示法
计算机系统在处理表达式时，从左到右依次读出表达式中的各个符号（操作数或运算符），每读出一个符号ch后，根据运算规则做如下处理：

如果ch是操作数，则将其压入操作数栈OPRD，并依次读取下一个符号。

若ch是运算符，则：
若读出的运算符的优先级大于OPTR栈顶的运算符优先级，则将其压入OPTR，并依次读下一个符号。
若读出的是“#”，且OPTR栈顶的运算符也是“#”，则表达式处理结束，最后的计算结果在OPRD的栈顶位置。

若读出的是“（”，则将其压入OPTR。

若读出的是“）”，则：若OPTR栈顶不是“(”，则从OPRD连续退出两个操作数，从OPTR中退出一个运算符，然后作相应的运算，并将运算结果压入OPRD，然后返回a)，让ch继续与OPTR栈顶元素进行比较。
若OPTR栈顶为“(”，则从OPTR退出“(”，依次读下一个符号。

若读出的运算符的优先级小于OPTR栈顶运算符的优先级，则从OPRD连续退出两个操作数，从OPTR中退出一个运算符，然后作相应的运算，将运算结果压入OPRD 。返回(2)继续OPTR栈顶元素进行比较。

（2）波兰表示法和逆波兰表示法

以5 + ( 6 – 4 / 2 ) * 3为例：

波兰表示法：+ 5 * - 6 / 4 2 3  

逆波兰表示法：5 6 4 2 / - 3 * +。

运算时按从左到右的顺序进行，不需要括号。在计算表达式时，可设置一个栈，从左到右扫描后缀表达式，每读到一个操作数就将其压入栈中；每读到一个运算符时，则从栈顶取出两个操作数运算，并将结果压入栈中，一直到后缀表达式读完。最后栈顶就是计算结果。

括号匹配

#include<stdio.h>
#define maxsize 100
typedef int datatype;

typedef struct{
    datatype data[maxsize];
    datatype top;
}seqstack;
seqstack *s;

void build();
void push();
void pop();
int check(char ss[]);

void main(){
    char ss[maxsize];
    build();
    printf("请输入要测试的算数表达式:");
    scanf("%s",ss);
    if(check(ss)==-1)
        printf("算数表达式不匹配!");
    else
        printf("算数表达式匹配!");
}

void build(){
    s=(seqstack*)malloc(sizeof(seqstack));
    s->top=-1;
}
int check(char ss[]){
    int i=0;
    while(ss[i] != '\0'){
        i++;
        if(ss[i] == '(')
            push();
        else if(ss[i] == ')')
            pop();
    }
    return s->top;
}

void push(){
    s->top++;
}
void pop(){
    s->top--;
}

回文串判断

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define maxsize 100

typedef struct {
    char data[maxsize];
    int top;
} stack;

typedef struct {
    char data[maxsize];
    int front;
    int rear;
} queue;

int isempty_queue(queue * stq){
    return stq->front == stq->rear;
}

int isfull_queue(queue *stq){
    return stq->rear >= maxsize -1 ;
}

queue * init_queue(){
    queue * tmp = (queue*) malloc(sizeof(queue));
    tmp->front = tmp->rear = 0;
    return tmp;
}

char dequeue(queue * stq){
    if( isempty_queue(stq) ) {
        printf("队列为空，无法出队\n");
        exit(0);
    }
    return stq->data[stq->front++];
}

void inqueue(queue *stq, char value) {
    if( isfull_queue(stq) ) {
        printf("队列已满，无法入队\n");
        exit(0);
    }
    stq->data[stq->rear++] = value;
}

stack * init_stack(){
    stack * tmp = (stack *) malloc( sizeof(stack) );
    tmp->top = 0;
    return tmp;
}

int isempty_stack(stack *stk) {
    return stk->top == 0 ? 1 : 0;
}

int isfull_stack(stack *stk) {
    return stk->top >= maxsize -1 ? 1: 0;
}

char pop(stack *stk) {
    if( isempty_stack(stk) ) {
        printf("堆栈为空，无法出栈\n");
        exit(0);
    }
    return stk->data[--stk->top];
}

void push(stack *stk, char value) {
    if( isfull_stack(stk) ) {
        printf("堆栈已满，无法入栈\n");
        exit(0);
    }
    stk->data[stk->top++] = value;
}

void compare(stack * stk, queue *stq, char str[], int len) {
    int i;
    int flag = 0;
    char temp_stack;
    char temp_queue;

    for(i = 0; i < len; i++){
        push(stk, str[i]);
        inqueue(stq, str[i]);
    }

    for(i = 0; i < len; i++){
        temp_stack = pop(stk);
        temp_queue = dequeue(stq);

        if(temp_stack != temp_queue) {
            printf("不是回文串\n");
            flag = 1;
            break;
        }
    }

    if( !flag )
        printf("是回文串\n");
}

int main(){
    queue * stq = init_queue();
    stack * stk = init_stack();

    char c[maxsize],s;
    int i=0;
    printf("请输入字符序列，以@结束\n");
    scanf("%c",&s);
    while(s!='@'){
        c[i]=s;
        scanf("%c",&s);
        i++;
    }
    c[i]='\0';
    compare(stk, stq, c, strlen(c)-1);

    return 0;
}

例题
例1
栈和队列是特殊的线性表，其特殊性体现在？为什么要引入循环队列？

和普通线性表相比，对插入、删除运算加以限制。一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，为了解决这种问题，就要引入循环队列。

例2
设一个栈的入栈序列为A、B、C、D，则可能的出栈序列有哪些？

共计14种，分别是：ABCD、ACBD、ACDB、ABDC、ADCB、BACD、BADC、BCAD、BCDA、BDCA、CBAD、CBDA、CDBA、DCBA。

例3
有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（C第一个出栈且D第二个出栈）的次序有哪几种？

共计3种，分别是：CDEBA、CDBEA、CDBAE。

例4
判定一个顺序栈ST（元素个数最多为StackSize）为空/满的条件是【】。

空：ST->top=0，满：ST->top=MAXSIZE-1。

例5
判定一个循环队列Q（存放元素位置：0至QueueSize-1）队满的条件是【】。

sq-> front ==(sq-> rear + 1) % maxSize。

例6
若用一个大小为6的数组来实现环形队列，且当前rear和front的值分别是0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是【】和【】。

2 ; 4

数据结构第三章栈和队列

栈

栈的顺序实现

基本操作

两栈共享技术

栈的链式实现

结构定义

基本操作

队列

链式队列

循环队列

栈和队列的应用

算法表达式求值

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

数据结构 第三章 栈和队列

栈

栈的顺序实现

基本操作

两栈共享技术

栈的链式实现

结构定义

基本操作

队列

链式队列

循环队列

栈和队列的应用

算法表达式求值

热门文章

最新文章

相关课程

相关电子书

数据结构第三章栈和队列