栈和队列上机实验

1.要求

  1.利用栈的基本操作实现将任意一个十进制整数转化为R进制整数。

  2.利用循环队列实现.约瑟夫环问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人出圈；他的下一个人又从1开始报数，数到k的那个人出圈；依此规律重复下去，直到圆桌周围的人只剩最后一个。模拟该游戏，并输出出圈顺序。

            

2.栈的实现（以顺序栈为例）

  栈的基本概念：

  栈（stack）是一种数据结构，它是一种只能在一端进行插入和删除操作的特殊线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

  
  栈的基本结构和初始化：

  我们定义了一个名为Stack的模板类，用于实现可以存储各种数据类型的栈的数据结构。我们创建了三个Stack的成员函数：_base、_top 和 _size。

  _base: 它作为动态分配的栈内存的起始位置。

  _top:表示栈顶的位置。 在构造函数中，它被初始化为指向InitStackSize个新分配的SElemType元素的数组的末尾。

  _size: 是一个整数，用于表示栈的当前大小，即栈中元素的数量。 在构造函数中，它被初始化为InitStackSize。

  构造函数: Stack()函数负责初始化这个栈。 它首先为_base和_top分配InitStackSize个SElemType大小的内存，并将_size设置为InitStackSize。

  析构函数: ~Stack()函数负责清理和释放由Stack对象持有的内存。 它首先删除_base指向的数组，然后将_base和_top设置为0，将_size设置为0。这是为了确保在对象销毁后，不会错误地引用任何内存地址。

  注意：数据结构的的实现是很灵活的，对于栈而言，顺序结构和链式结构都可以实现，当然，_base，_top等成员变量也可以设计成整型或者是指针，只要满足该数据类型的特征，就都可以设计。

template<class T>
class Stack
{//构造函数Stack(){_base = _top = new SElemType[InitStackSize];_size = InitStackSize;}//析构函数~Stack(){delete[] _base;_top = _base = nullptr;_size = 0;}private:SElemType* _base, * _top;int _size;
};

  
  入栈和扩容操作：

  我们现在实现栈最基本的入栈操作，首先创建一个Push函数，它用于将一个元素压入栈中。如果栈满了，它会进行扩容操作。

  如果 _top 指针和 _base 指针之间的距离等于 _size（这意味着栈已经满了），那么将进行扩容操作。扩容操作包括创建一个新的数组（大小为原数组的两倍），然后复制原数组的元素到新数组中。 最后，更新 _base 指针指向新数组，_top 指针指向新数组的末尾，_size 变为新数组的大小。

  入栈操作，如果栈没有满，那么将 val 的值赋给 _top 指针所指向的位置，并将 _top 指针向前移动一位。 最后，_size 加一。

void Push(const SElemType& val)
{//栈满，扩容if (_top - _base == _size){//转移栈中的元素SElemType* newbase = new SElemType[_size * 2];for (int i = 0; i < _size; i++){newbase[i] = _base[i];}//删除原来栈中元素delete[] _base;_base = newbase;_top = newbase + _size;_size *= 2;}//入栈操作*_top = val;_top++;_size++;
}

  
  出栈操作：

  我们现在实现出栈操作，先创建一个名为Pop的函数，用于从栈中删除并返回栈顶元素。

  函数声明：Pop(SElemType& e) 是一个函数，它接受一个类型为 SElemType 的引用作为参数，命名为 e。引用的使用意味着我们可以在函数内部修改传入的参数，而不仅仅是它的副本。

  栈检查：在函数体中，首先检查栈的大小（_size），如果为0，说明栈是空的。 此时，会打印一条消息 ‘该栈为空，无法删除\n’ 并结束函数。出栈操作：如果栈非空，我们执行出栈操作。首先，将栈顶元素的值赋给参数 e。然后，将 _top 指针向前移动一位（即向下移动到栈顶元素的前一个位置），因为我们已经取出了栈顶元素。最后，_size 减一，因为栈中少了一个元素。

  这样，Pop 函数就能够从栈中删除并返回栈顶元素，同时还能处理空栈的情况。

void Pop(SElemType& e)
{if (_size == 0){cout << "该栈为空，无法删除\n";return;}//出栈操作e = *_top;_top--;_size--;
}

  栈测试：

            

