栈和队列基础练习¶

class MyStack225_1
{
private:
    queue<int> q1;
    queue<int> q2;

public:
    MyStack225_1()
    {
    }

    void push(int x)
    {
        // 插入到不为空的队列末尾
        if (!q1.empty())
            q1.push(x);
        else
            q2.push(x);
    }

    int pop()
    {
        int back = 0;
        // 找到非空队列的最后一个
        while (!q1.empty())
        {
            back = q1.front();
            if (q1.size() == 1)
            {
                q1.pop();
                return back;
            }
            q2.push(back);
            q1.pop();
        }

        while (!q2.empty())
        {
            back = q2.front();
            if (q2.size() == 1)
            {
                q2.pop();
                break;
            }
            q1.push(back);
            q2.pop();
        }

        return back;
    }

    int top()
    {
        // 找到非空队列的对头元素
        if (!q1.empty())
            return q1.back();

        return q2.back();
    }

    bool empty()
    {
        return q1.empty() && q2.empty();
    }
};

class MyStack225_2
{
public:
    queue<int> que;

    MyStack225_2()
    {

    }

    void push(int x)
    {
        que.push(x);
    }

    int pop()
    {
        int size = que.size();
        size--;
        while (size--)
        {
            que.push(que.front()); // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
            que.pop();
        }
        int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
        que.pop();
        return result;
    }

    int top()
    {
        int size = que.size();
        size--;
        while (size--)
        {
            // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result = que.front(); // 此时获得的元素就是栈顶的元素了
        que.push(que.front());    // 将获取完的元素也重新添加到队列尾部，保证数据结构没有变化
        que.pop();
        return result;
    }

    bool empty()
    {
        return que.empty();
    }
};

// 栈的实现
typedef int STDataType;
typedef struct stack
{
    STDataType *data;
    int top;      // 栈顶位置
    int capacity; // 元素个数
} ST;

// 栈的初始化
void STInit(ST *st);
// 栈的销毁
void STDestroy(ST *st);
// 数据入栈
void STPush(ST *st, STDataType x);
// 数据出栈
void STPop(ST *st);
// 判断栈是否为空
bool STEmpty(ST *st);
// 获取栈顶元素
STDataType STTop(ST *st);
// 获取栈内数据个数
int STSize(ST *st);

// 栈的初始化
void STInit(ST *st)
{
    // 判断是否存在队列
    assert(st);
    // 初始化队列
    st->data = NULL;
    st->top = 0; // 栈顶指针指向存储数据的下一个位置，代表栈内无数据
    // st->top = -1;//栈顶指针指向存储数据的位置，代表栈内无数据
    st->capacity = 0;
}

// 栈的销毁
void STDestroy(ST *st)
{
    // 确保有栈的存在
    assert(st);
    // 销毁栈
    free(st->data);
    st->data = NULL;
    // top和capacity更改为无数据的位置
    st->top = st->capacity = 0;
}

// 数据入栈
void STPush(ST *st, STDataType x)
{
    // 确保有栈的存在
    assert(st);
    // 向top位置增加数据，并使top向后移动
    // 需要判断栈的容量大小
    if (st->top == st->capacity)
    {
        // 如果栈的空间为0，则开辟四个空间，如果栈容量不为0，则扩容原来容量的2倍
        int newCapacity = st->capacity == 0 ? 4 : st->capacity * 2;
        STDataType *tmp = (STDataType *)realloc(st->data, sizeof(STDataType) * newCapacity);
        assert(tmp);
        st->data = tmp;
        // 注意更新容量大小
        st->capacity = newCapacity;
    }

    // 数据压栈并改变top
    st->data[st->top++] = x;
}
// 数据出栈
void STPop(ST *st)
{
    // 确保有栈的存在
    assert(st);
    // 确保栈不会越界
    assert(!STEmpty(st));

    // 直接移动top指针，“看不见即删除”
    st->top--;
}
// 判断栈是否为空
bool STEmpty(ST *st)
{
    // 确保有栈的存在
    assert(st);
    // 栈为空返回真，栈不为空返回假
    return st->top == 0; // 判断表达式返回值只有1和0，如果为真返回1(true)，如果为假返回0(false)
}
// 获取栈顶元素
STDataType STTop(ST *st)
{
    // 确保栈存在
    assert(st);
    // 确保栈不为空
    assert(!STEmpty(st));
    // top为栈内数据的下一个位置，要获取当前位置的元素需要-1操作
    return st->data[st->top - 1];
}

// 获取栈内数据个数
int STSize(ST *st)
{
    assert(st);
    return st->top;
}

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

MyQueue *myQueueCreate()
{
    // 初始化栈
    MyQueue *Queue = (MyQueue *)malloc(sizeof(MyQueue));
    STInit(&(Queue->pushST));
    STInit(&(Queue->popST));

    return Queue;
}

void myQueuePush(MyQueue *obj, int x)
{
    assert(obj);

    // 向pushSt栈中插入数据
    STPush(&(obj->pushST), x);
}

int myQueuePop(MyQueue *obj)
{
    assert(obj);
    // 复用myQueuePeek函数
    int data = myQueuePeek(obj);
    STPop(&(obj->popST));
    return data;
}

int myQueuePeek(MyQueue *obj)
{
    assert(obj);
    int data = 0;
    // 获取队列的头元素相当于栈的顶部元素
    // 如果popST不为空先执行popST
    if (!STEmpty(&(obj->popST)))
    {
        data = STTop(&(obj->popST));
        return data;
    }
    //  如果pushST中有数据并且popST为空，将数据移到popST中
    while (!STEmpty(&(obj->pushST)))
    {
        STPush(&(obj->popST), STTop(&(obj->pushST)));
        STPop(&(obj->pushST));
    }

    // 从popST中出数据
    data = STTop(&(obj->popST));
    return data;
}

bool myQueueEmpty(MyQueue *obj)
{
    assert(obj);
    return STEmpty(&(obj->pushST)) && STEmpty(&(obj->popST));
}

void myQueueFree(MyQueue *obj)
{
    assert(obj);
    STDestroy(&(obj->pushST));
    STDestroy(&(obj->popST));

    free(obj);
}

class MyQueue
{
private:
    // 创建两个栈
    stack<int> pushSt;
    stack<int> popSt;

public:
    MyQueue()
    {}

