C++ Stack Sequence
Description
Given five different integers that are pushed onto a stack in the order they are read, and a possible sequence of popping from the stack, please write a program to check if the popping sequence is valid. If it is not valid, output “no”; if it is valid, output “yes”.
Input Description
The first line contains five integers representing the numbers pushed onto the stack in order.The second line contains five integers representing the possible popping sequence.
Output Description
A single line string, either “no” or “yes”.
Sample Input 1
3 6 2 5 4 2 6 3 5 4Sample Output 1
yes
Problem Solving Approach
Code Sharing
#include <bits/stdc++.h>using namespace std;int s[6],top;// Using an array to build the stack, top is the position of the top of the stack void push(int x){// Push onto stack if(top<5){ top++; s[top]=x; }}void pop(){// Pop from stack if(top>0)top--;}int getTop(){// Get the top of the stack return s[top];}int a[6],b[6];// Two sequences, first put them into two arrays for easy access int main() { for(int i=0;i<5;i++){ cin>>a[i];// Input the first sequence data } for(int i=0;i<5;i++){ cin>>b[i];// Input the second sequence data } int j=0;// j is the index of array b for(int i=0;i<5;i++){ push(a[i]);// Push the sequence from array a while(top>0 && getTop()==b[j]){// Keep popping until a match is found, and stop if empty pop(); j++;// Move to the next number in b } } if(top==0)cout<<"yes";// Finally check if the stack is empty else cout<<"no"; return 0;}
Click the blue text to follow immediately
