1.队列的存储结构

#define MaxSize 50
typedef struct{ElemType data[MaxSize]; //存放队列的元素int front,rear; //队头尾指针
}SqQueue;

初始化操作：
Q.front=0=R.rear=0;
进队和出队操作：
1.``当队列不满时，先将值送到队尾元素，后队尾指针+1；
2.``队列不为空时，取队头元素，然后将队头指针+1；

假溢出现象：
Q.rear到顶后，Q.front不断pop后跟Q.rear指向同一个元素，但是浪费了很多空缺，且添加不了新的元素

2.循环队列

队尾指针前进 1： Q.rear=(Q.rear+1)%MaxSize；
队首指针前进1： Q.front=(Q.front+1)%MaxSize；
队列长度： （Q.rear+MaxSize-Q.front）%MaxSize；
循环队列判空的条件： Q.front=Q.rear；
重点：判断队列是否满
(Q.rear+1)%MaxSize==Q.front；
队列中元素的个数
(Q.rear-Q.front+MaxSize)%MaxSize；

2.1初始化队列

void InitQueue(SqQueue &Q){Q.rear=Q.front=0; //初始化队首队尾指针
}

2.2判空

bool isEmpty(SqQueue Q){ //不需要对队列进行操作，所以用SqQueue Q即可而非SqQueue &Qif(Q.rear==Q.front) return true; return false;
}

2.3入队

bool EnQueue(SqQueue &Q,ElemType x){ //给队列Q添加元素x，Q队列会发生改变，故需要用SqQueue &Q//1.首先判断是否为满if((Q.rear+1)%MaxSize==Q.front) return false;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;return true;
}

2.4出队

bool DeQueue(SqQueue &Q,ElemType &x){ //出队：队列和元素都会发生变化，故需要用&//1.首先判断是否为空if(Q.rear=Q.front) return false;//2.取出头指针指向的值x=Q.data[Q.front]x=Q.data[Q.front];//3.头指针前进Q.front=(Q.front+1)%MaxSize;return true;
}

3.链式队列

队列是一逻辑结构中的线性结构，而链式队列相等于一种存储类型（链式存储类型）

typedef struct ListQueue{LinkNode *front,*rear; //链式队列
}*LinkQueue;

3.1为空的判断

Q.front==NULL && Q.rear==NULL;

比如在出队的时候我们需要判断链表的队列不为空，才能进行下一步对front的操作；
而在入队的时候，我们需要判断的是链表是否为满（Q.rear+1）%MaxSize==Q.front

3.2链式队列初始化操作

void InitQueue(LinkQueue &Q){//1.Q的front和rear指向同一个元素Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));//2.下一个为空Q.front->next=Null;
}

Q.front==Q.rear; //为空

3.3入队

void enQueue(LinkQueue &Q,ElemType x){//1.创建一个新节点，将x值赋值给新节点LinkNode *newNode=(LinkNode*)malloc(sizeof(LinkNOde));newNode->data=x;s->next=NULL;//2.将节点赋值到链表末尾节点Q.rear->next=s;//3.更新rear尾节点Q.rear=s;
}

3.4出队

bool DeQueue(LinkQueue &Q,ElemType &x){if (Q. front==Q.rear) return false;//空队LinkNode *p=Q.front->next;x=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q. front; //若原队列中只有一个结点，删除后变空free(p);return true;
}
}

4.用栈的几道题目（括号匹配问题，层序遍历问题，斐波那契问题）

