2.用队列实现栈
题目链接
225.用队列实现栈 - 力扣（LeetCode）
题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
- 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
解题思路
这题的目的是让我们用队列实现栈，队列和栈的特性分别是先进先出和后进先出，那么我们可以引入两个队列，往复的拷贝存储数据，然后利用队列先进先出的特性，留下队列里最后一个数据，对于栈，该数据就是最先出栈的数据。利用这个思路，就可以很容易实现一个栈，其中对于队列的一些接口，直接调用即可。由于C语言没有内置数据结构，这里我们拷贝之前实现的队列接口：
typedef int QDaTaType; typedef struct QueueNode { struct QueueNode* next; QDaTaType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void QueuePush(Queue* pq, QDaTaType x); void QueuePop(Queue* pq); QDaTaType QueueFront(Queue* pq); QDaTaType QueueBack(Queue* pq); bool QueueEmpty(Queue* pq); int QueueSize(Queue* pq); void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QDaTaType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->head->next == NULL)//队列中剩下最后一个节点时 { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* del = pq->head; pq->head = pq->head->next; free(del); del = NULL; } pq->size--; } QDaTaType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QDaTaType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL && pq->tail == NULL; } int QueueSize(Queue* pq) { assert(pq); return pq->size; }
代码实现
typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); if(obj == NULL) { exit(-1); } QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { Queue* empty = &obj->q1; Queue* nonEmpty = &obj->q2; if(!QueueEmpty(&obj->q1)) { empty = &obj->q2; nonEmpty = &obj->q1; } while(QueueSize(nonEmpty) > 1) { QueuePush(empty,QueueFront(nonEmpty)); QueuePop(nonEmpty); } int top = QueueFront(nonEmpty); QueuePop(nonEmpty); return top; } int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestory(&obj->q1); QueueDestory(&obj->q2); free(obj); obj = NULL; }
3.用栈实现队列
题目链接
232.用栈实现队列 - 力扣（LeetCode）
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 ：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
解题思路
这题与上一题正好是反过来的，所以我们可以试着借鉴上一题的思路，用两个栈来实现一个队列，上一题中，为了实现栈的先进后出，我们将一个队列中的数据倒入另一个队列中，这里也可以这样做，但是如果画图以后，就会发现，似乎倒入一次以后，直接pop就能实现队列的先进先出，因为栈在倒入的时候，已经将数据的顺序颠倒过一次。再继续看我们不难发现，如果将原来倒入的数据全部pop出去之后，再次倒入新的数据，然后pop也是符合队列的特性的。所以我们就采用另一种方式：将两个栈分别命名为pushST和popST，在入队列的时候，都push进pushST中，出队列的时候都出popST中的数据，在每次访问popST之前，对popST判空，如果真的为空，那就将pushST中的数据倒入popST中，否则不执行操作。这样即可解决所有问题。由于C语言没有内置数据结构，这里我们拷贝之前实现的栈的接口：
typedef int STDataType; typedef struct Stack { STDataType* arr; int top; int capacity; }Stack; void StackInit(Stack* ps); void StackDestory(Stack* ps); void StackPush(Stack* ps, STDataType x); void StackPop(Stack* ps); STDataType StackTop(Stack* ps); bool StackEmpty(Stack* ps); int StackSize(Stack* ps); void StackInit(Stack* ps) { assert(ps); ps->arr = NULL; ps->capacity = ps->top = 0; } void StackDestory(Stack* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capacity = ps->top = 0; } void StackPush(Stack* ps, STDataType x) { assert(ps); //扩容 if (ps->capacity == ps->top) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->arr = tmp; ps->capacity = newCapacity; } //压栈 ps->arr[ps->top] = x; ps->top++; } void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } STDataType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->arr[ps->top - 1]; } bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; } int StackSize(Stack* ps) { return ps->top; }
代码实现
typedef struct { Stack pushST; Stack popST; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); if(obj == NULL) { perror("malloc"); exit(-1); } StackInit(&obj->pushST); StackInit(&obj->popST); return obj; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushST,x); } void PushToPop(MyQueue* obj) { if(StackEmpty(&obj->popST)) { while(!StackEmpty(&obj->pushST)) { StackPush(&obj->popST,StackTop(&obj->pushST)); StackPop(&obj->pushST); } } } int myQueuePop(MyQueue* obj) { PushToPop(obj); int front = StackTop(&obj->popST); StackPop(&obj->popST); return front; } int myQueuePeek(MyQueue* obj) { PushToPop(obj); return StackTop(&obj->popST); } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST); } void myQueueFree(MyQueue* obj) { StackDestory(&obj->popST); StackDestory(&obj->pushST); free(obj); obj == NULL; }
4.设计循环队列
题目链接
622.设计循环队列 - 力扣（LeetCode）
题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
解题思路
实现一个循环队列，我们可以用数组的方式，也可以用链表的方式，这里我使用数组的方式。对于循环链表，他的头尾是可以互通的，我们只需要在当指针走到物理意义上的尾的时候加上一个逻辑判断即可。这里我们引入两个指针表示队头和队尾。如果要入队列，当back在物理意义上的尾的时候，我们可以让back++，然后back对N取模即可让back回到物理意义的头上。出队列的情况与此类似。但是如果要获取队尾数据，对于边界情况，如果back处于物理意义的头时，再减一会出现错误，所以我们在这个结果上加上N，然后再对N取模，结果不会发生变化。对于循环队列无法判空判满的问题，我们只需要在其中留下一个空间不存放数据，然后当front==back的时候，就是空队列，相差1的时候就是满队列。
代码实现
typedef struct { int* a; int front; int back; int N; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a = (int*)malloc(sizeof(int) * (k + 1)); obj->front = obj->back = 0; obj->N = k+1; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->back; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->back+1)%obj->N == obj->front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->a[obj->back] = value; obj->back++; //对于到空间尾以后的处理 obj->back %= obj->N; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; obj->front++; //对于到空间尾以后的处理 obj->front %= obj->N; return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; else return obj->a[(obj->back - 1 + obj->N) % obj->N]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
