实验（训）项目名称

栈和队列的应用

实验（训）地点

明远楼C110

实验（训）日期

4.21

小组成员

无

小组成员

分工情况

个人

实验（训）所用设备、材料、软件等：

Win10操作系统计算机

VC++ 2010学习版软件

实验（训）目的：

掌握栈和队列的类型定义方法；掌握栈和队列的基本操作；掌握栈和队列的应用场合，能够根据具体问题选择合适的数据结构。

实验（训）内容、步骤、结果、心得体会：

一、实验内容

1.输入一个表达式，表达式中包括三种括号“（）”、“[]”和“{}”，判断该表达式的括号是否匹配。检验算法借助一个栈，每当读入一个左括号，则直接入栈，等待相匹配的同类右括号；每当读入一个右括号，若与当前栈顶的左括号类型相同，则二者匹配，将栈顶的左括号出栈，直到表达式扫描完毕。。

2.循环队列的应用——舞伴配对问题：在舞会上，男、女各自排成一队。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。试模拟解决上述舞伴配对问题。要求：从屏幕输出每一轮舞伴配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。

二、实验步骤

实验1：

#include <iostream>

using namespace std;

#define MAXSIZE 100 // 栈的最大容量

// ========== 顺序栈的定义 ==========

typedef struct {

  char data[MAXSIZE]; // 存储栈元素的数组

  int top;            // 栈顶指针，-1表示空栈

} SqStack;

// 初始化栈

void InitStack(SqStack &S) { S.top = -1; }

// 入栈

bool Push(SqStack &S, char e) {

  if (S.top == MAXSIZE - 1) { // 栈满

    cout << "栈满，无法入栈！" << endl;

    return false;

  }

  S.data[++S.top] = e; // 栈顶指针先+1，再存入元素

  return true;

}

// 出栈

bool Pop(SqStack &S, char &e) {

  if (S.top == -1) { // 栈空

    return false;

  }

  e = S.data[S.top--]; // 先取出栈顶元素，指针再-1

  return true;

}

// 取栈顶元素（不出栈）

bool GetTop(SqStack S, char &e) {

  if (S.top == -1) {

    return false;

  }

  e = S.data[S.top];

  return true;

}

// 判断栈是否为空

bool StackEmpty(SqStack S) { return S.top == -1; }

// 判断左右括号是否匹配

bool Match(char left, char right) {

  if (left == '(' && right == ')')

    return true;

  if (left == '[' && right == ']')

    return true;

  if (left == '{' && right == '}')

    return true;

  return false;

}

// ========== 主函数 ==========

int main() {

  SqStack S;

  InitStack(S);

  char str[200];

  cout << "请输入表达式: ";

  cin.getline(str, 200);

  int i = 0;

  bool flag = true;

  char ch;      // 当前扫描的字符

  char topElem; // 栈顶元素

  while (str[i] != '\0') {

    ch = str[i];

    // 遇到左括号，入栈

    if (ch == '(' || ch == '[' || ch == '{') {

      Push(S, ch);

    }

    // 遇到右括号，检查栈顶

    else if (ch == ')' || ch == ']' || ch == '}') {

      if (StackEmpty(S)) {

        cout << "错误：右括号 '" << ch << "' 没有对应的左括号！" << endl;

        flag = false;

        break;

      }

      GetTop(S, topElem);

      if (Match(topElem, ch)) {

        Pop(S, topElem); // 匹配成功，栈顶左括号出栈

      } else {

        cout << "错误：括号类型不匹配！栈顶是 '" << topElem << "'，当前是 '"

             << ch << "'" << endl;

        flag = false;

        break;

      }

    }

    // 其他字符直接忽略

    i++;

  }

  // 表达式扫描完毕，检查栈是否为空

  if (flag) {

    if (!StackEmpty(S)) {

      cout << "错误：存在未匹配的左括号，剩余 " << (S.top + 1) << " 个！"

           << endl;

      flag = false;

    }

  }

  if (flag) {

    cout << "结果：括号匹配正确！" << endl;

  } else {

    cout << "结果：括号不匹配！" << endl;

  }

  return 0;

}

结果：

实验2：

#include <iostream>

#include <string>

using namespace std;

#define MAXSIZE 100

// ========== 循环队列 ==========

typedef struct {

  string data[MAXSIZE];

  int front;

  int rear;

  int size;

} CirQueue;

void InitQueue(CirQueue &Q) {

  Q.front = 0;

  Q.rear = 0;

  Q.size = 0;

}

bool EnQueue(CirQueue &Q, string e) {

  if (Q.size == MAXSIZE)

    return false;

  Q.data[Q.rear] = e;

  Q.rear = (Q.rear + 1) % MAXSIZE;

  Q.size++;

  return true;

}

bool DeQueue(CirQueue &Q, string &e) {

  if (Q.size == 0)

    return false;

  e = Q.data[Q.front];

  Q.front = (Q.front + 1) % MAXSIZE;

  Q.size--;

  return true;

}

