【数据结构与算法】栈与队列

栈

应用

数制转换

括号匹配的检验

行编辑程序问题

迷宫求解

表达式求值

栈与递归

汉诺塔问题

队列

定义及表示

链式队列

结构体定义

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

typedef struct{      //链队列定义
    QueuePtr front;  //队头指针，front->next是队头元素
    QueuePtr rear;   //队尾指针，指向队列尾元素
}LinkQueue;

构造一个空队列：

Status InitQueue (LinkQueue &Q) {
    // 构造一个空队列Q
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}

将队列销毁：

Status DestroyQueue (LinkQueue &Q) {
    // 销毁队列Q
    //这里有个问题！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
    while(Q.front){
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    return OK;
}

入队列：

Status EnQueue (LinkQueue &Q, QElemType e) {
    // 插入元素e为Q的新的队尾元素
    p = (QueuePtr) malloc (sizeof (QNode));
    if(!p) exit (OVERFLOW);  //存储分配失败
    p->data = e;   
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

出队列：

Status DeQueue (LinkQueue &Q, QElemType &e) {
    // 若队列不空，则删除Q的队头元素，
    // 用 e 返回其值，并返回OK；否则返回ERROR
    if(Q.rear == Q.front) return ERROR;
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear == p) Q.rear = Q.front;//注意这一步！！！！！！！！！！！！
    free(p);
    return OK;
}

循环队列

结构体定义

#define MAXQSIZE 100 //最大队列长度
typedef struct {
    ElemType *base; // 动态分配存储空间
    int front;       // 头指针，若队列不空,指向队列头元素
    int rear;       // 尾指针，若队列不空,指向队列尾元素 的下一个位置
}SqQueue;

构造空队列：

Status InitQueue (SqQueue &Q) {
    // 构造一个空队列Q
    Q.base = (ElemType*)malloc(MAXQSIZE * sizeof(ElemType));
    Q.front = Q.rear = 0;
    if(!Q.base) exit(OVERFLOW);
    return OK;
 }

入队列：

Status EnQueue (SqQueue &Q, ElemType e) {   
    // 插入元素e为Q的新的队尾元素
    //这里有问题！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
    if((Q.rear + 1) % MAXQSIZE == Q.front) exit(OVERFLOW);
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}

出队列：

Status DeQueue (SqQueue &Q, ElemType &e) { 
    // 若队列不空，则删除Q的队头元素，
    // 用e返回其值，并返回OK;  否则返回ERROR
    if (Q.front == Q.rear)  return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return OK;
}

应用

广度优先搜索求解迷宫最短路径