第三章 栈和队列

栈和队列的基本概念

栈的基本概念

  1. 栈的定义:是一种只能在一端进行插入或删除操作的线性表,其中允许进行插入或删除操作的一端称为栈顶。栈顶由一个称为栈顶指针的位置指示器(其实就是一个变量,对于顺序栈,就是记录栈顶元素所在数组位置标号的整型变量;对于链式栈,就是记录栈顶元素所在结点地址的指针)来指示。它是动态变化的,表的另一端为栈底,栈底是固定不变的,栈的插入和删除操作称为入栈和出栈。

  2. 栈的特点:由栈的定义可以看出,栈的主要特点是先进后出(FILO)。

  3. 栈的存储结构:可以通过顺序表和链表来存储栈,栈可以依照存储结构分为两种:顺序栈和链式栈

  4. 栈的数学特性:当n个元素以某种顺序进栈,并且可在任意时刻出栈(在满足先进后出的前提下)时,所获得的元素排列的数目N恰好满足函数Catalan()的计算,即\(N=\frac{1}{n+1}C_{2n}^{n}\)。

队列的基本概念

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

栈和队列的存储结构实现

栈和队列的结构体定义

  1. 顺序栈的定义
#define maxSize 100
typedef struct SeqStack{
    int data[maxSize];
    int top;
}SeqStack;
  1. 链栈节点定义
//有头结点的链栈
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode;
  1. 顺序队列定义
#define maxSize 100
//队列是循环队列。
typedef struct SeqQueue{
    int data[maxSize];
    int front; //队首指针
    int rear; //队尾指针
}SeqQueue;
  1. 队列结点定义
typedef struct QNode{
    int data;
    struct QNode *next;
}QNode;
  1. 链队定义
//链式队列不是循环队列
typedef struct LinkQueue{
    QNode *front; //队头
    QNode *rear; //队尾
}LinkQueue;

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

顺序栈

顺序表的要素

  1. 几个状态
    1. 栈空状态:st.top == -1,有的书上规定st.top == 0为栈空条件,但是这样会浪费一个元素大小的空间。
    2. 栈满状态:st.top == maxSize-1,maxSize为栈中最大元素的个数。则maxSize-1为栈满时栈顶元素在数组中的位置,因为数组下标从0开始,因此规定栈顶指针top为-1时栈空。即top==0的数组位置也可以存有数据元素。
    3. 非法状态(上溢和下溢):栈满就是一种继续入栈就会上溢的状态,对应的栈下溢就是栈空的时候继续出栈所导致的结果。
  2. 两个操作
    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. 两个状态
    1. 栈空状态:lst->next == NULL
    2. 栈满状态:不存在栈满的状况(假设内存无限大的情况)。
  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. 两个状态
    1. 队空状态:qu.rear == qu.front
    2. 队满装态:(qu.rear+1)%maxSize == qu.front
  2. 两个操作
    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. 两个状态
    1. 队空状态:lqu->rear == NULL或者lqu->front == NULL
    2. 队满状态:不存在队列满的情况。
  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,分别指向双端队列中两端的元素。

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

上一篇:JUC之阻塞队列(BlockingQueue)基础


下一篇:令人费解的java泛型