LeetCode —— 栈和队列相关的oj题（含循环队列）

一、用队列实现栈

** 请你仅使用两个队列实现一个后入先出（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

链接：https://leetcode-cn.com/problems/implement-stack-using-queues

1.题干分析

** 队列的特点---先进先出，后进后出；栈的特点---先进后出，后进先出；**** 用两个队列实现一个栈，那么他们入数据都是一样的，知识出数据的时候相反；为什么要用两个队列呢？假设q1和q2两个队列；q1队列用来入数据（入1,2,3,4），q2队列用来入q1队列的数据（就是依次取q1队列的队头的数据，入1,2,3），当q2队列只剩下一个数据（4）的时候，就把这个数据取出；数字4是后进队列的，此时取出就相当于数字4后进先出，这不就是栈的特点嘛。如果继续出数据，把q1里的数据入到q2里，当q1只剩下一个数据时，就出数据；那么两个队列实现一个栈就完成了；**

如何创建一个栈呢？还要有两个队列呢？

我们之前在C语言实现的队列中，是这样定义的：

typedef int QDataType;

typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QueueNode;

typedef struct Queue
{
    QueueNode* head;//队头
    QueueNode* tail;//队尾
}Queue;

题目中给了这样的代码：

typedef struct {


} MyStack;

这是栈的结构体；栈是用两个队列实现的，那么栈里面肯定是需要两个队列来实现的；

typedef struct {
    Queue q1;//队列1
    Queue q2;//队列2
} MyStack;

因为嵌套了几个结构体，很容易搞混，尤其是在调用的时候，下面是关系图：

2.动图解析

3.代码实现

在没有学习C++之前，用C语言实现这道题，我们可以将C语言实现的队列直接调过来 ；

typedef int QDataType;

typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QueueNode;

typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}Queue;

//队列的初始化
void QueueInit(Queue* pq);

//队列的销毁
void QueueDestroy(Queue* pq);

//队尾入队列
void QueuePush(Queue* pq, QDataType x);

// 队头出队列
void QueuePop(Queue* pq);

//取队头的数据
QDataType QueueFront(Queue* pq);

//取队尾的数据
QDataType QueueBack(Queue* pq);

//计算有多少个数据
int QueueSize(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

//队列的初始化
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = NULL;
    pq->tail = NULL;
}

//队列的销毁
void QueueDestroy(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur != NULL)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    } 
    pq->head = pq->tail = NULL;
}

//队尾入队列(尾插）
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}

// 队头出队列（删除数据）
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    QueueNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
    
    //此时head和tail同时指向最后一个空间，释放head后，要注意也要把tail释放了
    if (pq->head == NULL)
    {
        pq->tail = NULL;
    }
}

//取队头的数据
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;
}

//计算有多少个数据
int QueueSize(Queue* pq)
{
    assert(pq);
    int n = 0;
    QueueNode* cur = pq->head;
    while (cur)
    {
        ++n;
        cur = cur->next;
    }
    return n;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

//栈的创建
MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

//数据入栈
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

//数据出栈
int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;
    Queue* noneemptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        noneemptyQ = &obj->q1;
    }
    while(QueueSize(noneemptyQ) > 1)
    {
        QueuePush(emptyQ,QueueFront(noneemptyQ));
        QueuePop(noneemptyQ);
    }
    int top = QueueFront(noneemptyQ);
    QueuePop(noneemptyQ);
    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) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

二、有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = " ( ) "
输出：true
示例 2：

输入：s = " ( ) [ ] { } "
输出：true
示例 3：

输入：s = " ( ] "
输出：false
示例 4：

输入：s = " ( [ ) ] "
输出：false
示例 5：

输入：s = " { [ ] } "
输出：true

链接：https://leetcode-cn.com/problems/valid-parentheses

1.题干分析

** 本题向要表达的意思就是给定了一个含有左右括号的字符串，如果形如‘（ ）’则为有效，形如‘（ }’则为无效；我们该如何入手呢？，我们可以用栈的特点来实现，先进栈的左括号后匹配，配对成功则删除这对括号，直至全部匹配成功；**

2.动图解析

3.代码实现

typedef char STDataType;

typedef struct Stack
{
    STDataType* a;
    int top;//栈顶
    int capacity;
}ST;

//栈的初始化
void StackInit(ST* ps);

//栈的销毁
void StackDestroy(ST* ps);

//栈的栈顶插入
void StackPush(ST* ps, STDataType x);

//栈的删除
void StackPop(ST* ps);

//取栈顶的数据
STDataType StackTop(ST* ps);

//栈的元素个数
int StackSize(ST* ps);

//判断栈是不是空
bool StackEmpty(ST* ps);

//栈的初始化
void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

//栈的销毁
void StackDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

//栈的栈顶插入
void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newCapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

//栈的删除
void StackPop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}

//取栈顶的数据
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1];
}

//栈的元素个数
int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

//判断栈是不是空
bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}

bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        //入左括号
        if(*s == '(' || *s== '{' || *s== '[')
        {
            StackPush(&st,*s);
            ++s;
        }
        else
        {
            //遇到右括号，但是栈里面没有数据，说明前面没有左括号，不匹配
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            //取栈顶的数据，进行比对
            STDataType top = StackTop(&st);
            StackPop(&st);

            if((*s == ')' && top != '(')
            ||(*s == '}' && top != '{')
            ||(*s == ']' && top != '['))
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                s++;
            }
        }
    }
    //如果不是空，说明还有左括号未出；
    //没有匹配返回的是false
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

