验证出栈顺序是否正确题解&队列

（1）验证出栈顺序是否正确

队列遵循先入后出的原则，故需要一个数组来模拟记录入栈和出栈

再分别对出栈顺序进行遍历验证是否正确

#include <iostream>
using namespace std;
# define m 100000
int b[m], a[m], c[m];
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		for (int j = 0; j < n; j++) {
			cin >> b[j];
		}
		int x = 0, y = 0, z = 0;
		//先入后出
		while (x < n&& y < n&&z < n) {
			c[x] = a[y];//在c中进行出栈和入栈
			while (c[x] == b[z]) {
				if (z < n) z++;
				if (x > 0)x--;
				else break;
			}
			x++;
			y++;
		}
		while (c[x] == b[z]&&z<n) {
			 if(z  < n) z++;
			 if (x > 0)x--;
			 else break;
		}
		if (z == n) {//遵循先入后出的原则并且能够遍历b，说明出栈顺序正确
			cout << "Yes\n";
		}
		else {
			cout << "No\n";
		}

	}

	return 0;
}

第一个while循环先用c数组实现出栈和入栈对b数组进行检索如果有先入栈又立即出栈的元素则c数组中不记录该元素，对b数组中下一个元素进行检查

若没有先入栈又立即出栈的元素则第一个while循环将a数组复制给数组再对b进行遍历，再进行计数

在c++中也可用stack函数来进行入栈和出栈思路大致相同

（2）队列

只允许在一段进行插入另一端进行删除的线性表

重要术语：队头，队尾，空队列，队头元素，队尾元素

重要特性：先入先出，后入后出

1.队列的顺序实现

1.队列的创建

# define max 10
typedef sturct{
int date[max];
int front;
int rear;
}sqQueue
void initqueue(sqQueue&s){
s.front=0;//初始化队头指针和队尾指针
s.rear=0;
} 
void testqueue(){
sqQueue s;
initqueue(s);
}

通过判断队头队尾是否相等来判断队列是否为空

2.入队

bool qnqueue(sqQueue& s,int t){
    if ((s.rear + 1) % max == s.front) {
        return false;
    }
    else {
        s.dat[s.rear] = t;//循环队列
        s.rear = (s.rear + 1) % max;
        return true;
    }

}

3.查

bool qnqueue(sqQueue& s,int& t){
    if (s.rear == s.front) {
        return false;
    }
    else {
        s.dat[s.rear] = t;
        return true;
    }

}

4.出队

bool qnqueue(sqQueue& s,int &t){
    if (s.rear== s.front) {
        return false;
    }
    else {
        s.dat[s.front] = t;
        s.front = (s.front+ 1) % max;
        return true;
    }

}

循环队列要判断队列是否已满则要看队尾指针的后面一位是否为队头指针，故if条件中用的是s.rear + 1) % max == s.front

如果不想浪费最后一片空间则可以在队列中定义一个int size，入队则size++，出队则size--

若最后size==max则说明队满，也可定义一个int frion，用来记录操作，删除为1则队空，插入为0队满

队尾指针指向不同位置时增删查改也会不同

判断队列中的元素个数t=(s.rear+max-s.front)%max

2.队列的链式实现

1.创建一个队列

typedef struct ListNode {
    int val;               
    struct ListNode* next;
} ListNode;

typedef struct {
    ListNode* front;
    ListNode* rear;
} linkqueue;
//初始化一个队列
void initqueue(ListNode&q){
   q.front=q.rear = (ListNode*)malloc(sizeof(ListNode));
    q.front->next = NULL;
}
void testqueue() {
    linkqueue s;
    initqueue(s);
}

带头节点判断队列是否为空只需要判断头指针是否指向NULL或者front和rear是否指向同一节点

不带头节点判断队列是否为空只需判断front或者rear是否等于NULL即可

2.入队

（1）带头节点的插入

void enqueue(linkequeue& q, int t) {
    listnode*s=(ListNode*)malloc(sizeof(ListNode));
    s->date = t;
    s->next = NULL;
    q.rear->next = s;
    q.rear = s;
}

（2）不带头节点的插入

void enqueue(linkequeue& q, int t) {
    listnode*s=(ListNode*)malloc(sizeof(ListNode));
    s->date = t;
    s->next = NULL;
    if (q.front = NULL) {
        q.front = s;
        q.rear = s;
    }
    q.rear->next = s;
    q.rear = s;
}

3.出队

（1）带头节点

bool dequeue(linkequeue& q, int& t) {
    if (q.front == q.rear) {
        return false;
    }
    listnode* s = (ListNode*)malloc(sizeof(ListNode));
    x = s->date;
    q.front->next = s->next;
    if (s== q.rear) {
        q.rear->next = q.front;
    }
    free(s)
        return true;
}

（2）不带头节点

bool dequeue(linkequeue& q, int& t) {
    if (q.front == NULL) {
        return false;
    }
    listnode* s = q.front;
    x = s->date;
    q.front = s->next;
    if (s == q.rear) {
        q.rear= NULL;
        q.front= NULL;
    }
    free(s)
        return true;
}

3.双端队列

输出受限

删除受限

不同的受限出队列方式不同