leetcode:栈和队列oj题

目录

1.有效的括号

2.用队列实现栈                                                                              

3.用栈实现队列                                                                              

4.设计循环队列                                                                             

1.有效的括号

https://leetcode.cn/problems/valid-parentheses/solutions/373578/you-xiao-de-gua-hao-by-leetcode-solution/                                                                                  

        这道题用栈比较好解决,当我们遇到左括号时,就将其入栈,遇到右括号时,出栈与之匹配,如果匹配成功就返回true匹配下一个,直到栈为空返回false,遍历结束.为了方便我们可以将括号存入哈希表,键为右括号,值为左括号.其中如果栈中数据为奇数,我们直接返回false即可,因为不可能匹配成功, 注意:这道题形如"([{}])"是可以匹配成功,但是"[{]}"这种是错误的                                                             

class Solution {
public:
    bool isValid(string s) {
        int n=s.size();
        if(n%2==1)
            return false;

        unordered_map<char,char>pairs={
            {')','('},
            {']','['},
            {'}','{'}
        };

        stack<char> stk;
        for(char ch:s)
        {
            if(pairs.count(ch))
            {
                if(stk.empty()||stk.top()!=pairs[ch])
                    return false;
                stk.pop();
            }
            else
                stk.push(ch);
        }
        return stk.empty();
    }
};

2.用队列实现栈                                                                              

https://leetcode.cn/problems/implement-stack-using-queues/description/                                                                             

        入栈操作时,首先将元素入队到 queue2,然后将 queue1的全部元素依次出队并入队queue2,此时queue2的前端的元素即为新入栈的元素.再将 queue1和queue2互换,则 queue1的元素即为栈内的元素,queue1的前端和后端分别对应栈顶和栈底.由于每次入栈操作都确保queue1的前端元素为栈顶元素,因此出栈操作和获得栈顶元素操作都可以简单实现.出栈操作只需要移除 queue1的前端元素并返回即可,获得栈顶元素操作只需要获得 queue1的前端元素并返回,queue1用于存储栈内的元素,判断栈是否为空时,只需要判断 queue 1 是否为空即可

class MyStack {
public:
    queue<int> queue1;
    queue<int> queue2;

    void push(int x) {
        queue2.push(x);
        while (!queue1.empty()) {
            queue2.push(queue1.front());
            queue1.pop();
        }
        swap(queue1, queue2);
    }
    
    
    int pop() {
        int r = queue1.front();
        queue1.pop();
        return r;
    }
    
   
    int top() {
        int r = queue1.front();
        return r;
    }
    
    
    bool empty() {
        return queue1.empty();
    }
};

3.用栈实现队列                                                                              

https://leetcode.cn/problems/implement-queue-using-stacks/solutions/632369/yong-zhan-shi-xian-dui-lie-by-leetcode-s-xnb6/         这道题的解法与上题类似,将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。每次 pop 或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序

class MyQueue {
private:
    stack<int> Stack1, Stack2;

    void in2out() {
        while (!Stack2.empty()) {
            Stack1.push(Stack2.top());
            Stack2.pop();
        }
    }

public:
    MyQueue() {}

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

    int pop() {
        if (Stack1.empty()) {
            in2out();
        }
        int x = Stack1.top();
        Stack1.pop();
        return x;
    }

    int peek() {
        if (Stack1.empty()) {
            in2out();
        }
        return Stack1.top();
    }

    bool empty() {
        return Stack2.empty() && Stack1.empty();
    }
};

4.设计循环队列                                                                             

          https://leetcode.cn/problems/design-circular-queue/description/                                             

        我们用链表实现队列,入队列时,将新的元素插入到链表的尾部,出队列时，将链表的头节点返回,并将头节点指向下一个节点

class MyCircularQueue {
private:
    ListNode *head;
    ListNode *tail;
    int capacity;
    int size;

public:
    MyCircularQueue(int k) {
        this->capacity = k;
        this->size = 0;
        this->head = this->tail = nullptr;
    }

    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        ListNode *node = new ListNode(value);
        if (!head) {
            head = tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
        size++;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        ListNode *node = head;
        head = head->next;  
        size--;
        delete node;
        return true;
    }

    int Front() {
        if (isEmpty()) {
            return -1;
        }
        return head->val;
    }

    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return tail->val;
    }

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

    bool isFull() {
        return size == capacity;
    }
};