数据结构之队列

简介: 给大家分享一下数据结构吧

特点——先进先出:


只允许一端进行插入操作,另一端进行删除操作的 线性表


插入一段是队尾,删除的一端是队头


存储方式——顺序存储和链式存储


顺序存储

顺序存储用数组实现


假设有N个元素的一个队列,数组下标为0的一端是对头,入队操作就是通过数组下标一个个顺序追加,不需要移动元素,如果删除对头元素,后面的元素就要往前移动,这种方式性能不高


顺序队列的实现代码如下:


public class ArrayQueue {

   private Array<E> data;

   public ArrayQueue(){

       this.data = new DynamicArray();

   }

   public boolean isEmpty() {

       return data.isEmpty();

   }

   public int size() {

       return data.size();

   }

   public void enqueue(E e) {

       data.add(e);

   }

   public E dequeue() {

       return data.remove(0);

   }

   public E head() {

       return data.get(0);

   }

   @Override

   public String toString() {

       return "Head " + data.toString() + " Tail";

   }    

}


为了提高队的性能,于是出现了循环队列


循环队列



就是有两个指针,front指向队头,rear指向对尾元素的下一个位置


元素出队时front往后移动,如果到了对尾则转到头部,同理入队时rear后移,如果到了对尾则转到头部,这样通过下标front出队时,就不需要移动元素了


循环操作rear依次后移,然后再从头开始,出现rear和front相等时,队列满


注意(当队列为空时,front和rear相等       当队列为满时,front和rear也相等)


为了区分这种情况,规定数组还有一个空闲单元时,就表示队列已满


因为rear 可能在front后面,也可能循环到front前面,所以队列满的条件就变成了(rear+1)%maxsize = front ,同时队列元素个数的计算就是(rear -front+maxsize)%maxsize


循环队列的实现代码如下:


public class LoopQueue<E> {

   private E[] data;

   private int size;

   private int tail;

   private int head;

   public LoopQueue(){

       this(8);

   }

   public LoopQueue(int capcaity) {

       this.data = (E[]) new Object[capcaity + 1];

       this.head = 0;

       this.tail = 0;

       this.size = 0;

   }

   public int size() {

       return size;

   }

   public boolean isEmpty() {

       return size == 0;

   }

   public void enqueue(E e) {

       if((tail + 1) % data.length == head % data.length){

           resize(data.length * 2);

       }

       data[tail] = e;

       tail = (tail + 1)% data.length;

       size++;

   }

   public E dequeue() {

       if(tail == head){

           return null;

       }

       E e = data[head];

       head = (head + 1)% data.length;

       size--;

       if(size == data.length / 4 && data.length / 2 != 0){

           resize(data.length / 2);

       }

       return e;

   }

   public E head() {

       return data[head];

   }

   private void resize(int newCapcaity){

       E[] newData = (E[])new Object[newCapcaity + 1];

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

           newData[i] = data[(i + head) % data.length];

       }

       head = 0;

       tail = size;

       data = newData;

   }

   @Override

   public String toString() {

       StringBuilder sBuilder = new StringBuilder();

       sBuilder.append("Head ");

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

           sBuilder.append(data[(i + head) % data.length]).append(",");

       }

       int lastIndex = sBuilder.lastIndexOf(",");

       if(lastIndex != -1){

           sBuilder.deleteCharAt(lastIndex);

       }

       sBuilder.append(" Tail");

       return sBuilder.toString();

   }


温馨提示:


循环队列要事先申请好空间,整个过程都不能释放,而且要有固定的长度


链式列表:

由于循环队列不够灵活,于是引入了链式存储队列,即线性表的单链表


它只能对尾进,队头出,并且规定队头指针指向链队列的头结点,对尾指针指向终端节点


当队列为空时,front和rear都指向头结点



具体实现代码如下:


#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define MAXSIZE 20

typedef int Status;

typedef int QElemType;

//结点结构

typedef struct QNode{

QElemType data;

struct QNode *next;

}QNode,*QueuePtr;

//队列的链表结构


目录
打赏
0
0
0
0
3
分享
相关文章
|
2月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
284 9
|
12天前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
128 75
|
3月前
|
数据结构之 - 双端队列数据结构详解: 从基础到实现
数据结构之 - 双端队列数据结构详解: 从基础到实现
136 5
|
12天前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
34 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
12天前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
35 9
|
12天前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
29 7
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
87 5
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
3月前
初步认识栈和队列
初步认识栈和队列
68 10
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
39 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等