当前位置: 首页> 汽车> 行情 > 浅谈【数据结构】栈和队列之队列

浅谈【数据结构】栈和队列之队列

时间:2025/7/12 7:06:29来源:https://blog.csdn.net/weixin_67526434/article/details/141530959 浏览次数: 0次

目录

1、队列

1.1思想

2、队列的两类

2.1顺序队列

2.2链式队列


谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注

没错,说的就是你,不用再怀疑!!!

希望我的文章内容能对你有帮助,一起努力吧!!!


1、队列

1.1思想

  • 先进先出,后进后出
  • 例如:排队买奶茶
    • 入队:队伍新增一个来买奶茶的人。(应当要排在队伍最后面)
    • 出队:有一个一个买到了奶茶离开队伍。(应当是队伍第一个人)

2、队列的两类

2.1顺序队列

  • 数组+整型===>结构体

struct queue {

        int head; // 表示队头

        int tail; // 表示队尾

        ElementType queue[MAXLENG]; // 数组:表示队列的空

};

  • 地址是连续
  • 循环队列解决无法回到起点问题
  • 循环队列存在一个空间会浪费
    • 解决:在结构体再定义一个长度

示例代码:

#include <iostream>#define QUEUEERR 0xefffff
#define MAX 10
/*为空:head和tail相等的时候为满:tail减head等于10的时候head:指向已出元素的位置tail:指向待入队元素的位置
*/
typedef struct Queue
{int length;int head;int tail;int q[MAX];
}Queue;Queue *createSeqQueue()
{Queue *q = new Queue;// 初始化为空q->head = 0;q->tail = 0;return q;
}/*@brief 入队@param queue 需要入队的队列指针@param data 需要入队的数据@return 成功返回true,失败返回false
*/
bool push_data(Queue *queue, int data)
{std::cout << "tail:" <<queue->tail << std::endl;// 判断队列是否是满的if((queue->tail+1)%MAX==queue->head) // 就是判断下一个位置是不是headreturn false;// 重置下标queue->tail = (queue->tail+1)%MAX;queue->q[queue->tail] = data;return true;
}/*@brief 出队@param queue需要出队的队列指针@return 成功返回出队的元素,失败返回QUEUEERR
*/
int pop_data(Queue *queue)
{// 判断队列是否空了/*if(queue->head == queue->tail-1) // 越界非常严重return QUEUEERR;*/ std::cout << "head:" << queue->head << std::endl;if(queue->tail == queue->head)return QUEUEERR;int data = queue->q[queue->head];queue->head = (queue->head+1)%MAX;return data;
}int main()
{Queue *queue = createSeqQueue();// 存元素for(int i = 1;i <= 20;i ++){if(push_data(queue,i))std::cout << "存入" << i << "个" << std::endl;else break;}std::cout << queue->tail << std::endl;while(1){int data = pop_data(queue);if(data == QUEUEERR)break;std::cout << data << std::endl;}return 0;
}

2.2链式队列

带头结点的单链表实现

示例代码:

#include <iostream>#define QUEUEERR 0xefffffstruct node 
{int data;struct node *next;
};struct head
{struct node *first;struct node *final;
};struct head *createListQueue()
{struct head *queue = new struct head;queue->final = nullptr;queue->first = nullptr;return queue;
}/*头插
*/
void push_data(struct head *queue,int data)
{if(!queue)return;struct node *node_ptr = new struct node;node_ptr->data = data;node_ptr->next = queue->first;queue->first = node_ptr;// 作为第一个结点插入的时候if(queue->final == nullptr)queue->final = node_ptr;
}/*尾取
*/
int pop_data(struct head*queue)
{if(!queue)return QUEUEERR;if(queue->first == nullptr)return QUEUEERR;if(queue->first == queue->final){int data = queue->final->data;queue->first = nullptr;queue->final = nullptr;return data;}int data = queue->final->data;struct node *node_ptr = queue->final;queue->final = queue->first;// 更新队列final指针while(queue->final->next != node_ptr)queue->final = queue->final->next;return data;
}int main()
{struct head *queue = createListQueue();std::cout << __LINE__ << std::endl;push_data(queue,5);push_data(queue,4);push_data(queue,3);push_data(queue,2);push_data(queue,1);push_data(queue,0);std::cout << pop_data(queue) << std::endl;std::cout << pop_data(queue) << std::endl;std::cout << pop_data(queue) << std::endl;while(1){int data = pop_data(queue);if(data == QUEUEERR)break;std::cout << data << std::endl;}return 0;
}

关键字:浅谈【数据结构】栈和队列之队列

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: