数据结构&算法 队列



  • 队列

    队列是一种抽象的数据结构,有点类似于堆栈。与堆栈不同,队列的两端都是打开的。一端始终用于插入数据(入队),另一端用于删除数据(出队)。队列遵循先进先出的方法,即首先存储的数据项将首先被访问。
    队列的真实示例可以是单车道单向道路,车辆首先进入,然后首先离开。在售票窗口和公交车站的队列中,可以看到更多实际示例。
  • 队列表示

    现在我们知道在队列中,出于不同的原因访问两端。下面给出的下图试图将队列表示解释为数据结构-
    与在堆栈中一样,也可以使用数组,链接列表,指针和结构来实现队列。为了简单起见,我们将使用一维数组实现队列。
  • 基本操作

    队列操作可能涉及初始化或定义队列,利用它,然后从内存中完全擦除它。在这里,我们将尝试了解与队列相关的基本操作-
    • enqueue() -向队列添加(存储)项目。
    • dequeue() -从队列中删除(访问)一个项目。
    需要很少的功能来使上述队列操作高效。这些是-
    • peek -在队列的最前面获取元素而不删除它。
    • isfull -检查队列是否已满。
    • isempty -检查队列是否为空。
    在队列中,我们总是使前指针所指向的数据出队(或访问),而在队列中将数据入队(或存储)时,我们会使用后指针。首先让我们了解队列的支持函数-
    peek()
    此功能有助于查看队列前面的数据。peek()函数的算法如下-
    
    begin procedure peek
       return queue[front]
    end procedure
    
    
    用C编程语言实现peek()函数-
    
    int peek() {
       return queue[front];
    }
    
    
    isfull()
    当我们使用单维数组实现队列时,我们只需检查后指针达到MAXSIZE即可确定队列已满。如果我们将队列维护在循环链表中,则算法将有所不同。isfull()函数的算法-
    
    begin procedure isfull
    
       if rear equals to MAXSIZE
          return true
       else
          return false
       endif
       
    end procedure
    
    
    用C编程语言实现isfull()函数-
    
    bool isfull() {
       if(rear == MAXSIZE - 1)
          return true;
       else
          return false;
    }
    
    
    isempty()
    isempty()函数的算法-
    
    begin procedure isempty
    
       if front is less than MIN  OR front is greater than rear
          return true
       else
          return false
       endif
       
    end procedure
    
    
    如果front的值小于MIN或0,则表明队列尚未初始化,因此为空。
    用C编程语言实现isempty()函数-
    
    bool isempty() {
       if(front < 0 || front > rear) 
          return true;
       else
          return false;
    }
    
    
  • 入队操作

    队列维护两个数据指针,前和后。因此,它的操作比堆栈的实现相对困难。应该采取以下步骤将数据排队(插入)到队列中-
    • 步骤1-检查队列是否已满。
    • 步骤2-如果队列已满,则产生溢出错误并退出。
    • 步骤3-如果队列未满,请增加后指针以指向下一个空白空间。
    • 步骤4-将数据元素添加到后方指向的队列位置。
    • 步骤5-返回成功。
    有时,我们还会检查队列是否已初始化,以处理任何无法预料的情况。
    入队操作算法
    
    procedure enqueue(data)      
       
       if queue is full
          return overflow
       endif
       
       rear ← rear + 1
       queue[rear] ← data
       return true
       
    end procedure
    
    
    enqueue()在C编程语言中的实现--
    
    int enqueue(int data)      
       if(isfull())
          return 0;
       
       rear = rear + 1;
       queue[rear] = data;
       
       return 1;
    end procedure
    
    
  • 出队操作

    从队列访问数据是两个任务的过程-访问前端指向的数据并在访问后删除数据。采取以下步骤执行出队操作-
    • 步骤1-检查队列是否为空。
    • 步骤2-如果队列为空,则产生下溢错误并退出。
    • 步骤3-如果队列不为空,请访问front指向的数据。
    • 步骤4-递增前指针以指向下一个可用的数据元素。
    • 步骤5-返回成功。
    出队操作算法
    
    procedure dequeue
       
       if queue is empty
          return underflow
       end if
    
       data = queue[front]
       front ← front + 1
       return true
    
    end procedure
    
    
    用C编程语言实现dequeue()-
    
    int dequeue() {
       if(isempty())
          return 0;
    
       int data = queue[front];
       front = front + 1;
    
       return data;
    }
    
    
  • 队列在C中完整实现

    我们将在这里看到用C编程语言实现的堆栈实现。
    
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    #define MAX 6
    
    int intArray[MAX];
    int front = 0;
    int rear = -1;
    int itemCount = 0;
    
    int peek() {
       return intArray[front];
    }
    
    bool isEmpty() {
       return itemCount == 0;
    }
    
    bool isFull() {
       return itemCount == MAX;
    }
    
    int size() {
       return itemCount;
    }  
    
    void insert(int data) {
    
       if(!isFull()) {
      
          if(rear == MAX-1) {
             rear = -1;            
          }       
    
          intArray[++rear] = data;
          itemCount++;
       }
    }
    
    int removeData() {
       int data = intArray[front++];
      
       if(front == MAX) {
          front = 0;
       }
      
       itemCount--;
       return data;  
    }
    
    int main() {
       /* insert 5 items */
       insert(3);
       insert(5);
       insert(9);
       insert(1);
       insert(12);
    
       // front : 0
       // rear  : 4
       // ------------------
       // index : 0 1 2 3 4 
       // ------------------
       // queue : 3 5 9 1 12
       insert(15);
    
       // front : 0
       // rear  : 5
       // ---------------------
       // index : 0 1 2 3 4  5 
       // ---------------------
       // queue : 3 5 9 1 12 15
      
       if(isFull()) {
          printf("Queue is full!\n");   
       }
    
       // remove one item 
       int num = removeData();
      
       printf("Element removed: %d\n",num);
       // front : 1
       // rear  : 5
       // -------------------
       // index : 1 2 3 4  5
       // -------------------
       // queue : 5 9 1 12 15
    
       // insert more items
       insert(16);
    
       // front : 1
       // rear  : -1
       // ----------------------
       // index : 0  1 2 3 4  5
       // ----------------------
       // queue : 16 5 9 1 12 15
    
       // As queue is full, elements will not be inserted. 
       insert(17);
       insert(18);
    
       // ----------------------
       // index : 0  1 2 3 4  5
       // ----------------------
       // queue : 16 5 9 1 12 15
       printf("Element at front: %d\n",peek());
    
       printf("----------------------\n");
       printf("index : 5 4 3 2  1  0\n");
       printf("----------------------\n");
       printf("Queue:  ");
      
       while(!isEmpty()) {
          int n = removeData();           
          printf("%d ",n);
       }   
    }
    
    
    如果我们编译并运行上述程序,它将产生以下结果-
     
    Queue is full!
    Element removed: 3
    Element at front: 5
    ----------------------
    index : 5 4 3 2 1 0
    ----------------------
    Queue: 5 9 1 12 15 16