文章目录
- [225. 用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues/)
- [剑指 Offer 09. 用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)
- [239. 滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/)
- [622. 设计循环队列](https://leetcode-cn.com/problems/design-circular-queue/)
- [面试题 03.04. 化栈为队](https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci/)
- [641. 设计循环双端队列](https://leetcode-cn.com/problems/design-circular-deque/)
225. 用队列实现栈
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-j69eRzUl-1631408789824)(
#define LEN 20
typedef struct queue {
int *data;
int head;
int rear;
int size;
} Queue;
typedef struct {
Queue *queue1, *queue2;
} MyStack;
Queue *initQueue(int k) {
Queue *obj = (Queue *)malloc(sizeof(Queue));
obj->data = (int *)malloc(k * sizeof(int));
obj->head = -1;
obj->rear = -1;
obj->size = k;
return obj;
}
void enQueue(Queue *obj, int e) {
if (obj->head == -1) {
obj->head = 0;
}
obj->rear = (obj->rear + 1) % obj->size;
obj->data[obj->rear] = e;
}
int deQueue(Queue *obj) {
int a = obj->data[obj->head];
if (obj->head == obj->rear) {
obj->rear = -1;
obj->head = -1;
return a;
}
obj->head = (obj->head + 1) % obj->size;
return a;
}
int isEmpty(Queue *obj) {
return obj->head == -1;
}
MyStack *myStackCreate() {
MyStack *obj = (MyStack *)malloc(sizeof(MyStack));
obj->queue1 = initQueue(LEN);
obj->queue2 = initQueue(LEN);
return obj;
}
void myStackPush(MyStack *obj, int x) {
if (isEmpty(obj->queue1)) {
enQueue(obj->queue2, x);
} else {
enQueue(obj->queue1, x);
}
}
int myStackPop(MyStack *obj) {
if (isEmpty(obj->queue1)) {
while (obj->queue2->head != obj->queue2->rear) {
enQueue(obj->queue1, deQueue(obj->queue2));
}
return deQueue(obj->queue2);
}
while (obj->queue1->head != obj->queue1->rear) {
enQueue(obj->queue2, deQueue(obj->queue1));
}
return deQueue(obj->queue1);
}
int myStackTop(MyStack *obj) {
if (isEmpty(obj->queue1)) {
return obj->queue2->data[obj->queue2->rear];
}
return obj->queue1->data[obj->queue1->rear];
}
bool myStackEmpty(MyStack *obj) {
if (obj->queue1->head == -1 && obj->queue2->head == -1) {
return true;
}
return false;
}
void myStackFree(MyStack *obj) {
free(obj->queue1->data);
obj->queue1->data = NULL;
free(obj->queue1);
obj->queue1 = NULL;
free(obj->queue2->data);
obj->queue2->data = NULL;
free(obj->queue2);
obj->queue2 = NULL;
free(obj);
obj = NULL;
}
-------------------------------------------------------------------------
class MyStack {
public:
queue<int> queue1;
queue<int> queue2;
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
queue2.push(x);
while (!queue1.empty()) {
queue2.push(queue1.front());
queue1.pop();
}
swap(queue1, queue2);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int r = queue1.front();
queue1.pop();
return r;
}
/** Get the top element. */
int top() {
int r = queue1.front();
return r;
}
/** Returns whether the stack is empty. */
bool empty() {
return queue1.empty();
}
};
typedef struct tagListNode {
struct tagListNode* next;
int val;
} ListNode;
typedef struct {
ListNode* top;
} MyStack;
MyStack* myStackCreate() {
MyStack* stk = calloc(1, sizeof(MyStack));
return stk;
}
void myStackPush(MyStack* obj, int x) {
ListNode* node = malloc(sizeof(ListNode));
node->val = x;
node->next = obj->top;
obj->top = node;
}
int myStackPop(MyStack* obj) {
ListNode* node = obj->top;
int val = node->val;
obj->top = node->next;
free(node);
return val;
}
int myStackTop(MyStack* obj) {
return obj->top->val;
}
bool myStackEmpty(MyStack* obj) {
return (obj->top == NULL);
}
void myStackFree(MyStack* obj) {
while (obj->top != NULL) {
ListNode* node = obj->top;
obj->top = obj->top->next;
free(node);
}
free(obj);
}
------------------------------------------------------------------------
class MyStack {
public:
queue<int> q;
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
int n = q.size();
q.push(x);
for (int i = 0; i < n; i++) {
q.push(q.front());
q.pop();
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int r = q.front();
q.pop();
return r;
}
/** Get the top element. */
int top() {
int r = q.front();
return r;
}
/** Returns whether the stack is empty. */
bool empty() {
return q.empty();
}
};
剑指 Offer 09. 用两个栈实现队列
class CQueue {
stack<int> stack1,stack2;
public:
CQueue() {
while (!stack1.empty()) {
stack1.pop();
}
while (!stack2.empty()) {
stack2.pop();
}
}
void appendTail(int value) {
stack1.push(value);
}
int deleteHead() {
// 如果第二个栈为空
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
if (stack2.empty()) {
return -1;
} else {
int deleteItem = stack2.top();
stack2.pop();
return deleteItem;
}
}
};
239. 滑动窗口最大值
void swap(int** a, int** b) {
int* tmp = *a;
*a = *b, *b = tmp;
}
int cmp(int* a, int* b) {
return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
}
struct Heap {
int** heap;
int size;
int capacity;
};
void init(struct Heap* obj, int capacity) {
obj->size = 0;
obj->heap = NULL;
obj->capacity = capacity;
obj->heap = malloc(sizeof(int*) * (obj->capacity + 1));
for (int i = 1; i <= obj->capacity; i++) {
obj->heap[i] = malloc(sizeof(int) * 2);
}
}
void setFree(struct Heap* obj) {
for (int i = 1; i <= obj->capacity; i++) {
free(obj->heap[i]);
}
free(obj->heap);
free(obj);
}
void push(struct Heap* obj, int num0, int num1) {
int sub1 = ++(obj->size), sub2 = sub1 >> 1;
(obj->heap[sub1])[0] = num0, (obj->heap[sub1])[1] = num1;
while (sub2 > 0 && cmp(obj->heap[sub2], obj->heap[sub1]) < 0) {
swap(&(obj->heap[sub1]), &(obj->heap[sub2]));
sub1 = sub2, sub2 = sub1 >> 1;
}
}
void pop(struct Heap* obj) {
int sub = 1;
swap(&(obj->heap[sub]), &(obj->heap[(obj->size)--]));
while (sub <= obj->size) {
int sub1 = sub << 1, sub2 = sub << 1 | 1;
int maxSub = sub;
if (sub1 <= obj->size && cmp(obj->heap[maxSub], obj->heap[sub1]) < 0) {
maxSub = sub1;
}
if (sub2 <= obj->size && cmp(obj->heap[maxSub], obj->heap[sub2]) < 0) {
maxSub = sub2;
}
if (sub == maxSub) {
break;
}
swap(&(obj->heap[sub]), &(obj->heap[maxSub]));
sub = maxSub;
}
}
int* top(struct Heap* obj) {
return obj->heap[1];
}
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
struct Heap* q = malloc(sizeof(struct Heap));
init(q, numsSize);
for (int i = 0; i < k; i++) {
push(q, nums[i], i);
}
int* ans = malloc(sizeof(int) * (numsSize - k + 1));
*returnSize = 0;
ans[(*returnSize)++] = top(q)[0];
for (int i = k; i < numsSize; ++i) {
push(q, nums[i], i);
while (top(q)[1] <= i - k) {
pop(q);
}
ans[(*returnSize)++] = top(q)[0];
}
setFree(q);
return ans;
}
------------------------------------------------------------------------
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
priority_queue<pair<int, int>> q;
for (int i = 0; i < k; ++i) {
q.emplace(nums[i], i);
}
vector<int> ans = {q.top().first};
for (int i = k; i < n; ++i) {
q.emplace(nums[i], i);
while (q.top().second <= i - k) {
q.pop();
}
ans.push_back(q.top().first);
}
return ans;
}
};
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
int q[numsSize];
int left = 0, right = 0;
for (int i = 0; i < k; ++i) {
while (left < right && nums[i] >= nums[q[right - 1]]) {
right--;
}
q[right++] = i;
}
*returnSize = 0;
int* ans = malloc(sizeof(int) * (numsSize - k + 1));
ans[(*returnSize)++] = nums[q[left]];
for (int i = k; i < numsSize; ++i) {
while (left < right && nums[i] >= nums[q[right - 1]]) {
right--;
}
q[right++] = i;
while (q[left] <= i - k) {
left++;
}
ans[(*returnSize)++] = nums[q[left]];
}
return ans;
}
-------------------------------------------------------------------------
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q;
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> ans = {nums[q.front()]};
for (int i = k; i < n; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
while (q.front() <= i - k) {
q.pop_front();
}
ans.push_back(nums[q.front()]);
}
return ans;
}
};
622. 设计循环队列
面试题 03.04. 化栈为队
typedef struct {
int* stk;
int stkSize;
int stkCapacity;
} Stack;
Stack* stackCreate(int cpacity) {
Stack* ret = malloc(sizeof(Stack));
ret->stk = malloc(sizeof(int) * cpacity);
ret->stkSize = 0;
ret->stkCapacity = cpacity;
return ret;
}
void stackPush(Stack* obj, int x) {
obj->stk[obj->stkSize++] = x;
}
void stackPop(Stack* obj) {
obj->stkSize--;
}
int stackTop(Stack* obj) {
return obj->stk[obj->stkSize - 1];
}
bool stackEmpty(Stack* obj) {
return obj->stkSize == 0;
}
void stackFree(Stack* obj) {
free(obj->stk);
}
typedef struct {
Stack* inStack;
Stack* outStack;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* ret = malloc(sizeof(MyQueue));
ret->inStack = stackCreate(100);
ret->outStack = stackCreate(100);
return ret;
}
void in2out(MyQueue* obj) {
while (!stackEmpty(obj->inStack)) {
stackPush(obj->outStack, stackTop(obj->inStack));
stackPop(obj->inStack);
}
}
void myQueuePush(MyQueue* obj, int x) {
stackPush(obj->inStack, x);
}
int myQueuePop(MyQueue* obj) {
if (stackEmpty(obj->outStack)) {
in2out(obj);
}
int x = stackTop(obj->outStack);
stackPop(obj->outStack);
return x;
}
int myQueuePeek(MyQueue* obj) {
if (stackEmpty(obj->outStack)) {
in2out(obj);
}
return stackTop(obj->outStack);
}
bool myQueueEmpty(MyQueue* obj) {
return stackEmpty(obj->inStack) && stackEmpty(obj->outStack);
}
void myQueueFree(MyQueue* obj) {
stackFree(obj->inStack);
stackFree(obj->outStack);
}
---------------------------------------------------------------------------
class MyQueue {
private:
stack<int> inStack, outStack;
void in2out() {
while (!inStack.empty()) {
outStack.push(inStack.top());
inStack.pop();
}
}
public:
MyQueue() {}
void push(int x) {
inStack.push(x);
}
int pop() {
if (outStack.empty()) {
in2out();
}
int x = outStack.top();
outStack.pop();
return x;
}
int peek() {
if (outStack.empty()) {
in2out();
}
return outStack.top();
}
bool empty() {
return inStack.empty() && outStack.empty();
}
};
641. 设计循环双端队列
#include <iostream>
#include <vector>
using namespace std;
class MyCircularDeque {
private:
vector<int> arr;
int front;
int rear;
int capacity;
public:
/** Initialize your data structure here. Set the size of the deque to be k. */
MyCircularDeque(int k) {
capacity = k + 1;
arr.assign(capacity, 0);
front = 0;
rear = 0;
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
bool insertFront(int value) {
if (isFull()) {
return false;
}
front = (front - 1 + capacity) % capacity;
arr[front] = value;
return true;
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
bool insertLast(int value) {
if (isFull()) {
return false;
}
arr[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
bool deleteFront() {
if (isEmpty()) {
return false;
}
// front 被设计在数组的开头，所以是 +1
front = (front + 1) % capacity;
return true;
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
bool deleteLast() {
if (isEmpty()) {
return false;
}
// rear 被设计在数组的末尾，所以是 -1
rear = (rear - 1 + capacity) % capacity;
return true;
}
/** Get the front item from the deque. */
int getFront() {
if (isEmpty()) {
return -1;
}
return arr[front];
}
/** Get the last item from the deque. */
int getRear() {
if (isEmpty()) {
return -1;
}
// 当 rear 为 0 时防止数组越界
return arr[(rear - 1 + capacity) % capacity];
}
/** Checks whether the circular deque is empty or not. */
bool isEmpty() {
return front == rear;
}
/** Checks whether the circular deque is full or not. */
bool isFull() {
// 注意：这个设计是非常经典的做法
return (rear + 1) % capacity == front;
}
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque* obj = new MyCircularDeque(k);
* bool param_1 = obj->insertFront(value);
* bool param_2 = obj->insertLast(value);
* bool param_3 = obj->deleteFront();
* bool param_4 = obj->deleteLast();
* int param_5 = obj->getFront();
* int param_6 = obj->getRear();
* bool param_7 = obj->isEmpty();
* bool param_8 = obj->isFull();
*/`