bool GetFront(CirQueue Q, string &e) {

  if (Q.size == 0)

    return false;

  e = Q.data[Q.front];

  return true;

}

bool QueueEmpty(CirQueue Q) { return Q.size == 0; }

int QueueLength(CirQueue Q) { return Q.size; }

// 求最小值

int Min(int a, int b) { return a < b ? a : b; }

// ========== 主函数 ==========

int main() {

  CirQueue maleQ, femaleQ;

  InitQueue(maleQ);

  InitQueue(femaleQ);

  int m, n, rounds;

  string name;

  // 输入男队

  cout << "请输入男队员人数: ";

  cin >> m;

  cin.ignore();

  cout << "请依次输入男队员姓名:" << endl;

  for (int i = 0; i < m; i++) {

    cout << "  第 " << i + 1 << " 位: ";

    getline(cin, name);

    EnQueue(maleQ, name);

  }

  // 输入女队

  cout << "\n请输入女队员人数: ";

  cin >> n;

  cin.ignore();

  cout << "请依次输入女队员姓名:" << endl;

  for (int i = 0; i < n; i++) {

    cout << "  第 " << i + 1 << " 位: ";

    getline(cin, name);

    EnQueue(femaleQ, name);

  }

  cout << "\n请输入舞会轮数: ";

  cin >> rounds;

  cout << "\n========== 舞会开始 ==========\n" << endl;

  for (int r = 1; r <= rounds; r++) {

    cout << "--- 第 " << r << " 轮舞曲 ---" << endl;

    // 核心修正：一轮的配对次数 = 两队当前长度的较小值

    int pairNum = Min(QueueLength(maleQ), QueueLength(femaleQ));

    int pairCount = 0;

    string male, female;

    for (int i = 0; i < pairNum; i++) {

      DeQueue(maleQ, male);

      DeQueue(femaleQ, female);

      cout << "  配对: " << male << " <-> " << female << endl;

      pairCount++;

      // 配对后回到队尾，等待下一轮

      EnQueue(maleQ, male);

      EnQueue(femaleQ, female);

    }

    cout << "  本轮共配对 " << pairCount << " 对" << endl;

    // 判断未配对情况

    if (QueueLength(maleQ) > QueueLength(femaleQ)) {

      string nextMale;

      GetFront(maleQ, nextMale);

      cout << "  >> 女队已空，男队剩余 "

           << (QueueLength(maleQ) - QueueLength(femaleQ)) << " 人未配对"

           << endl;

      cout << "  >> 下一轮第一个出场的未配对男队员: " << nextMale << endl;

    } else if (QueueLength(femaleQ) > QueueLength(maleQ)) {

      string nextFemale;

      GetFront(femaleQ, nextFemale);

      cout << "  >> 男队已空，女队剩余 "

           << (QueueLength(femaleQ) - QueueLength(maleQ)) << " 人未配对"

           << endl;

      cout << "  >> 下一轮第一个出场的未配对女队员: " << nextFemale << endl;

    } else {

      cout << "  >> 两队人数相等，全部配对，无剩余人员" << endl;

    }

    cout << endl;

  }

  cout << "========== 舞会结束 ==========" << endl;

  return 0;

}

结果：

心得体会：

本次实验围绕栈和队列这两种基本数据结构展开，通过"括号匹配"和"舞伴配对"两个具体问题的编程实现，我对线性结构的特性与应用有了更深刻的认识。

在实验一中，我采用顺序栈实现括号匹配。通过手动定义栈的结构体、编写入栈和出栈操作，我真正理解了"后进先出"原则的实际意义。当遇到左括号时入栈，遇到右括号时与栈顶元素匹配，这一过程中栈顶指针的动态变化让我体会到栈在解决"嵌套"和"对称"类问题时的天然优势。

实验二使用循环队列模拟舞伴配对，这是本次实验收获最大的一部分。最初我使用while循环配合"出队配对后回队尾"的逻辑，结果导致程序陷入无限循环。经过分析，我发现问题的根源在于没有明确界定"一轮舞曲"的边界——配对后回队虽然符合循环队列的等待机制，但一轮内的配对次数应由该轮开始时两队人数的较小值决定。修正为for循环控制配对次数后，程序逻辑才正确。这让我深刻认识到，选择合适的数据结构只是第一步，更重要的是将实际问题准确抽象为算法步骤，尤其要注意边界条件的设定。

通过亲手实现相关算法而非直接调用，让我更加理解了顺序栈和循环队列的底层存储原理，包括指针移动、取模运算、队空队满的判断等细节。这次实验让我体会到，数据结构不仅是理论的堆砌，更是解决实际问题的工具，只有将逻辑想清楚、把边界理明白，才能写出正确可靠的程序。

教师评语：

成绩评定

教师签名