3.队列的实现（以顺序队列为例）

  队列的基本概念：

  队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。 和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

  
  队列的基本结构和初始化：

  我们定义了一个名为Queue的C++模板类，用于实现可以存储不同数据类型的队列数据结构。我们创建了四个成员变量：

  _base：这是一个指向队列元素的指针。

  _front：这是队列的头部索引。

  _rear：这是队列的尾部索引。

  _capacity：这是队列的容量。

  构造函数：Queue的构造函数初始化了队列的基础元素数组。将队列的前端和后端索引设为0，并将队列的容量设为 ‘QueueSize’。这个 ‘QueueSize’ 应该是在类外部定义的常数，表示队列的最大容量。

  析构函数：当 Queue 对象被销毁时，析构函数将被调用。 这个析构函数删除了队列的基础元素数组，将 _base 设为 nullptr，将队列的前端和后端索引设为0，并将队列的容量设为0。这是为了释放队列占用的内存，并重置队列的状态。

template<class T>
class Queue
{
public://构造函数Queue(){_base = new QElemType[QueueSize];_front = _rear = 0;_capacity = QueueSize;}//析构函数~Queue(){delete[] _base;_base = nullptr;_front = _rear = 0;_capacity = 0;}private:QElemType* _base;int _front, _rear;int _capacity;
};

  
  入队和扩容操作：

  我们现在实现队列的入队函数，用于将一个元素添加到队列中。

  if (_front == (_rear + 1) % _capacity): 这是一个判断语句，它检查队列是否已满。这里的_front，_rear和_capacity可能是队列的私有成员变量。其中_front代表队列的第一个元素的位置，_rear代表队列的最后一个元素的位置（下一个插入元素的位置），_capacity代表队列的最大容量。如果_front等于_rear + 1 % _capacity，这意味着队列的下一个位置（_rear）已经被占用了，即队列已满。

  扩容：QElemType* newqueue = new QElemType[_capacity * 2];: 如果队列已满，这段代码会创建一个新的、容量是原队列两倍的队列。for (int i = _front; i < _rear; i++): 这个循环复制原队列中从_front到_rear - 1的所有元素到新的队列中。delete[] _base;: 释放原队列所占用的内存。_base = newqueue;: 将新队列的指针赋值给_base，这样原队列的指针就指向了新的队列。然后更新队列的容量即可。

  入队： 就在队列的最后一个位置插入新的元素。更新队列的最后一个位置即可。如果增加后超过了队列的容量，则取模（%）操作会将其限制在队列的范围内（0到_capacity-1）。

  顺序队列的一些操作和判断：

  空队列判断条件： rear == front

  尾指针的移动方式： rear = (rear+1)%QueueSize

  头指针的移动方式： front=(front+1)%QueueSize

  判断队列满： front == (rear+1)%QueueSize

void Push(const QElemType& val)
{//判断队列是否已满if (_front == (_rear + 1) % _capacity){QElemType* newqueue = new QElemType[_capacity * 2];for (int i = _front; i < _rear; i++){newqueue[i] = _base[i];}//删除原来栈中元素delete[] _base;_base = newqueue;_capacity *= 2;}_base[_rear] = val;//如果想让队列超过QueueSize的长度，一定要%_capacity;_rear = (_rear + 1) % _capacity;
}

  
  出队操作：

  实现队列出队操作我们先判断队列是否为空， 它检查队列的前端（_front）和后端（_rear）是否相等。如果相等，这意味着队列为空，没有元素可以删除。则输出信息直接返回，不执行任何操作。

  如果队列不为空，这行代码将_base数组中索引为_front的元素赋值给引用参数e。这意味着，当你调用Pop函数时，通过引用参数e来获取被出队的元素。当元素被删除后，前端位置需要更新以指向下一个未被删除的元素。 这里使用模运算符（%）来确保前端位置在超过队列容量时回到队列的开始位置。

void Pop(QElemType& e)
{if (_front == _rear){cout << "队列为空，无法删除\n";return;}e = _base[_front];_front = (_front + 1) % _capacity;
}

  队列测试：

            

