第三章栈和队列

2024-01-19 19:21:52

栈和队列的基本概念

栈的基本概念

栈的定义：是一种只能在一端进行插入或删除操作的线性表，其中允许进行插入或删除操作的一端称为栈顶。栈顶由一个称为栈顶指针的位置指示器（其实就是一个变量，对于顺序栈，就是记录栈顶元素所在数组位置标号的整型变量；对于链式栈，就是记录栈顶元素所在结点地址的指针）来指示。它是动态变化的，表的另一端为栈底，栈底是固定不变的，栈的插入和删除操作称为入栈和出栈。
栈的特点：由栈的定义可以看出，栈的主要特点是先进后出（FILO）。
栈的存储结构：可以通过顺序表和链表来存储栈，栈可以依照存储结构分为两种：顺序栈和链式栈。
栈的数学特性：当n个元素以某种顺序进栈，并且可在任意时刻出栈（在满足先进后出的前提下）时，所获得的元素排列的数目N恰好满足函数Catalan()的计算，即\(N=\frac{1}{n+1}C_{2n}^{n}\)。

队列的基本概念

队列的定义：也是一种操作受限的线性表，其限制为仅允许在表中的一端进行插入，在表的另一端进行删除。可进行插入的一端称为队尾（rear），可以进行删除的一端称为队头（front）。向队列中插入新的元素称为进队，新元素进队后就成为新的队尾元素；从队列中删除元素称为出队，元素出队后，其后继元素称为新的队头元素。
队列的特点：由队列的定义得到，队列主要特点为先进先出（FIFO）。
队列的存储结构：可用顺序表和链表来存储队列，队列按存储结构分为顺序队和链队。

栈和队列的存储结构实现

栈和队列的结构体定义

顺序栈的定义

#define maxSize 100
typedef struct SeqStack{
    int data[maxSize];
    int top;
}SeqStack;

链栈节点定义

//有头结点的链栈
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode;

顺序队列定义

#define maxSize 100
//队列是循环队列。
typedef struct SeqQueue{
    int data[maxSize];
    int front; //队首指针
    int rear; //队尾指针
}SeqQueue;

队列结点定义

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

链队定义

//链式队列不是循环队列
typedef struct LinkQueue{
    QNode *front; //队头
    QNode *rear; //队尾
}LinkQueue;

栈只需要创建结点，因为栈只有一个控制结点，使用单独的结点进行控制。

顺序栈

顺序表的要素

几个状态
1. 栈空状态：st.top == -1，有的书上规定st.top == 0为栈空条件，但是这样会浪费一个元素大小的空间。
2. 栈满状态：st.top == maxSize-1，maxSize为栈中最大元素的个数。则maxSize-1为栈满时栈顶元素在数组中的位置，因为数组下标从0开始，因此规定栈顶指针top为-1时栈空。即top==0的数组位置也可以存有数据元素。
3. 非法状态（上溢和下溢）：栈满就是一种继续入栈就会上溢的状态，对应的栈下溢就是栈空的时候继续出栈所导致的结果。
两个操作
1. 元素x进栈的操作：++(st.top);st.data[st.top]=x;。规定了top为-1时栈为空，则元素进栈操作必须先移动指针，再进入元素。
2. 元素x出栈的操作：x=st.data[st.top];--(st.top);。进栈操作的次序决定了出栈操作的次序。由于进栈操作是先变动栈顶指针，再存入元素，因此出栈操作必须先取出元素，再变动指针。

操作定义

//初始化栈
SeqStack* initStack();
//判断栈是否为空，栈为空时返回1
int isEmpty(SeqStack stack);
//判断栈是否为满，如果满时返回1
int isFull(SeqStack stack);
//进栈操作，进栈成功返回1
int push(SeqStack* stack,int data);
//出栈操作，x为出栈元素的结果
int pop(SeqStack* stack,int* x);

操作实现

SeqStack* initStack(){
    SeqStack* stack = (SeqStack*) malloc(sizeof(SeqStack));
    stack->top = -1;
    return stack;
}

int isEmpty(SeqStack* stack){
    if(stack->top == -1){
        return 1;
    }else{
        return 0;
    }
}

int isFull(SeqStack* stack){
    if(stack->top == maxSize-1){
        return 1;
    }else{
        return 0;
    }
}