    void push(int x)
    {
        // 向pushSt插入数据
        pushSt.push(x);
    }

    int pop()
    {
        // 判断popSt是否为空
        if (popSt.empty())
        {
            // 将pushSt中的数据移动到popSt
            int top = 0;
            while (!pushSt.empty())
            {
                top = pushSt.top();
                pushSt.pop();
                popSt.push(top);
            }
        }

        // popSt不为空时直接弹出数据
        int top = popSt.top();
        popSt.pop();
        return top;
    }

    int peek()
    {
        // 如果popSt不为空，返回该栈顶元素
        if (!popSt.empty())
        {
            return popSt.top();
        }

        // 将pushSt中的数据移动到popSt
        int top = 0;
        while (!pushSt.empty())
        {
            top = pushSt.top();
            pushSt.pop();
            popSt.push(top);
        }

        return popSt.top();
    }

    bool empty()
    {
        return pushSt.empty() && popSt.empty();
    }
};

class MyCircularQueue
{
private:
    // 队头指针
    int front = 0;
    // 队尾指针
    int back = 0;
    // 最大元素个数
    int maxLen = 0;
    // 元素个数
    int num = 0;
    vector<int> cir;

public:
    MyCircularQueue(int k)
    {
        maxLen = k;
        cir.resize(k);
    }

    bool enQueue(int value)
    {
        // 判断队列是否已满
        if (isFull())
            return false;

        // 否则在指定位置插入
        // 位置修正
        if (back >= maxLen)
            back = back % maxLen;

        cir[back++] = value;
        num++;
        return true;
    }

    bool deQueue()
    {
        if (isEmpty())
            return false;
        front++;
        num--;
        if (front >= maxLen)
            front = front % maxLen;

        return true;
    }

    int Front()
    {
        if (num == 0)
            return -1;

        return cir[front];
    }

    int Rear()
    {
        if (num == 0)
            return -1;

        int ret = back == 0 ? cir[back] : cir[back - 1];

        return ret;
    }

    bool isEmpty()
    {
        return num == 0;
    }

    bool isFull()
    {
        return num == maxLen;
    }
};

class Solution
{
public:
    bool isValid(string s)
    {
        // 奇数个数的括号肯定不匹配
        if (s.size() % 2 != 0)
            return false;
        // 左括号进栈，右括号出栈匹配
        // 如果在判断过程中栈为空，或者括号不匹配都不属于有效括号
        // 此时栈为空说明此时左括号多了
        stack<char> st;

        for (char i : s)
        {
            if (i == '(' || i == '[' || i == '{')
                st.push(i);
            else if (i == ')')
            {
                if (st.empty() ||st.top() != '(')
                    return false;
                st.pop();
            }
            else if (i == ']')
            {
                if (st.empty() || st.top() != '[')
                    return false;
                st.pop();
            }
            else if (i == '}')
            {
                if (st.empty() ||st.top() != '{')
                    return false;
                st.pop();
            }
        }

        // 判断结果如果栈不为空，说明栈内还有左括号
        // 右括号与左括号个数不匹配，不属于有效括号
        if (!st.empty())
            return false;

        return true;
    }
};

class Solution1047_1
{
public:
    string removeDuplicates(string s)
    {
        stack<char> st;
        for (int i = 0; i < s.size(); i++)
        {
            if (st.empty() || st.top() != s[i])
                st.push(s[i]);
            else
                st.pop();
        }

        // 遍历当前栈取出其中的元素
        s.resize(st.size());
        int i = s.size() - 1;
        while (!st.empty())
        {
            s[i] = st.top();
            i--;
            st.pop();
        }

        return s;
    }
};

class Solution1047_2
{
public:
    string removeDuplicates(string s)
    {
        string ret;
        for (auto ch: s)
        {
            if (ret.empty() || ret.back() != ch)
                ret.push_back(ch);
            else
                ret.pop_back();
        }

        return ret;
    }
};