# 队列

2023-09-18

#### 队列结构定义

#define MaxSize 100
typedef struct {
int data[MaxSize];
int front, rear;	//队列头尾指针
}SqQueue;


#### 初始化

void initQueue(SqQueue &Q) {
Q.rear = Q.front = 0;
}


#### 判队列是否为空

bool isEmpty(SqQueue Q) {
return Q.rear == Q.front ? true : false;
}


#### 进队

bool EnQueue(SqQueue &Q, int x) {
if ((Q.rear + 1) % MaxSize == Q.front)
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;
return true;
}


#### 出队

bool DeQueue(SqQueue &Q, int &x) {
if (Q.rear == Q.front)
return false;
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
}


### 相关题目

#### 通过栈实现队列元素逆置

void inverse(Stack &S, Queue &Q) {
while(!QueueEmpty(Q)) {
x = DeQueue(Q);
Push(S, x);
}
while(!StackEmpty(S)) {
Pop(S, x);
EnQueue(Q, x);
}
}


#### 利用两个栈S1和S2来模拟队列

class CQueue {
public:

stack<int> st1;
stack<int> st2;

CQueue() {
}

void appendTail(int value) {
st1.push(value);
}

if(st2.empty()) {
while(!st1.empty()) {
st2.push(st1.top());
st1.pop();
}
}
if (st2.empty())    return -1;
else{
int ans = st2.top();
st2.pop();
return ans;
}
}
};


Q.E.D.