队列：复试第三章

1.队列的存储结构

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

初始化操作：
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; //初始化队首队尾指针
}
1
2
3

2.2判空

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

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;
}
1
2
3
4
5
6
7

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;
}
1
2
3
4
5
6
7
8
9

3.链式队列

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

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

3.1为空的判断

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

比如在出队的时候我们需要判断链表的队列不为空，才能进行下一步对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;
}
1
2
3
4
5
6

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

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;
}
1
2
3
4
5
6
7
8
9
10

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;
}
}
1
2
3
4
5
6
7
8
9
10
11

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

队列实现层序遍历

List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        //1.头节点为null返回result
        if (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将每层的集合填入res
            result.add(new ArrayList<>(path));
        }
        return result;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

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

一些例题：

正确的说法是：

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

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

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

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