隊列的鏈?zhǔn)酱鎯Υa實現(xiàn)

//帶頭節(jié)點 Q.front->next才指向第一個元素
typedef struct QNode{
  ElemType data;
  struct QNode *next;
}QNode, *QueuePtr;

typedef struct{
  QueuePtr front;
  QueuePtr rear;
}LinkQueue;

void InintQueue(LinkQueue &Q)
{
  Q.front = Q.rear = (QNode*)malloc(sizeof(QNode))
  Q.front->next = NULL;
}

bool EmptyQueue(LinkQueue &Q)
{
  return (Q.front == Q.rear);
}

Status EnQueue(LinkQueue &Q, ElemType x)
{
  QNode *p = (QNode*)malloc(sizeof(QNode));
  p->data = x;
  p->next = NULL;
  Q.rear->next = p;
  Q.rear = p;
  return OK;
}

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

ElemType GetHead(LinkQueue Q)
{
  if(Q.front->next == NULL)
    return NULL;
  return Q.front->next->data;
}

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

typedef struct{
  QueuePtr front;
  QueuePtr rear;
}LinkQueue;

//不帶頭節(jié)點 頭指針是直接指向第一個隊頭元素
void InitQueue(LinkQueue &Q)
{
  Q.front = Q.rear = NULL;
}

bool EmptyQueue(LinkQueue &Q)
{
  return (Q.front == NULL);
}

Status EnQueue(LinkQueue &Q, ElemType x)
{
  QNode *p = (QNode*)malloc(sizeof(QNode));
  p->data = x;
  p->next = NULL;
  if(Q.front == NULL)
  {
    Q.front = p;
    Q.rear = p;
  }
  Q.rear->next = p;
  Q.rear = p;
}

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

ElemType GetHead(LinkQueue Q)
{
  if(Q.front != NULL)
    return Q.front->data;
  return NULL;
}

隊列的具體應(yīng)用

1. 計算八進制

void conversion(int N)
{
	Stack S;
	InitStatck(S);
	while(N>0)
	{
		push(S, N % 8);
		N /= 8;
	}
	while(!EmptyStack(S))
	{
		cout << Pop(S) << endl;
	}
}

2. 括號匹配

bool matching(char a[], int len)
{
	Stack S;
	InitStack(S);
	for(int i = 0; i < len; i++)
	{
		if(a[i] == '(' || a[i] == '[' || a[i] == '{')
			push(S, a[i]);
		else
		{
			if(EmptyStack(S))
				return false
			e = GetTop(S);
			if(e == '(' && a[i] == ')' || e == '[' && a[i] == ']'|| e == '{' && a[i] == '}')
			{
				Pop(S);
			}
			else
				return false;
		}
	}
	if(!EmptyStack(S))
		return false;
	return true;
}

4.表達式計算

規(guī)則：
1.遇到操作數(shù)直接加入操作數(shù)棧中 
2.遇到運算符：運算符棧頂元素 和 當(dāng)前運算符 進行優(yōu)先級比較
	1.運算符棧頂元素 >= 當(dāng)前運算符 彈出運算符棧 操作數(shù)棧彈出最上層的兩個棧頂元素進行改彈出運算符的運算并將結(jié)果放回操作數(shù)棧中，依次繼續(xù)和棧頂元素進行比較，比出來<就停止
	2.運算符棧頂元素 < 當(dāng)前運算符 棧頂元素繼續(xù)呆在運算符棧
都要將當(dāng)前運算符入棧
3.遇到括號界定符：
	1. 遍歷到“(”入棧
	2. 遍歷到“)”，彈出運算符，并彈出最上層的兩個棧頂元素進行運算并將結(jié)果放回操作數(shù)棧中，直到彈出“)”

//NUM 操作數(shù)棧 OPR運算符棧
char EvaluateExpression()
{
	Push(OPR,'#')
	cin >> ch;
	while(ch != '#' && GetTop(OPR) != '#')\
	{
		if(!operators(ch))
		{
			push(NUM, ch);
			cin >> ch;
		}
		else
			switch(precede(GetTop(OPR), ch))
			{
				case '<':
				//運算符棧頂元素 < 當(dāng)前運算符
					push(OPR, ch)
					cin >> ch;
					break;
				case '>':
				//這里優(yōu)先級包含左優(yōu)先，但當(dāng)棧頂元素是（時，不彈出。
				//規(guī)定左括號運算級別最高，右括號運算級別最低，則括號內(nèi)的運算符基本運算完成后還剩下其他運算符時，一和右括號比較，優(yōu)先級肯定高 也會彈出棧進行運算
				//運算符棧頂元素 >= 當(dāng)前運算符，彈出運算，！！繼續(xù)將當(dāng)前元素和棧頂元素比較！
					Pop(OPR, op);
					Pop(NUM, a);
					Pop(NUM, b);
					push(NUM, operate(a,op,b))
				case '=':
				//只有一種情況 左括號遇到右括號時 彈出
					Pop(OPR,op);
					cin >> ch;
					
			}
		
	}
}

5. 和舞伴一起跳舞（實際應(yīng)用，只用基本函數(shù)并聲明一下）

void DancePartner(Person dance[], int num)
{
	InitQueue(Mdancers);
	InitQueue(Fdancers);
	for(int i = 0; i < num; i++)
	{
		if(person[i].sex = 'M')
			EnQueue(Mdancers, person[i]);
		else
			EnQueue(Fdancers, person[i]);
	}
	while(!EmptyQueue(Fdancers) && !EmptyQueue(Mdancers))
	{
		DeQueue(Mdancers, man);
		DeQueue(Fdancers, woman);
		cout << "歡迎" << man.name << "男士和" << woman.name << "女士一起跳舞" << endl;
	}
	if(!EmptyQueue(Fdancers))
	{
		woman = GetTop(Fdancers);
		cout << "下一場第一個跳舞的女士是" << woman.name << endl;
	}
	if(!EmptyQueue(Mdancers))
	{
		man = GetTop(Mdancers);
		cout << "下一場第一個跳舞的女士是" << man.name << endl;
	}

}