4.利用栈实现进制转换

  我们可以利用栈将一个十进制数转换为另一个进制数：

  函数首先声明了两个字符串变量s和table，以及两个整型量m和n。table是一个包含16个字符的字符串，用于表示16进制的数。

  然后函数要求用户输入要转换的十进制数m和目标进制数n。函数检查如果输入的数m为0，则直接输出0，因为0在任何进制下都等于0。

  接下来如果输入的数m为负数，则将其转换为正数，并标记flag为true，表示这个数之前是负数。然后我们创建了一个名为st的堆，利用堆的性质，可以存储转换后的字符。在while循环中，函数将输入的数m不断模以目标进制数n，取出每次的余数，将余数对应的字符从table中取出，并压入堆栈st中。 同时，更新输入的数m为原来的数除以目标进制数。

  如果之前标记过flag为true（即输入的数是负数），则在堆栈中压入一个’-'字符。最后，函数将堆栈中的所有字符取出并拼接到字符串s中，然后输出这个字符串。这个字符串就是转换后的数。

void Decimal_Conversion()
{string s, table = "0123456789ABCDEF";int m, n;cout << "请输入:m为输入的数,n为转换的进制\n";cout << "m=";cin >> m;cout << "n=";cin >> n;bool flag = false;if (m == 0) cout << "0";//如果是负数，则转成正数，并标记一下if (m < 0){m = 0 - m;flag = true;}Stack<char> st;//按进制换算成对应的字符添加到swhile (m){st.Push(table[m % n]);m /= n;}if (flag){st.Push('-');}while (!st.Empty()){s += st.Top();st.Pop();}cout << s << endl;
}

  测试：
  
10转化为2进制：1010

  
150转化为8进制：226

  
100001转化为16进制：186A1

            

5.利用队列解决约瑟夫环问题

  我们可以利用队列解决约瑟夫环问题。约瑟夫环：描述了一组共m个人围成一圈，从第n个人开始报数，报到m的人出列，然后从下一个人重新开始报数，直到所有的人都出列的问题。

  首先，函数向用户提示输入约瑟夫环的两个人数m和n。然后，使用队列que来模拟人们围成的圆圈。初始时，将1到m的人依次入队。使用一个计数器count，从1开始计数，每次循环都会增加1，直到达到目标n。

  如果计数器count小于目标n，表示当前人不需要出列，将队头元素取出（即这个人），从队列中删除（模拟这个人跳过），然后将这个元素重新插入队尾（这个人回到圆圈的尾部）。 然后，计数器count加1，为下一次循环做准备。

  如果计数器count等于目标n，表示当前人需要出列，将队头元素取出并打印（这个人是出列的人），然后从队列中删除这个元素（模拟这个人完全出列），然后将计数器count重置为1，继续下一轮循环。

  当队列为空时，说明所有的人已经出列，退出循环。

void Joseph_Exchange()
{cout << "约瑟夫环问题：请输入一共有m人，第n人出局:\n";int m, n;cout << "m=";cin >> m;cout << "n="; cin >> n;//填入队列中Queue<int> que;for (int i = 1; i <= m; i++){que.Push(i);}//计数器，计到目标就输入int count = 1;while (!que.Empty()){if (count < n){QElemType tmp = que.Head();que.Pop();que.Push(tmp);count++;}else if (count == n){cout << que.Head() << " ";que.Pop();count = 1;}}
}

  测试：

            

6.全部源码

Stack.h

#pragma once#define SElemType int
#define InitStackSize 100template<class T>
class Stack
{
public://构造函数Stack(){_base = _top = new SElemType[InitStackSize];_size = InitStackSize;}//析构函数~Stack(){delete[] _base;_top = _base = nullptr;_size = 0;}//入栈void Push(const SElemType& val){//栈满，扩容if (_top - _base == _size){//转移栈中的元素SElemType* newbase = new SElemType[_size * 2];for (int i = 0; i < _size; i++){newbase[i] = _base[i];}//删除原来栈中元素delete[] _base;_base = newbase;_top = newbase + _size;_size *= 2;}//入栈操作*_top = val;_top++;_size++;}//出栈void Pop(SElemType& e){if (_size == 0){cout << "该栈为空，无法删除\n";return;}//出栈操作e = *_top;_top--;_size--;}//重载出栈void Pop(){if (_size == 0){cout << "该栈为空，无法删除\n";return;}//出栈操作_top--;}//输出栈顶元素SElemType Top(){if (_base == _top){cout << "栈空，没有元素\n";return -1;}return *(_top - 1);}//判断栈空bool Empty(){if (_base == _top){return true;}else{return false;}}//打印栈中的元素void Print(){SElemType* cur = _base;if (_base == _top){cout << "该栈为空\n";return;}else{cout << "该栈中的元素为:";while (cur != _top){cout << *cur << " ";cur++;}cout << endl;}}private:SElemType* _base, * _top;int _size;
};

            

