浅谈【数据结构】栈和队列之队列
目录
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;
}