該隊列是使用順序存儲方式進(jìn)行存儲的畴。
順序存儲方式類比于數(shù)組，直接分配一整塊連續(xù)的內(nèi)存進(jìn)行數(shù)據(jù)存儲尝胆。
@author:Kadima
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status; //用作函數(shù)值類型丧裁，表示函數(shù)結(jié)果狀態(tài)
typedef int ElemType;
//循環(huán)隊列:循環(huán)隊列為空的條件是Q.front==Q.rear,循環(huán)隊列為滿的條件是Q.front==(Q.rear+1)%Q.maxSize,即少用一個元素
typedef struct {
ElemType * elem; //存儲空間的基址
int front; //隊頭位標(biāo)
int rear; //隊尾位標(biāo)，指示隊尾元素的下一位置
int maxSize; //最大長度
} SqQueue;
/*1.初始化操作：構(gòu)造一個空隊列Q含衔，最大隊列長度為size*/
Status InitQueue_Sq(SqQueue &Q, int size){//構(gòu)造一個空隊列
Q.elem = (ElemType *)malloc(size*sizeof(ElemType));//分配存儲空間
if(NULL==Q.elem) return OVERFLOW;
Q.maxSize = size;
Q.front = Q.rear = 0;//置Q位空隊列
return OK;
}
/*2.出隊操作：若隊列不空則刪除當(dāng)前隊列Q中的頭元素煎娇，用e返回其值，并返回OK贪染；否則ERROR*/
Status DeQueue_Sq(SqQueue &Q, ElemType &e){
if(Q.front == Q.rear) return ERROR; //隊空報錯
e = Q.elem[Q.front];
Q.front = (Q.front + 1) % Q.maxSize;//Q.front循環(huán)加1
return OK;
}
/*3.入隊操作：在當(dāng)前隊列的尾元素之后插入元素e為新的尾元素*/
Status EnQueue_Sq(SqQueue &Q, ElemType e){
//若當(dāng)前隊列不滿缓呛，在隊列的尾元素之后，插入元素e為新的隊列尾元素
if((Q.rear + 1)%Q.maxSize==Q.front) return ERROR;
Q.elem[Q.rear] = e;
Q.rear = (Q.rear + 1) % Q.maxSize;
return OK;
}
/*銷毀隊列Q杭隙，Q不再存在*/
Status DestroyQueue_Sq(SqQueue &Q){
Q.front = Q.rear = 0; //置隊為空
Q.maxSize = 0;
free(Q.elem); //釋放指針指向的內(nèi)存
Q.elem = NULL; //把基址設(shè)為null,懸空哟绊。防止指針在后面不小心又被解引用了。
return OK;
}
/*將Q置為空隊列*/
void ClearQueue_Sq(SqQueue &Q){
Q.front = Q.rear = 0;
}
/*若隊列Q為空隊列則返回TRUE痰憎，否則FALSE*/
Status QueueEmpty_Sq(SqQueue Q){
if(Q.front == Q.rear)
return TRUE;
else
return FALSE;
}
/*返回隊列Q中的元素個數(shù)票髓，即隊列的長度*/
int QueueLength_Sq(SqQueue Q){
if(Q.rear >= Q.front)
return (Q.rear - Q.front);
else
return (Q.rear - Q.front + Q.maxSize); //Q.maxSize - (Q.front - Q.rear)
}
/*若隊列不空，則用e返回Q的隊列頭元素铣耘，并返回OK洽沟；否則ERROR*/
Status GetHead_Sq(SqQueue Q, ElemType &e){
if(Q.front == Q.rear)
return ERROR;
else{
e = Q.elem[Q.front];
return OK;
}
}
/*
車廂編號
假設(shè)隊列元素是char類型，'H'表示硬座蜗细，'S'表示軟臥裆操，隊列A表示一組硬座和臥鋪混編的車廂。
要求把隊列A中的硬座車廂移動到隊列B炉媒，隊列A中的臥鋪車廂移動到隊列C踪区，同時保留原有硬座車廂之間和軟臥車廂之間的先后順序不變。
*/
void Arrange(SqQueue A, SqQueue &B, SqQueue &C){
ElemType e; //書上是char類型橱野，但是我把ElemType用define定義為int型朽缴，故報錯
InitQueue_Sq(B, A.maxSize); //空的硬座隊列B
InitQueue_Sq(C, A.maxSize); //空的硬座隊列C
while(FALSE == QueueEmpty_Sq(A)){//依次處理隊列A中的每個車廂
DeQueue_Sq(A, e);
if(e == 'H') EnQueue_Sq(B, e);//加入硬座隊列B
else EnQueue_Sq(C, e);//加入軟臥隊列C
}
}
int main(){
SqQueue A, B, C;
char c[30];
int i = 0;
int n = 0;
ElemType e;
printf("輸入括號串:");
scanf("%s",c);
n = strlen(c);
InitQueue_Sq(A, n+1); //注意：此處記得要將字符串長度加1，因為隊列是少用一個元素空間來進(jìn)行判空的
for(i=0;i<n;i++){
EnQueue_Sq(A, c[i]);
}
Arrange(A, B, C);
printf("B隊列長度為:%d\n",QueueLength_Sq(B));
printf("B隊列:");
while(FALSE == QueueEmpty_Sq(B)){//依次處理隊列A中的每個車廂
DeQueue_Sq(B, e);
printf("%c",e);
}
printf("\n");
printf("C隊列長度為:%d\n",QueueLength_Sq(C));
printf("C隊列:");
while(FALSE == QueueEmpty_Sq(C)){//依次處理隊列A中的每個車廂
DeQueue_Sq(C, e);
printf("%c",e);
}
printf("\n");
return 0;
}