Queue.h

#pragma once#define QueueSize 100
#define QElemType inttemplate<class T>
class Queue
{
public://构造函数Queue(){_base = new QElemType[QueueSize];_front = _rear = 0;_capacity = QueueSize;}//析构函数~Queue(){delete[] _base;_base = nullptr;_front = _rear = 0;_capacity = 0;}//入队操作void Push(const QElemType& val){//判断队列是否已满if (_front == (_rear + 1) % _capacity){QElemType* newqueue = new QElemType[_capacity * 2];for (int i = _front; i < _rear; i++){newqueue[i] = _base[i];}//删除原来队列中元素delete[] _base;_base = newqueue;_capacity *= 2;}_base[_rear] = val;//如果想让队列超过QueueSize的长度，一定要%_capacity;_rear = (_rear + 1) % _capacity;}//出队操作void Pop(QElemType& e){if (_front == _rear){cout << "队列为空，无法删除\n";return;}e = _base[_front];_front = (_front + 1) % _capacity;}//重载出队操作void Pop(){if (_front == _rear){cout << "队列为空，无法删除\n";return;}_front = (_front + 1) % _capacity;}//输出队头元素QElemType Head(){if (_front == _rear){cout << "队列为空，无队头元素\n";return -1;}return _base[_front];}//判断是否为空队列bool Empty(){if (_front == _rear){return true;}else{return false;}}//打印队列中的元素void Print(){if (_front == _rear){cout << "该队列为空\n";return;}else{cout << "该队列中的元素为:";for (int i = _front; i < _rear; i++) {std::cout << _base[i] << " ";}cout << endl;}}private:QElemType* _base;int _front, _rear;int _capacity;
};

            

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
using namespace std;#include"Stack.h"
#include"Queue.h"void stack_test()
{Stack<int> st;st.Print();cout << "该栈是否为空:" << st.Empty() << endl;st.Push(1);st.Push(2);st.Push(3); st.Push(4);st.Print();cout << "栈顶元素为:" << st.Top() << endl;st.Pop();st.Pop();st.Print();cout << "该栈是否为空:" << st.Empty() << endl;st.Push(5);st.Push(6);st.Push(7);st.Push(8);st.Print();cout << "栈顶元素为:" << st.Top() << endl;st.Pop();st.Pop();st.Print();
}void queue_test()
{Queue<int> que;que.Print();cout << "该队列是否为空:" << que.Empty() << endl;que.Push(1);que.Push(2);que.Push(3);que.Push(4);que.Print();cout << "队头元素为:" << que.Head() << endl;que.Pop();que.Pop();que.Print();cout << "该队列是否为空:" << que.Empty() << endl;que.Push(5);que.Push(6);que.Push(7);que.Push(8);que.Print();cout << "队头元素为:" << que.Head() << endl;que.Pop();que.Pop();que.Print();
}void Decimal_Conversion()
{string s, table = "0123456789ABCDEF";int m, n;cout << "请输入:m为输入的数,n为转换的进制\n";cout << "m=";cin >> m;cout << "n=";cin >> n;bool flag = false;if (m == 0) cout << "0";//如果是负数，则转成正数，并标记一下if (m < 0){m = 0 - m;flag = true;}Stack<char> st;//按进制换算成对应的字符添加到swhile (m){st.Push(table[m % n]);m /= n;}if (flag){st.Push('-');}while (!st.Empty()){s += st.Top();st.Pop();}cout << s << endl;
}void Joseph_Exchange()
{cout << "约瑟夫环问题：请输入一共有m人，第n人出局:\n";int m, n;cout << "m=";cin >> m;cout << "n="; cin >> n;//填入队列中Queue<int> que;for (int i = 1; i <= m; i++){que.Push(i);}//计数器，计到目标就输入int count = 1;while (!que.Empty()){if (count < n){QElemType tmp = que.Head();que.Pop();que.Push(tmp);count++;}else if (count == n){cout << que.Head() << " ";que.Pop();count = 1;}}
}int main()
{//stack_test();//queue_test();//Decimal_Conversion();Joseph_Exchange();return 0;
}