Ex_1_3_45.md

title	Algorithm4 Java Solution 1.3.45
date	2019-07-28 08:47:27 +0800
draft	false
tags	JAVA
categories	TECH archives

1.3.45

Problem:

Stack generability. Suppose that we have a sequence of intermixed push and pop operations as with our test stack client, where the integers 0, 1, ..., N-1 in that order (push directives) are intermixed with N minus signs (pop directives). Devise an algorithm that determines whether the intermixed sequence causes the stack to under- flow. (You may use only an amount of space independent of N—you cannot store the integers in a data structure.) Devise a linear-time algorithm that determines whether a given permutation can be generated as output by our test client (depending on where the pop directives occur).

Solution：

code:

Ex_1_3_45.java

count the number and - in the input stream. If the char is a number count++, else if the char is - , count--. if count < 0 then return false which means the intermixed sequence causes the stack to underflow.

Reference：