首页 > 代码库 > 剑指Offer20 栈的压入弹出序列是否正确

剑指Offer20 栈的压入弹出序列是否正确

 1 /************************************************************************* 2     > File Name: 20_IsPopOrder.cpp 3     > Author: Juntaran 4     > Mail: JuntaranMail@gmail.com 5     > Created Time: 2016年08月30日 星期二 19时53分19秒 6  ************************************************************************/ 7  8 #include <stdio.h> 9 #include <bits/stdc++.h>10 11 using namespace std;12 13 bool isPopOrder(int* push, int* pop, int length)14 {15     if (push==NULL || pop==NULL || length<=0)16         return false;17     18     int nextPush = 0;19     int nextPop  = 0;20     21     stack<int> stackData;22     while (nextPop < length)23     {24         // 如果当前栈为空 或栈顶元素不等于要出栈的元素,压栈25         while (stackData.empty() || stackData.top()!=pop[nextPop])26         {27             if (nextPush == length)28                 break;29             30             stackData.push(push[nextPush]);31             nextPush ++;32         }33         // 入栈队列结束还没找到钙元素, wrong34         if (stackData.top() != pop[nextPop])35             break;36         // 匹配到该元素,弹出,出栈指针后移一位37         stackData.pop();38         nextPop ++;39     }40     // 如果栈内已经没有元素且出栈指针已经走完,right41     if (stackData.empty() && nextPop==length)42         return true;43     44     return false;45 }46 47 int main()48 {49     int push[] = {1, 2, 3, 4, 5};50 //    int pop[]  = {4, 5, 3, 2, 1};51     int pop[]  = {4, 3, 5, 1, 2};52     int length = 5;53     if (isPopOrder(push, pop, length) == true)54         printf("Right\n");55     else56         printf("Wrong\n");57     58     return 0;59 }

 

剑指Offer20 栈的压入弹出序列是否正确