Shulou(Shulou.com)06/02 Report--

This article will explain in detail how to realize the stack push-in and pop-up sequence of c #. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

Enter two integer sequences. The first sequence represents the push-in order of the stack. Please determine whether the second sequence is the pop-up order of the stack. Assume that all the numbers pushed into the stack are not equal. For example, sequence 1, 2, 3, 4, 5 is the stack pressing order of a stack, and sequence 4, 5, 3, 2, 1 is a pop-up sequence corresponding to the stack sequence, but 4, 3, 5, 1, 2 cannot be the pop-up sequence of the stack sequence.

First of all, you can find the first element in the second sequence in the first sequence, that is, the stack order, which is 4, because the first element in the second sequence is the first element to be popped up, then in the push-in sequence, all the data before the data is popped up is pressed into the stack and has not been ejected, that is, it is continuously pressed into 1, 2, 3, 4, and then the first data 4 is popped up. After that, the next element in the second sequence is 5, if it is not the top element of the stack, start from 4 in the first sequence, continue to press in and eject again, take the element in the second sequence again, and pop up if it is the top of the stack. Until the stack is empty and the two sequences are traversed, otherwise, if the stack is not empty and both sequences have been traversed, it means that the second sequence is not the pop-up sequence of the stack sequence.

The program is designed as follows:

# include # include # include using namespace std;bool IsPopSeq (int * push_arr, int * pop_arr, size_t size) {assert (push_arr & & pop_arr & & size); / / determine the validity of the parameter stack s; size_t push_index = 0; size_t pop_index = 0 While (pop_index < size) {/ / pushes all elements in the input queue before the first element in the output queue into the stack while (push_index < size) {s.push (push_ arr [push _ index]); + + push_index; if (s.top () = = pop_ arr [index]) break } / / it is judged that if the input queue is all pressed but the first element of the output queue is still not found, return false if ((! s.empty ()) & & (s.top ()! = pop_ arr [pop _ index])) return false / the while ((! s.empty ()) & (pop_ arr [pop _ index] = = s.top ()) {s.pop (); + + pop_index continues to pop up when the elements in the stack happen to be the pop-up order of the output queue The condition of correct return is that if ((push_index = = size) & & (pop_index = = size) & & s.empty () return true; else return false;} int main () {int push_arr [] = {1,2,3,4,5} is judged when the input queue and output queue are traversed and the stack is empty. Int pop_arr1 [] = {4,5,3,2,1}; int pop_arr2 [] = {4,3,5,1,2}; int pop_arr3 [] = {2,5,3,4,1}; size_t size = sizeof (push_arr) / sizeof (push_arr [0]); bool ret = IsPopSeq (push_arr, pop_arr1, size); cout

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.