---
# System prepended metadata

title: Leetcode 946 Validate Stack Sequences
tags: [Leetcode, 程式菜雞的coding日常]

---

# Leetcode 946 Validate Stack Sequences
###### tags: `Leetcode` `程式菜雞的coding日常`
## 題目原文
Given two integer arrays `pushed` and `popped` each with distinct values, return `true` if this could have been the result of a sequence of push and pop operations on an initially empty stack, or `false` otherwise.

Example 1:
> Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:
> Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

## 題目理解
題目會給兩個陣列pushed及popped，判斷這是否可能是對一個空stack進行一連串push與pop之後的結果。

## 解題思路
能push就push，能pop就pop(?)
最後檢查stack是否為空即可。

## 程式實作
```cpp=
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> check;
        int n = 0;
        for(int item:pushed){
            check.push(item);
            while(!check.empty() && check.top() == popped[n]){
                n++;
                check.pop();
            }
        }
        return check.empty();
    }
};
```

## 後記
2023/4/13的daily challenge
怎麼又是stack啊(?)