数据结构 - 栈与队列 - 《Notes》

#include<stdio.h>
#include<malloc.h>
typedef struct node                 //定义链栈结点
{
    int data;                       //这里以整型数据为例
    struct node *next;              //指针类型,存放下一个结点地址
} NODE;
NODE *crea_linkstack()              //建立链栈
{
    NODE *top, *p;                  //定义栈顶指针top
    int a, n;
    top = NULL;
    printf("\nInput number of push linkstack : ");
    scanf("%d", &n);                //入链栈的元素个数
    if (n > 0)                      //若n<=0,建立空栈
    {
        printf("Input %d elements of push linkstack : ", n);
        while (n > 0) {
            scanf("%d", &a); //输入新元素
            p = (NODE *) malloc(sizeof(NODE));
            p->data = a;
            p->next = top;
            top = p;
            n--;
        }
    }
    return (top);                    //返回栈顶指针
}
NODE *pushstack(NODE *top, int x)    //进栈操作
{
    NODE *p;
    p = (NODE *) malloc(sizeof(NODE));
    p->data = x;                     //将要插入的数据x存储到结点p的数据域中
    p->next = top;                   //将p插入链表头部,即链栈顶部
    top = p;
    return (top);
}
void print(NODE *top)                //输出链栈中各元素
{
    NODE *p;
    p = top;
    if (p != NULL) {
        printf("Output the linkstack : ");
        while (p != NULL) {
            printf("%3d", p->data);
            p = p->next;
        }
    } else
        printf("\nThe stack is empty!!!");
}
main()                              //主程序
{
    int y;                          //将入栈的元素
    NODE *a;
    a = crea_linkstack();           //建立链栈
    print(a);                       //输出整个链栈
    printf("\nPush a element to linkstack : ");
    scanf("%d", &y);                //输入进栈元素y
    a = pushstack(a, y);            //y进栈
    print(a);                       //输出整个链栈
}

编写一个程序，输入 n（由用户输入）个 10 以内的数，每输入 i（0≤i≤9），就把它插入到第 i 号队列中。最后把 10 个队中非空队列，按队列号从小到大的顺序串接成一条链，并输出该链的所有元素。
解答：建立一个队头指针数组 quh 和队尾指针数组 qut，quh[i]和 qut[i]表示 i 号（0≤i≤9）队列的队头和队尾，先将它们所有元素置为 NULL。对于输入的 x，采用尾插法将其链到 x号队列中。然后按 0～9 编号的顺序把这些队列中的结点构成一个不带头结点的单链表，其首结点指针为 head。最后输出单链表 head 的所有结点值并释放所有结点。

#include <stdio.h>
#include <malloc.h>
#define MAXQNode 10                           //队列的个数
typedef struct node {
    int data;
    struct node *next;
} QNode;
void Insert(QNode *quh[], QNode *qut[], int x) //将 x 插入到相应队列中
{
    QNode *s;
    s = (QNode *) malloc(sizeof(QNode));       //创建一个结点 s s->data=x; s->next=NULL;
    if (quh[x] == NULL)                        //x 号队列为空队时
    {
        quh[x] = s;
        qut[x] = s;
    } else                                     //x 号队列不空队时
    {
        qut[x]->next = s;                      //将 s 结点链到 qut[x]所指结点之后
        qut[x] = s;                            //让 qut[x]仍指向尾结点
    }
}
void Create(QNode *quh[], QNode *qut[])       //根据用户输入创建队列
{
    int n, x, i;
    printf("n:");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        do {
            printf("输入第%d 个数:", i + 1);
            scanf("%d", &x);
        } while (x < 0 || x > 10);
        Insert(quh, qut, x);
    }
}
void DestroyList(QNode *head)                 //释放单链表
{
    QNode *pre = head, *p = pre->next;
    while (p != NULL) {
        free(pre);
        pre = p;
        p = p->next;
    }
    free(pre);
}
void DispList(QNode *&head)                   //输出单链表的所有结点值
{
    printf("\n 输出所有元素:");
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}
QNode *Link(QNode *quh[], QNode *qut[])     //将非空队列链接起来并输出
{
    QNode *head = NULL, *tail;              //总链表的首结点指针和尾结点指针
    int i;
    for (i = 0; i < MAXQNode; i++)          //扫描所有队列
        if (quh[i] != NULL)                 //i 号队列不空
        {
            if (head == NULL)               //若 i 号队列为第一个非空队列
            {
                head = quh[i];
                tail = qut[i];
            } else                          //若 i 号队列不是第一个非空队列
            {
                tail->next = quh[i];
                tail = qut[i];
            }
        }
    tail->next = NULL;
    return head;
}
int main() {
    int i;
    QNode *head;
    QNode *quh[MAXQNode], *qut[MAXQNode];   //各队列的队头 quh 和队尾指针 qut
    for (i = 0; i < MAXQNode; i++)
        quh[i] = qut[i] = NULL;             //置初值空
    Create(quh, qut);                       //建立队列
    head = Link(quh, qut);                  //链接各队列产生单链表
    DispList(head);                         //输出单链表
    DestroyList(head);                      //销毁单链表
    return 1;
}

环形队列？采用什么方法实现
当用数组表示队列时，把数组看成是一个环形的，即令数组中第一个元素紧跟在最末一个单元之后，就形成一个环形队列。环形队列解决了非环形队列中出现的“假溢出”现象。
通常采用逻辑上求余数的方法来实现环形队列，假设数组的大小为 n，当元素下标 i 增 1 时，采用 i=(i+1)%n 来实现。

环形队列一定优于非环形队列吗？什么情况下使用非环形队列？
队列主要是用于保存中间数据，而且保存的数据满足先产生先处理的特点。非环形队列可能存在数据假溢出，即队列中还有空间，可是队满的条件却成立了，为此改为环形队列，这样克服了假溢出。但并不能说环形队列一定优于非环形队列，因为环形队列中出队元素的空间可能被后来进队的元素覆盖，如果算法要求在队列操作结束后利用进队的所有元素实现某种功能，这样环形队列就不适合了，这种情况下需要使用非环形队列，例如利用非环形队列求解迷宫路径就是这种情况。