队列的链式存储结构的实现

川长思鸟来 2023-10-05 17:15 2阅读 0赞

队列的链式存储结构的实现  
(1) 用随机函数生成10个3位整数(100~999)，把这些整数应用入队操作存于队列中；  
(2) 应用遍历操作输出队列的内容；  
(3) 把队列的内容翻转，应用出队操作输出队列的内容。

#include <iostream>
    #include<ctime>
    #include<stack>
    using namespace std;
    struct queue
    {
        
        int data;
        queue* next;
    };
    struct queptr
    {
        
        queue* front;//队首头结点
        queue* rear;//队尾
    };
    void init(queptr& q)//初始化队列指针
    {
        
        q.front = new queue;
        q.rear = q.front;
        q.front->next = NULL;
    }
    
    void push(queptr& q, int data)//数据压入队尾
    {
        
        queue* tmp = new queue;
        tmp->data = data;
        tmp->next = NULL;//新建一个队列指针
        q.rear->next = tmp;//将队尾的next连接到添加节点
        q.rear = q.rear->next;//队尾移到新添加节点
    }
    int pop(queptr& q)//弹出队首元素并返回值
    {
        
        if (q.front == q.rear) {
         cout << "队列为空" << endl; return -1; }//队列为空
        queue* tmp = q.front->next;
        int data = tmp->data;
        q.front->next = tmp->next;//将队列头结点指向下一个结点
        if (q.rear == tmp) q.rear = q.front;//如果删除的为最后一个结点，队列空，队尾置为队首
        free(tmp);
        return data;
    }
    
    int main()
    {
        
        srand(unsigned int(time(0)));
        queptr q;//创建队列指针
        stack<int> s;//利用栈后进先出的特性来翻转队列
        init(q);//初始化队列
        for (int i = 0; i < 10; i++)
        {
        //生成随机数并压入队列
            int data = rand() % 899 + 100;
            push(q, data);
        }
        cout << "队列的遍历数据如下\n";
        for (int i = 0; i < 10; i++)//遍历队列所有数据
        {
        
            int data = pop(q);
            cout << data << endl;
            s.push(data);
        }
        while (!s.empty())//翻转数据并压入队列
        {
        
            push(q, s.top());
            s.pop();
        }
        cout << "队列翻转后输出内容\n";
        for (int i = 0; i < 10; i++)//遍历输出数据
        {
        
            cout << pop(q) << endl;
        }
    }