4.1括号匹配问题

  /*** 1.有效括号* @param s* @return*/public boolean isValid(String s) {Stack<Character> stack = new Stack<>();//1.遍历字符串for (char ch : s.toCharArray()) {//1.1如果ch为左括号，就压栈if(ch == '('||ch=='{'||ch=='[') {stack.push(ch);}else{//1.2否则(ch为右括号)就将当前ch字符保存，并pop出栈顶元素，判断能否消除if(stack.isEmpty()) return false;else{//1.3栈不为空时，判断此时右括号能否将栈顶的左括号进行抵消char popChar=stack.pop();if(ch==')'&&popChar!='(') return false;if(ch==']'&&popChar!='[') return false;if(ch=='}'&&popChar!='{') return false;}}}return stack.isEmpty()?true:false;}

C语言实现代码：
思路： 遍历字符串，当遇到右括号，就将其转置为左括号，因为右括号左边一定为左括号，进行判断是否相等；如果遇到的是左括号就压入数组中；

char pairs(char c){//1.当遇到右括号时返回左括号if(c=='}') return '{';if(c==']') return '[';if(c==')') return '(';return 0;
}//判断：右括号一定在右边
//所以我们遍历到右括号返回它的左括号ch，并与前一个字符进行判断看是否相等即可
bool isValid(char* s) {//1.得到s字符串的长度 int n=strlen(s); if(n%2==1) return false;//2.初始化栈和尾指针int stack[n+1];int rear=0;//3.遍历下标i的字符元素，return出相反元素for(int i=0;i<n;i++){char ch=pairs(s[i]);if(ch){//3.1ch为右括号时if(rear==0||stack[rear-1]!=ch) return false;rear--;}else{//ch为左括号时，将括号放入栈中stack[rear++]=s[i];}}return rear==0;
}

C语言栈实现有效括号的判断：

bool IsBraCheck(char *str){//1.初始化栈InitStack(S);int i=0;while(str[i]!='\0'){//1.左括号则压入栈中switch(str[i]){case '(': Push(S,'('); break;case '{': Push(S,'{'); break;case '[': Push(S,'['); break;//2.右括号case ')': Pop(S,e);if(e!='(') return false;break;   case ']': Pop(S,e);if(e!='[') return false;break;case '}': Pop(S,e);if(e!='{') return false;      break;}i++; }return IsEmpty(S)?true:false;}

队列实现层序遍历

List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {//1.头节点为null返回resultif (root == null) return result;//2.new一个队列，将头节点填入Queue<TreeNode> queue = new LinkedList<>();queue.add(root);//3.遍历队列的每个节点，3.1外循环-每层个数，3.2内循环-将当前层的值节点累加，并poll出来，3.3然后将他们的子节点offer到队列中while (!queue.isEmpty()) {//3.1外循环-每层个数int size = queue.size();ArrayList<Integer> path = new ArrayList<>();for (int i = 0; i < size; i++) {//3.2内循环-将当前层的值节点累加，并poll出来TreeNode poll = queue.poll();path.add(poll.val);//3.3将poll的子节点offer到queue中if (poll.left != null) queue.offer(poll.left);if (poll.right != null) queue.offer(poll.right);}//3.4将每层的集合填入resresult.add(new ArrayList<>(path));}return result;}

队列在计算机系统中的应用

1.打印机数据缓冲区 所存储的数据就是一个队列
原因： 因为主机和打印机之间的速度不匹配，主机输出数据给打印机打印，输出的速度比打印的速度要快很多，打印机是跟不上，由于速度不匹配：所以我们设置了一个数据缓冲区，主机把要打印数据依次写入到缓冲区，写满后就暂停输出，主机转而去做其他的事情，提高了效率；
2.CPU的资源竞争：

一些例题：

正确的说法是：

A. 消除递归不一定需要使用栈。虽然栈可以用来消除递归，但也有其他方法可以达到相同的效果，比如使用循环或者尾递归。

B. 错误。对于同一输入序列，不同的合法入栈和出栈组合操作可能会得到不同的输出序列。因此，栈的顺序是影响输出结果的一个关键因素。

C. 错误。通常使用栈来处理函数或过程调用，而非队列。函数调用时，先将当前的执行状态保存在栈中，然后跳转到函数的代码段继续执行。当函数返回时，再从栈中恢复之前保存的执行状态。

D. 错误。队列和栈都是线性表，但它们的运算方式是不同的。队列只允许在队头删除元素，在队尾添加元素；而栈只允许在栈顶添加或删除元素。