循环队列的基本操作:
- #include<stdio.h>
- #include<stdlib.h>
- #define maxSize 20
- typedef int QElemType;
- typedef struct
- {
- QElemType elem[maxSize];
- int front,rear;
- }CircQueue;
- void InitQueue(CircQueue *Q) // 初始化队列
- {
- Q->front=Q->rear=0;
- }
- int EnQueue(CircQueue *Q,QElemType x) // 进队列
- {
- if((Q->rear+1)%maxSize==Q->front)
- {
- return 0;
- }
- Q->elem[Q->rear]=x;
- Q->rear=(Q->rear+1)%maxSize;
- return 1;
- }
- int DeQueue(CircQueue *Q,QElemType *x) // 出队列
- {
- if(Q->front==Q->rear)
- {
- return 0;
- }
- *x=Q->elem[Q->front];
- Q->front=(Q->front+1)%maxSize;
- return 1;
- }
- int QueueSize(CircQueue *Q) // 求对列长度
- {
- return (Q->rear-Q->front+maxSize)%maxSize;
- }
- int QueueEmpty(CircQueue *Q) // 判断队列空否
- {
- return Q->front==Q->rear;
- }
- int QueueFull(CircQueue *Q) // 判断队列满否
- {
- return (Q->rear+1)%maxSize==Q->front;
- }
- int GetFront(CircQueue *Q,QElemType *x) // 读取队头
- {
- if(Q->front==Q->rear)
- {
- return 0;
- }
- *x=Q->elem[Q->front];
- return 1;
- }
1. 返回循环队列中最小元素的值的位置:
- int FindMin(CircQueue *Q)
- {
- int locate=-1; //locate 为最小元素的位置, 物理位置
- int x,n=QueueSize(Q);
- int min;
- GetFront(Q,&min);
- for(int i=0;i<n;i++) // 遍历队列
- {
- DeQueue(Q,&x);
- if(min>x)
- {
- min=x;
- locate=i;
- }
- EnQueue(Q,x);
- }
- return locate;
- }
2. 借助空栈将循环队列元素逆置
所需顺序栈的基本操作:
- typedef int SElemType;
- typedef struct
- {
- SElemType *elem;
- int maxsize,top;
- }SeqStack;
- void StackInit(SeqStack *S) // 初始化栈
- {
- (*S).elem=(SElemType *)malloc(maxSize*sizeof(SElemType));
- if(S->elem==NULL)
- {
- printf("存储分配错误!\n");
- exit(1);
- }
- S->maxsize=maxSize;
- S->top=-1;
- }
- int StackPush(SeqStack *S,SElemType x) // 进栈
- {
- if(S->top==S->maxsize-1)
- {
- return 0;
- }
- S->elem[++S->top]=x;
- return 1;
- }
- int StackPop(SeqStack *S,SElemType *x) // 出栈
- {
- if(S->top==-1)
- {
- return 0;
- }
- *x=S->elem[S->top--];
- return 1;
- }
队列逆置:
- void QueueReverse(CircQueue *Q)
- {
- int x,n=QueueSize(Q);
- SeqStack S;
- StackInit(&S);
- for(int i=0;i<n;i++)
- {
- DeQueue(Q,&x);
- StackPush(&S,x);
- }
- for(int i=0;i<n;i++)
- {
- StackPop(&S,&x);
- EnQueue(Q,x);
- }
- }
- void QStackInit(CircQueue *Q1,CircQueue *Q2) // 初始化模拟栈
- {
- InitQueue(Q1);
- InitQueue(Q2);
- }
- bool QStackEmpty(CircQueue *Q1,CircQueue *Q2) // 判断模拟栈空否
- {
- return QueueEmpty(Q1)&&QueueEmpty(Q2);
- }
- bool QStackFull(CircQueue *Q1,CircQueue *Q2) // 判断模拟栈满否
- {
- return QueueFull(Q1)||QueueFull(Q2);
- }
- bool QStackPush(CircQueue *Q1,CircQueue *Q2,int x) // 进入模拟栈
- {
- if(QStackFull(Q1,Q2))
- {
- return false;
- }
- if(QStackEmpty(Q1,Q2))
- {
- EnQueue(Q1,x);
- }
- else if(!QueueEmpty(Q1))
- {
- EnQueue(Q1,x);
- }
- else
- {
- EnQueue(Q2,x);
- }
- return true;
- }
- bool QStackPop(CircQueue *Q1,CircQueue *Q2,int *x) // 出模拟栈
- {
- if(QStackEmpty(Q1,Q2))
- {
- return false;
- }
- if(!QueueEmpty(Q1))
- {
- while(1)
- {
- DeQueue(Q1,x);
- if(!QueueEmpty(Q1))
- {
- EnQueue(Q2,*x);
- }
- else
- {
- break;
- }
- }
- }
- else
- {
- while(1)
- {
- DeQueue(Q2,x);
- if(!QueueEmpty(Q2))
- {
- EnQueue(Q1,*x);
- }
- else
- {
- break;
- }
- }
- }
- return true;
- }
- int main()
- {
- CircQueue Q1,Q2;
- InitQStack(&Q1,&Q2);
- int x,i,result=0;
- printf("请输入一个十进制数:\n");
- scanf("%d",&x);
- while(x!=0)
- {
- i=x%2;
- x=x/2;
- QStackPush(&Q1,&Q2,i);
- }
- while(!QStackEmpty(&Q1,&Q2))
- {
- QStackPop(&Q1,&Q2,&i);
- result=result*10+i;
- }
- printf("二进制为:%d\n",result);
- }
来源: http://www.bubuko.com/infodetail-3041295.html