int push(SeqStack* stack,int data){
    if(isFull(stack) == 1){
        return 0;
    }else{
        ++stack->top;
        stack->data[stack->top] = data;
        return 1;
    }
}

int pop(SeqStack* stack,int* x){
    if(isEmpty(stack) == 1){
        return 0;
    }
    *x = stack->data[stack->top];
    --stack->top;
    return 1;
}

链栈

链栈的要素

两个状态
1. 栈空状态：lst->next == NULL
2. 栈满状态：不存在栈满的状况（假设内存无限大的情况）。
两个操作
1. 元素（由指针p所指）进栈操作：p->next = lst->next; lst->next = p;（其实就是头插法插入节点）
2. 出栈操作（出栈元素保存在x中）：p = lst->next;x = p->data;lst->next = p->next;（其实就是单链表的删除操作）

操作定义

//初始化链栈
LNode* initStack();
//判断栈空，返回1,栈满
int isEmpty(LNode* lst);
//进栈操作
void push(LNode* lst,int x);
//出栈操作，如果成功返回1
int pop(LNode *lst,int* x);

操作实现

LNode* initStack(){
    LNode* lst = (LNode*) malloc(sizeof(LNode));
    lst->next = nullptr;
    return lst;
}

int isEmpty(LNode* lst){
    if(lst->next == nullptr){
        return 1;
    }else{
        return 0;
    }
}

void push(LNode* lst,int x){
    LNode *p;
    p = (LNode*) malloc(sizeof(LNode));
    p->next = nullptr;
    //头插法插入节点
    p->data = x;
    p->next = lst->next; //原先的节点在后面。弹出时，将首节点弹出即可。
    lst->next = p;
}

int pop(LNode *lst,int* x){
    LNode *p;
    if(lst->next == nullptr){
        return 0;
    }
    p = lst->next;
    *x = p->data;
    lst->next = p->next; //删除首节点的元素
    free(p);
    return 1;
}

顺序队

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

要实现指针在递增的过程中沿着环形道路行走，拿front指针来说，可以循环执行front = (front+1)%maxSize，若front的初始值为0，在一个无限循环中，front的取值范围只能是0~maxSize-1。

因为必须要求有表头，所以循环链表必须损失一个存储空间，如果表头也存入元素，则队满的条件为front==rear，即和队空条件相同，那么无法区分队空和队满。

循环队列的要素

两个状态
1. 队空状态：qu.rear == qu.front
2. 队满装态：(qu.rear+1)%maxSize == qu.front
两个操作
1. 元素x进队操作（移动队尾指针）：qu.rear=(qu.rear+1)%maxSize;qu.data[qu.rear]=x;
2. 元素x出队操作（移动队头指针）：qu.front=(qu.front+1)%maxSize;x=qu.data[qu.front];

操作定义

//初始化队列
SeqQueue* initSeqQueue();
//判断队空
int isQueueEmpty(SeqQueue *queue);
//进队操作
int enQueue(SeqQueue *queue,int x);
//出队操作
int deQueue(SeqQueue* queue,int *x);

操作实现

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

int isQueueEmpty(SeqQueue *queue){
    if(queue->rear == queue->front){
        return 1;
    }else{
        return 0;
    }
}

//元素进队操作(移动队尾指针)：
// queue->rear = (queue->rear+1)%maxSize; queue->data[queue->rear]=x;
int enQueue(SeqQueue *queue,int x){
    if((queue->rear+1)%maxSize == queue->front){ //队满
        return 0;
    }
    queue->rear = (queue->rear + 1) % maxSize;
    queue->data[queue->rear] = x;
    return 1;
}

//元素出队操作（移动队首指针）
//queue->front = (queue->front + 1)%maxSize; *x = queue->data[queue->front];
int deQueue(SeqQueue* queue,int *x){
    if(queue->front == queue->rear){ //队空
        return 0;
    }
    queue->front = (queue->front + 1)%maxSize;
    *x = queue->data[queue->front];
    return 1;
}

链队

链队就是采用链式存储结构存储队列，这里采用单链表实现，链表的特点就是不存在队列满上溢的情况。

链队的要素

两个状态
1. 队空状态：lqu->rear == NULL或者lqu->front == NULL
2. 队满状态：不存在队列满的情况。
两个操作
1. 元素进队操作：lqu->rear->next=p;lqu->rear=p;
2. 元素出队操作：p=lqu->front;lqu->front=p->next;x=p->data;

操作定义