三、用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["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

连接：https://leetcode-cn.com/problems/implement-queue-using-stacks

1.题干分析

** 用两个栈来才实现队列，一个栈先入数据，另一个栈用来存第一个栈的数据，如：第一个栈如1,2,3,4，第二个栈从第一个栈的栈顶拿数据入，即为4,3,2,1；，这时候在取第二个栈的栈顶数据，就符合原来1,2,3,4先进先出的顺序，即队列的特点**

2.动图解析

3.代码实现

typedef int STDataType;
typedef struct Stack
{
    STDataType* a;
    int top;//栈顶
    int capacity;
}ST;

//栈的初始化
void StackInit(ST* ps);

//栈的销毁
void StackDestroy(ST* ps);

//栈的栈顶插入
void StackPush(ST* ps, STDataType x);

//栈的删除
void StackPop(ST* ps);

//取栈顶的数据
STDataType StackTop(ST* ps);

//栈的元素个数
int StackSize(ST* ps);

//判断栈是不是空
bool StackEmpty(ST* ps);

//栈的初始化
void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

//栈的销毁
void StackDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

//栈的栈顶插入
void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newCapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

//栈的删除
void StackPop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}

//取栈顶的数据
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1];
}

//栈的元素个数
int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

//判断栈是不是空
bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}

typedef struct {
    ST pushST;
    ST popST;
} MyQueue;

//队列的创建
MyQueue* myQueueCreate() {
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushST);
    StackInit(&q->popST);
    return q;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST,x);
}

//取队头数据
int myQueuePop(MyQueue* obj) {
    //如果popST中没有数据，将pushST中的数据导过去
    //popST中的数据就符合先进先出的顺序了
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    int front = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return front;
}

//返回队列开头的元素
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}

//判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}

//队列销毁
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}

四、设计循环队列

** 设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 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

链接：https://leetcode-cn.com/problems/design-circular-queue

1.题干分析

**什么是循环队列？循环队列与普通队列的差异是什么？ **

普通队列我们可以采用链表和顺序表的方式进行实现，之前的博客中说到，顺序表实现队列，由于数据在出队列的时候需要每次挪动数据代价比较大；因而我们选择了链表来实现；

如果非要采用顺序存储呢？建议采用循环队列的形式；

假设：初始化创建空队时，令head（头指针）和tail（尾指针）为0；，每当插入新的数据时，尾指针tail增1；每当删除队列头数据时，头指针head减1；在非空队列中，head始终指向队列的头，tail始终指向队列的尾的下一个位置；如下图所示;

循环队列，就是头尾相接 ；如果是链表，实现循环，我们可以想到一个循环链表，尾结点不指向空，指向头结点就可以了；那么数组怎么实现头尾相接呢？

重点：

** 循环队列，无论使用数组实现还是链表实现，都要多开一个空间，也就意味着，要是存K个数据的循环队列，要开k+1个空间，否则无法判空和判满；**

开辟k个空间：

满和空条件都是一样的，无法判端满；（数组也是如此）

开辟k+1个空间：

2. 代码实现

①数组实现

typedef struct {
    int* a;
    int k;
    int front;
    int tail;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->a = (int*)malloc(sizeof(int)*(k+1));//开辟k+1个空间
    cq->front = cq->tail = 0;
    cq->k = k;
    return cq;
}
//入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->tail] = value;
    ++obj->tail;
    obj->tail %= (obj->k+1);
    return true;
} 
//出数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    ++obj->front;
    obj->front%=(obj->k+1);
    return true;
}
//取队头
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->front];
}
//取队尾
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    if(obj->tail ==0)
        return obj->a[obj->k];
    else
        return obj->a[obj->tail-1];
    /*
    int i = (obj->tail + obj->k) % (obj->k+1);
    return obj->a[i];
    */
}
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1) % (obj->k+1) == obj->front;
}
//销毁
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

② 链表实现

**相比数组，链表不可以直接malloc k+1个节点；我们需要通过循环去开辟； **

typedef int CirQDataType;

typedef struct CirQNode
{
    CirQDataType Data;
    struct CirQNode* next;
}CirQNode;

typedef struct {
    int k;
    CirQNode* head;
    CirQNode* tail;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

//循环队列的初始化
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    CirQNode* cur = (CirQNode*)malloc(sizeof(CirQNode));
    cq->k = k;
    cq->head = cq->tail = cur;
    //创建好一个结点后，在后面循环创建k个结点
    while(k--)
    {
        CirQNode* newnode = (CirQNode*)malloc(sizeof(CirQNode));
        CirQNode* NewTail = cq->tail;//记录新的尾
        NewTail->next = newnode;//把申请的结点链到新的尾上
        newnode->next = cq->head;//新结点链到头结点
        cq->tail=newnode;//自己成为新的尾
    }
    cq->tail=cq->tail->next;//让tail回到原来的位置，也可不加，因为循环，只是个人看着不舒服
    cq->head = cq->tail;
    return cq;
}

//循环队列的入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    //依次入数据，tail向后走
    obj->tail->Data = value;
    obj->tail = obj->tail->next;
    return true;
}

//循环队列的出数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->head = obj->head->next;
    return true;
}

//循环队列取队头数据
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->head->Data;
    
}

//循环队列取队尾数据
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;   
        //tail的前有个位置的结点就是队尾的数据
        CirQNode* prev = obj->head;
        while(prev->next != obj->tail)
        {
            prev = prev->next;
        }
        return prev->Data;
}

//循环队列判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;
}

//循环队列判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->tail->next == obj->head;
}

//循环队列销毁
void myCircularQueueFree(MyCircularQueue* obj) {
    while(obj->head != obj->tail)
    {
        CirQNode* cur = obj->head->next;
        free(obj->head);
        obj->head = cur;
    }
    free(obj->head);
    free(obj);
}