在循环队列中插入和删除元素

Question

我正在研究数据结构中的循环队列。从下面的代码中可以看出，我尝试删除特定数据并将数据插入循环队列。但是，当我尝试运行时，删除数据并插入新数据时出现问题。我对此一无所知。我试图解决这个问题很多个小时，但我找不到任何东西。任何帮助将不胜感激。

#include <stdio.h>
#define SIZE 3

typedef struct queue{
    int val[SIZE]={NULL};
    int front;
    int rear;
}queue;
void display(struct queue *q);
void enqueue(struct queue *q){
    int ins,i=1;
    if((q->rear == SIZE-1 && q->front == 0) || (q->rear == q->front-1)){
        printf("Queue is full!\n");
    }
    else if (q->front == -1)
    { 
        printf("Enqueue data : ");
        scanf("%d",&ins);
        q->front = q->rear = 0; 
        q->val[q->rear] = ins; 
    }
    else if (q->rear == SIZE-1) 
    { 
        printf("Enqueue data : ");
        scanf("%d",&ins);
        q->rear = 0; 
        q->val[q->rear] = ins; 
    }   
    else
    {   
        printf("Enqueue data : ");
        scanf("%d",&ins);
        q->rear++; 
        q->val[q->rear] = ins; 
    } 
    display(q);
};

void dequeue(struct queue *q);
int main(){
    queue *q= new queue;
    q->front = -1;
    q->rear = -1;
    char select;
flag1:
    printf("\n------- Please Select Operations ---------\n");
    printf("Press e: Enqueue\n"); 
    printf("Press d: Dequeue\n");   
    printf("Press x: Exit Program\n");                   
    printf("------------------------------------------\n");
    printf("Select Menu : ");
    scanf(" %c",&select);
    switch(select){
        case 'e' : enqueue(q); goto flag1;
        case 'd' : dequeue(q); goto flag1;
        case 'x' : break;
    }
    
 return 0;  
}

void dequeue(struct queue *q){
    int deq,hold;
    if (q->front == -1) 
    { 
        printf("Queue is Empty"); 
    } 
    else
    {
     printf("Dequeue data : ");
     scanf("%d",&deq);
     for(int i=0;i<SIZE;i++){
        if(deq==q->val[i]){
           if(i==q->front){
            q->val[q->front]=NULL;
            q->front = i;
            q->rear=q->rear+1;
            if(q->rear=SIZE-1){
                q->rear=0;
               }
           }
           else
            q->val[q->front]=NULL;
        }   
    }
    display(q);
}
};

void display(struct queue *q){
    int i;
    printf("Queue : |");
    for (i= 0; i<SIZE; i++){
        if(q->val[i]==NULL){
        printf(" |");   
        }
        else
        printf("%d|", q->val[i]);
    }
};

Answer 1

加油！
您的代码过于复杂。
复杂的代码需要复杂的测试和调试。

试试下面的代码：

void enqueue( struct queue *q, int v) {
    int r = (q.rear + 1) % SIZE
    if(( r == q.front) {
        printf( "Queue is full!\n");
    } else {
        q.val[ q.rear] = v;
        q.rear = r;
    }
};

int dequeue( struct queue *q) {
    if( q.front == q.rear) {
        printf( "Queue is Empty");
        v = NULL; # or whatever (required as a return value)
    } else {
        v = q.val[ q.front];
        q.front = ( q.front + 1) % SIZE;
    }
    return v;
};

int main() {
    queue *q = new queue;
    q->front = q->rear = 0;
    ...
};

总结一下：

rear 是最年轻元素的索引
前面是最旧元素的索引
%（模运算符）负责索引覆盖。
(front == rear) 表示空缓冲区
((rear +1) % SIZE == front) 表示满缓冲区。

请注意，这个简单的算法总是在缓冲区中留下未使用的元素。这是区分“满”和“空”所必需的。

Answer 2

您的代码过于复杂且笨拙。我觉得你对循环队列不是很了解

这是我的简化代码。大家可以去看看，学习一下。

#include<stdio.h>
#include<stdlib.h>

typedef struct _node {
    int size,front,rear,*q;
} node;

node *pu;

void initialize() {
    if(pu!=NULL)
        free(pu);
    pu = (node *)malloc(sizeof(node));
    printf("\nEnter the size of the queue :- ");
    scanf(" %d",&pu->size);
    pu->q = (int *)malloc(sizeof(int) * pu->size +1);
    pu->front = pu->rear = 0;
}

int isempty() {
    return (pu->front == pu->rear);
}

int isfull() {
    return ((pu->rear + 1) % pu->size == pu->front);
}

void enqueue(int x) {
    if(isfull())
        return;
    else {
        pu->q[pu->rear=(pu->rear +1) % pu->size] = x;
    }
}

int dequeue() {
    if(isempty())
        return '$';
    else {
        return pu->q[ pu->front = (pu->front + 1) % pu->size];
    }
}

void display() {
    if(isempty())
        return;
    else {
        for( int i = pu->front + 1; i != (pu->rear +1)%pu->size ; i = ( i +1) % pu->size)
            printf("\n %d",pu->q[i]);
    }
}

int main() {
    // do something in here with the functions.
    return 0;
}

Answer 3

循环队列 Java

public class CircularQueue<T> {

    private Object[] arr;
    private int front = -1, rear = -1;

    public CircularQueue(int initialCapacity) {
        this.arr = new Object[initialCapacity];
    }

    public void add(T val) throws Exception {
        if (isEmpty()) {
            rear++;
            front++;
        } else if (isFull()) {
            throw new Exception("Queue is full");
        }
        arr[rear] = val;
        rear = (rear + 1) % arr.length;
    }

    public T delete() throws Exception {
        if (isEmpty()) {
            throw new Exception("No elements in Queue");
        }
        T temp = (T) arr[front];
        front = (front + 1) % arr.length;
        return temp;
    }

    public boolean isEmpty() {
        return (front == -1 && rear == -1);
    }

    public boolean isFull() {
        return (front == rear);
    }

    @Override
    public String toString() {
        String ret = "[ ";
        int temp = front;
        do {
            ret += arr[temp] + " ";
            temp = (temp + 1) % arr.length;
        } while (temp != rear);
        ret += "]";
        return ret;
    }

}

在循环队列中插入和删除元素

Insert and Delete element on Circular Queue

c

queue

data-structures

circular-queue