『剣指offer--スタックとキュー』21、スタックの圧入、ポップアップシーケンス;5、2つのスタックでキューを実現する.20.min関数を含むスタック(python、C++)

21.スタックの圧入、イジェクトシーケンス
2つの整数シーケンスを入力します.最初のシーケンスはスタックの圧入順序を表します.2番目のシーケンスがスタックのポップアップ順序である可能性があるかどうかを判断してください.スタックに押し込まれたすべての数字が等しくないと仮定します.例えば、シーケンス1,2,3,4,5は、あるスタックの押し込み順序であり、シーケンス4,5,3,2,1は、そのスタックシーケンスに対応するポップアップシーケンスであるが、4,3,5,1,2は、そのスタックシーケンスのポップアップシーケンスであることは不可能である.(注:この2つのシーケンスの長さは等しい)
問題解決の考え方:
1つの補助スタックを使用して、圧入順序を巡回して補助スタックに圧入し、補助スタックのトップ要素がポップアップシーケンス要素と同じかどうかを判断し、同じ場合、補助スタックがポップアップし、ポップアップシーケンスの次の要素を判断します.

C++
class Solution {
public:
    bool IsPopOrder(vector pushV,vector popV) {
        int s1=pushV.size();
        int s2=popV.size();
        stack stack_tmp;
        if(pushV.empty()||popV.empty()||s1 != s2)
            return 0;
        for(int i=0,j=0;i

5、二つのスタックでキューを実現する
2つのスタックで1つのキューを実現し、キューのPushとPop操作を完了します.キュー内の要素はintタイプです.
問題解決の考え方:
 

C++
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.empty())
        {
            while(stack1.size()>0)
            {
                int data=stack1.top();
                stack1.pop();
                stack2.push(data);
            }
        }
        int head=stack2.top();
        stack2.pop();
        return head;
    }

private:
    stack stack1;
    stack stack2;
};


python
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1=[]
        self.stack2=[]
    def push(self, node):
        # write code here
        self.stack1.append(node)
        
    def pop(self):
        # return xx
        if len(self.stack2)==0:
            while(len(self.stack1)>0):
                elem=self.stack1.pop()
                self.stack2.append(elem)
        return self.stack2.pop()
            
        

20、min関数を含むスタック
スタックのデータ構造を定義し、スタックに含まれる最小要素を得ることができるmin関数(時間複雑度はO(1))をこのタイプで実装します.
問題解決の考え方:
補助スタックを設定し、スタックに入るたびの最小値を補助スタックmin_に保存します.stackでdata_stackはデータスタックです.

C++
class Solution {
public:
    void push(int value) {
        data_stack.push(value);
        if(min_stack.empty() || value data_stack;
    stack min_stack;
};

python
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.data_stack=[]
        self.min_stack=[]
    def push(self, node):
        # write code here
        self.data_stack.append(node)
        if len(self.min_data)!=0:
            self.min_data.append(min(node,self.min_data[-1]))
        else:
            self.min_stack.append(self.min_stack[-1])
            
    def pop(self):
        # write code here
        if self.data_stack and self.min_stack:
            self.data_stack.pop()
            self.min_stack.pop()
    def top(self):
        # write code here
        if self.data_stack:
            return self.data_stack[-1]
    def min(self):
        # write code here
        if self.min_stack:
            return self.min_stack[-1]