数据结构

队列

基本队列
  1. 结构特点:元素先进先出。
  2. 关联算法:BFS
  3. 相关题目:图论、字符串相关问题
基本队列实现方法(链表法)
  1. 队列ADT

    typedef struct{
    QElement data;
    struct QNode * next;
    }QNode,*QueuePtr;

    typedef struct{
    QueuePtr front ;
    QueuePtr rear ;
    }LinkQueue;
  2. 初始化队列

    Status InitQueue(LinkQueue q)
    {
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next = nullptr;
    return OK;
    }
  3. 销毁队列

    Status DestroyQueue(LinkQueue &Q)
    {
    while(Q.front)
    {
    Q.rear = Q.front->next;
    free(Q.front);
    Q.front = Q.rear;
    }
    }
  4. 向队列添加元素

    Status EnQueue(LinkQueue & Q ,QElement e)
    {
    p = (QueuePtr)malloc(sizeof(QNode));
    if(!P) exit(OVERFLOW);
    p->data = e ;
    p->next = nullptr;
    Q.rear->next = p ;
    Q.rear = p;
    return OK;
    }
  5. 取出一个元素,并将其在队列中删除

    Status DeQueue(LinkQueue &Q ,QElement &e)
    {
    if(Q.front == Q.rear) return ERROR;
    p = Q.front->next;
    e = Q.front->data;
    Q.front->next = p->next;
    if(Q.rear == p) Q.rear = Q.front;
    free(p);
    return OK;
    }

循环队列

特点:循环利用空间,减少空间浪费

循环队列实现方法
  1. 初始化

    /** Initialize your data structure here. Set the size of the queue to be k. */    MyCircularQueue(int k) 
    {
    data = new int[k];
    head = 0;
    tail = 0;
    len = k;
    count = 0;
    }
  2. 向队列插入元素

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value)
    {
    if (isFull()) //循环队列满
    {
    return false;
    }
    else // 插入元素到队尾,队尾索引值增一,元素个数增一
    {
    data[tail] = value;
    count++;
    tail = (tail + 1) % len;
    return true;
    }
    }
  3. 从队列中取出元素

    /** Get the front item from the queue. */
    int Front()
    {
    if (isEmpty()) //循环队列空
    {
    return -1;
    }
    else
    {
    return data[head];
    }
    }
  4. 删除队列头元素

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue()
    {
    if (isEmpty()) //循环队列空
    {
    return false;
    }
    else // 队头索引值增一,元素个数减一
    {
    head = (head + 1) % len;
    count--;
    return true;
    }
    }
  5. 取出队尾元素

    int Rear() {
    if (isEmpty()) //循环队列空
    {
    return -1;
    }
    // 队尾元素位于队尾索引值减一的位置,但若队尾循环到索引 0 的位置,队尾元素位于数组最后
    else
    {
    int temp = tail == 0 ? (len-1) : (tail-1);
    return data[temp];
    }
    }
  6. 判断队列是否为空

    /** Checks whether the circular queue is empty or not. */
    bool isEmpty()
    {
    return count == 0; // 队列元素个数为零,队列空
    }
  7. 判断队列是否已满

    /** Checks whether the circular queue is full or not. */
    bool isFull()
    {
    return count == len; // 队列元素个数为数组最大长度,队列满
    }

C++队列使用方法

#include <queue>  
#include <cstdio>
using namespace std;
int main(int argc, char const *argv[])
{
queue<int> q ; //定义一个队列
q.push(23); //入队
q.size(); //返回队列大小
q.empty(); //判断队列为空
q.font(); //读取队头以及队尾元素
q.back();
q.pop(); //删除队首元素
return 0;
}

队列竞赛题参考

01矩阵

图像渲染

岛屿数量


未完待续

谢谢访问