//初始化队列
LinkQueue* initQueue();
//判断队空
int isQueueEmpty(LinkQueue* queue);
//入队操作
void enQueue(LinkQueue* queue,int x);
//出队操作
void deQueue(LinkQueue* queue,int *x);

操作实现

LinkQueue* initQueue(){
    LinkQueue* queue = (LinkQueue*) malloc(sizeof(LinkQueue));
    queue->front = queue->rear = nullptr;
    return queue;
}

int isQueueEmpty(LinkQueue* queue){
    if(queue->rear == nullptr || queue->front == nullptr){
        return 1;
    }else{
        return 0;
    }
}

void enQueue(LinkQueue* queue,int x){
    QNode *p;
    p = (QNode*) malloc(sizeof(QNode));
    p->data = x;
    p->next = nullptr;
    if(queue->rear == nullptr){
        queue->rear = queue->front = p;
    }else{
        queue->rear->next = p;
        queue->rear = p;
    }
}

void deQueue(LinkQueue* queue,int *x){
    QNode *p;
    if(queue->rear == nullptr){
        return;
    }else{
        p = queue->front;
    }
    if(queue->front == queue->rear){ //队列中有一个节点时出队要特殊处理
        queue->front = queue->rear = nullptr;
    } else{
        queue->front = queue->front->next;
    }
    *x = p->data;
}

栈的应用

括号匹配

int match(char exp[],int n){
    char stack[maxSize];
    int top = -1;
    for (int i = 0; i < n; ++i) {
        if(exp[i] == '('){
            stack[++top] = '(';
        }
        if(exp[i] == ')'){
            if(top == -1){
                return 0; //不匹配
            }else{
                top--; //如果栈不空，则出栈。
            }
        }
    }
    if(top == -1){ //栈空，则说明括号匹配
        return 1;
    }else{
        return 0; //否则，不匹配
    }
}

计算后缀表达式结果

int com(char exp[]){
    int i,a,b,c;
    int stack[maxSize];
    int top = -1;

    char Op;
    for(i = 0;exp[i] != '\0';++i){
        if(exp[i] >= '0' && exp[i] <= '9'){ //如果遇到操作数，则入栈等待处理。
            stack[++top] = exp[i] - '0';
        }else{ //碰到运算符，开始计算。
            Op = exp[i];
            b = stack[top--];
            a = stack[top--];
            c = op(a,Op,b);
            stack[++top] = c;
        }
    }
    return stack[top];
}

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 == '/'){
        if(b == 0){
            printf("Error");
            return 0;
        }else{
            return a/b;
        }
    }
    return 0;
}

共享栈和双端队列

共享栈

相比于普通的顺序栈，共享栈主要是为了提高内存的利用率和减少溢出的可能性而设计的，共享栈有很多特性。下面通过一个例题来了解共享栈。

为了增加内存空间的利用率和减少溢出的可能性，当两个栈共享一片连续的内存空间时，应将两栈的栈底分别设在这片内存空间的两端，这样当两个栈的栈顶在栈空间的某一位置相遇时，才产生溢出。

解析：两个栈共享一片连续的存储空间，可知这两个栈都是顺序栈，进一步可知，为顺序栈分配好的连续空间大小在栈的操作过程中不变，并且这个连续的存储空间有恒定不变的两端。于是可以想到，这两个栈的栈底分别位于存储空间两端。确定了栈底，则两栈栈顶必在存储空间内，显然当两栈顶相遇时，存储空间耗尽，会产生溢出。

双端队列

双端队列是一种插入和删除操作在两端都可以进行的线性表，可以把双端队列看成栈底连在一起的两个栈。它们与两个栈共享存储空间的共享栈不同的是：两个栈的栈顶指针时向两端延伸的。由于双端队列允许在两端插入和删除元素，因此需要设立两个指针：end1和end2，分别指向双端队列中两端的元素。

允许在一端进行插入和删除，另一端只允许删除的双端队列称为输入受限的双端队列。允许在一端进行插入和删除，另一端只允许插入的双端队列称为输出受限的双端队列。

码农公寓

栈和队列的基本概念

栈的基本概念

队列的基本概念

栈和队列的存储结构实现

栈和队列的结构体定义

顺序栈

链栈

顺序队

链队

栈的应用

括号匹配

计算后缀表达式结果

共享栈和双端队列

共享栈

双端队列

相关文章