栈和队列的题目，咕咕咕

1.咕

225. 用队列实现栈 - 力扣（LeetCode）

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类

class MyStack {private:queue<int> q1;queue<int> q2;
public:void push(int x) {if(q1.empty()){q2.push(x);}else{q1.push(x);}}int pop() {queue<int>& qnonempty=q1.empty()?q2:q1;queue<int>& qempty=q1.empty()?q1:q2;while(qnonempty.size()>1){qempty.push(qnonempty.front());qnonempty.pop();}int temp=qnonempty.front();qnonempty.pop();return temp;}int top() {int temp=pop();push(temp);return temp;}bool empty() {return (q1.empty()&&q2.empty());}
};

栈是后进先出，而队列是先进先出，为了使用队列实现栈，每次在要输出时把队列反转一下（转移到另一个队列）再输出。

2.咕咕

232. 用栈实现队列 - 力扣（LeetCode）

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类

class MyQueue {private:stack<int> s1;stack<int> s2;
public:void push(int x) {s1.push(x);}int pop() {if(s2.empty()){while(!s1.empty()){s2.push(s1.top());s1.pop();}}int temp=s2.top();s2.pop();return temp;}int peek() {int temp=pop();s2.push(temp);return temp;}bool empty() {return (s1.empty()&&s2.empty());}
};

队列要先进先出，s1为输入栈，s2为输出栈，一旦要输出，就先看看s2有没有之前的元素还排着队等输出，有就先输出s2的，没有就先把s1的转移到s2反转一下。

3.咕咕咕

622. 设计循环队列 - 力扣（LeetCode）

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

typedef struct {int* arr;int front;//队头int rear;//队尾int capacity;//循环队列的空间大小
} MyCircularQueue;//这里申请了2个堆空间，待会要释放2个堆空间
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* pq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//要有多余的空间，用来区分为空还是为满
//如果没有多余1个空间，front==rear既是为空也是为满
//多1个空间，front==rear为空，(rear+1)%(capacity+1)==front为满pq->arr=(int*)malloc(sizeof(int)*(k+1));pq->front=pq->rear=0;pq->capacity=k;return pq;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->capacity+1)==obj->front;//多存了一个空间，不存放
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)) return false;//不要越界,要求余，rear指向的是实际尾部数据的下一个位置obj->arr[obj->rear++]=value;obj->rear%=(obj->capacity+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)) return false;++obj->front;obj->front%=(obj->capacity+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)) return -1;return obj->arr[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)) return -1;int prev=obj->rear-1;//如果rear为0，会越界if(obj->rear==0){prev=obj->capacity;}return obj->arr[prev];
}void myCircularQueueFree(MyCircularQueue* obj) {if(obj->arr) free(obj->arr);free(obj);obj=NULL;
}