栈与队列问题：双向队列-白红宇

栈与队列问题：双向队列

阅读量：440 次

发布时间：2019-03-06

本文共 2465 字，大约阅读时间需要 8 分钟。

双向队列是一个可以同时从两端进行入队和出队操作的数据结构。队列的首尾相连，任何一端都可以作为队头或队尾。下面将详细介绍如何处理一系列操作，并输出最终队列的状态。

处理步骤

初始化

初始化一个数组来存储队列元素，使用一个变量来记录当前队列的长度。

处理命令

读取每条命令并根据命令类型进行相应操作：

左边入队（LIN X）：将元素插入队列的左端。如果队列已满，记录错误。

右边入队（RIN X）：将元素插入队列的右端。如果队列已满，记录错误。

左边出队（LOUT）：如果队列不为空，移除左端元素。

右边出队（ROUT）：如果队列不为空，移除右端元素。

记录错误

对于不合法的命令，记录错误信息并在输出时显示错误命令编号。

输出结果

如果队列为空，输出“队列为空”。

否则，从左到右输出每个元素，用空格隔开。

输出所有错误命令，格式为“X ERROR”，其中X是错误命令的序号。

示例输入

8LIN 5RIN 6LIN 3LOUTROUTROUTROUTLIN 3

处理过程

初始化

队列为空，数组f初始化为空，sum表示队列长度，初始为0。

处理每条命令

第1条：LIN 5
队列为空，插入5，队列变为[5]，sum=1。

第2条：RIN 6
插入6在右端，队列变为[5, 6]，sum=2。

第3条：LIN 3
插入3在左端，队列变为[3, 5, 6]，sum=3。

第4条：LOUT
移除左端元素3，队列变为[5, 6]，sum=2。

第5条：ROUT
移除右端元素6，队列变为[5]，sum=1。

第6条：ROUT
队列不为空，移除5，队列为空，sum=0。记录错误，命令序号6。

第7条：ROUT
队列为空，记录错误，命令序号7。

第8条：LIN 3
队列为空，插入3，队列变为[3]，sum=1。

输出结果

队列状态为[3]，输出为3。错误命令为第6、7条，输出6 ERROR和7 ERROR。

最终输出

36 ERROR7 ERROR

代码实现

#include 
   
    #include 
    
     #include 
     
      int main() {    int M;    scanf("%d", &M);    int sum = 0;    int s = 0;    int f[100000] = {-1};    int gh[100000] = {-1};    for (int j = 1; j <= M; ++j) {        char g[20];        scanf("%s", g);        if (strcmp(g, "LIN") == 0) {            int x;            scanf("%d", &x);            if (sum == 0) {                f[sum] = x;                sum++;            } else {                for (int i = sum; i > 0; --i) {                    f[i] = f[i - 1];                }                f[0] = x;                sum++;            }        } else if (strcmp(g, "RIN") == 0) {            int x;            scanf("%d", &x);            f[sum] = x;            sum++;        } else if (strcmp(g, "LOUT") == 0) {            if (sum == 0) {                gh[s] = j;                s++;            } else if (sum == 1) {                sum = 0;            } else {                for (int i = 0; i < sum - 1; ++i) {                    f[i] = f[i + 1];                }                sum--;            }        } else if (strcmp(g, "ROUT") == 0) {            if (sum == 0) {                gh[s] = j;                s++;            } else {                sum--;            }        } else {            gh[s] = j;            s++;        }    }    if (sum == 0) {        printf("队列为空");    } else {        for (int i = 0; i < sum - 1; ++i) {            printf("%d ", f[i]);        }        printf("%d\n", f[sum - 1]);    }    for (int i = 0; i < s; ++i) {        if (gh[i] != -1) {            printf("%d ERROR\n", gh[i]);        }    }    return 0;}