栈&队列的接口 | 掬一把月 手揽回忆怎么睡
Cobb 563 1

动态顺序栈 动态环形队列 单链表

判断一组符号是否匹配

bool IsSignMatchAll(string signStr)
{
    // 括号数量为奇数,则不匹配,直接返回
    if (signStr.size() % 2 != 0)
    {
        return false;
    }

    stack<char> s;
    char cmp;
    for (char ch : signStr)
    {
        if (ch == '{' || ch == '(' || ch == '[')
        {
            s.push(ch);
        }
        else
        {
            switch (ch)
            {
            case '}':
                cmp = '{';
                break;
            case ')':
                cmp = '(';
                break;
            case ']':
                cmp = '[';
                break;
            }
            if (s.empty())
                return false;
            char top = s.top();
            s.pop();
            if (top != cmp)
                return false;
        }
    }

    return s.empty();
}

队列

内存可扩容循环队列

内存可扩容循环队列

class Queue
{
public:
    Queue(int size = 10)
        : front_(0)
        , rear_(0)
        , cap_(size)
    {
        que_ = new int[cap_];
    }
    ~Queue()
    {
        delete[]que_;
        que_ = nullptr;
    }
    void Push(int val)
    {
        if ((rear_ + 1) % cap_ == front_)
        {
            int* p = new int[2 * cap_];
            int i = 0, j = front_;
            for (; j != rear_; i++, j = (j + 1) % cap_)
            {
                p[i] = que_[j];
            }
            delete[]que_;
            que_ = p;
            front_ = 0;
            rear_ = i;
            cap_ *= 2;
        }
        que_[rear_] = val;
        rear_ = (rear_ + 1) % cap_;
    }
    void Pop()
    {
        if (rear_ == front_)
            return;
        front_ = (front_ + 1) % cap_;
    }
    bool Empty()const 
    { 
        return rear_ == front_; 
    }

    int back ()
    {
        // 巧妙处理环的问题,返回最后一个元素
        return que_[(rear_ - 1 + cap_) % cap_];
    }

private:
    int* que_;
    int front_;
    int rear_;
    int cap_;
};

二叉树的层序遍历(队列实现)

栈&队列的接口 | 掬一把月 手揽回忆怎么睡

struct Node
{
    int data;
    Node* left;
    Node* right;
};
// 二叉树的层序遍历 (父进队列 =》父出队列 =》 子进队列<从左往右> )
void LevelOrder(Node* root)
{
    queue<Node*> q;
    q.push(root);
    while (!q.empty())
    {
        Node* p = q.front();
        cout << p->data << " ";
        q.pop();

        if (p->left != nullptr)
        {
            q.push(p->left);
        }
        if (p->right != nullptr)
        {
            q.push(p->right);
        }
    }
}
int main()
{
    Node root{ 50, nullptr, nullptr };
    Node n1{ 30, nullptr, nullptr };
    Node n2{ 20, nullptr, nullptr };
    Node n3{ 40, nullptr, nullptr };
    Node n4{ 45, nullptr, nullptr };
    Node n5{ 60, nullptr, nullptr };
    Node n6{ 80, nullptr, nullptr };

    root.left = &n1;
    root.right = &n5;

    n1.left = &n2;
    n1.right = &n3;

    n3.right = &n4;

    n5.right = &n6;

    LevelOrder(&root);
}

两个栈 -> 队列

// 两个栈 -> 队列(一个辅助,一个主攻)
class Queue
{
public:
    void push(int val)
    {
        s1.push(val);
    }

    void pop()
    {
        // s1中元素到 s2中
        while (!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }

        // 出栈
        s2.pop();

        // s2中元素到回s1中
        while (!s2.empty())
        {
            s1.push(s2.top());
            s2.pop();
        }
    }

    int front()const
    {
         // s1中元素到 s2中
        while (!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }

        // 获取元素
        int val = s2.top();

        // s2中元素到回s1中
        while (!s2.empty())
        {
            s1.push(s2.top());
            s2.pop();
        }

        return val;
    }

    int back()const
    {
        if (s1.empty())
            return;

        return s1.top();
    }

    bool empty()const
    {
        return s1.empty();
    }
private:
    stack<int> s1;
    stack<int> s2;
};

两个队列 -> 栈

// 两个队列 -> 栈  (一个辅助,一个主攻)
class Stack
{
public:
    void push(int val)
    {
        q1.push(val);
    }

    void pop()
    {
        // 每次的栈数据大小都会发生变化
        int size = q1.size();
        // q1 最后一个留下,出队列, 数据入队q2
        for (int i = 0; i < size - 1; i++)
        {
            q2.push(q1.front());
            q1.pop();
        }

        // 出队
        q1.pop();

         while (!q2.empty())
         {
            q1.push(q2.front());
            q2.pop();
         }
    }

    int top() const
    {
        int size = q1.size();
        for (int i = 0; i < size - 1; i++)
        {
            q2.push(q1.front());
            q1.pop();
        }
        int val = q1.front();
        // 获取最后一个元素值之后,再放回去
        q2.push(q1.front());
        q1.pop();

        while (!q2.empty())
         {
            q1.push(q2.front());
            q2.pop();
         }

        return val;
    }

    bool empty()const
    {
        return q1.empty();
    }

private:
    queue<int> q1;
    queue<int> q2;
};

评论区

索引目录