lẫn chuỗi Push và pop hoạt động tại sao lại trình tự này không possilbe

Question

Hi tất cả mọi người Tôi đang học tập cho một trận chung kết và tôi không thể hình dung câu hỏi này ra:

Giả sử một khách hàng thực hiện một chuỗi trộn lẫn của chồng đẩy và các hoạt động pop. Các hoạt động đẩy đẩy các số nguyên từ 0 đến 9 theo thứ tự vào ngăn xếp; các hoạt động pop in ra giá trị trả lại. Chuỗi nào sau đây không thể xảy ra?

(một) 4 3 2 1 0 9 8 7 6 5
(b) 2 1 4 3 6 5 8 7 9 0
(c) 0 4 6 5 3 8 1 7 2 9
(d) 4 6 8 7 5 3 2 9 1 0
(e) Tất cả những trình tự có thể xảy ra

Câu trả lời là C nhưng im không chắc chắn làm thế nào để đi đến kết luận rằng

Answer 1

Ok, Vì vậy, chương trình luôn đẩy 0-9 theo thứ tự, vì vậy nhìn vào mỗi dòng, chúng tôi làm việc ra lệnh push và pops xảy ra

**The first line.** - Stack is 
Pushes 0, 1, 2, 3, 4 - [0, 1, 2, 3, 4] 
Pops 4, 3, 2, 1, 0 - [] 
Pushes 5, 6, 7, 8, 9 - [5, 6, 7, 8, 9] 
Pops 9, 8, 7, 6, 5 - [] 

**Second line** - Stack is 
Pushes 0, 1, 2 - [0, 1, 2] 
Pops 2, 1  - [0] 
Pushes 3, 4  - [0, 3, 4] 
Pops 4, 3  - [0] 
Pushes 5, 6  - [0, 5, 6] 
Pops 6, 5  - [0] 
Pushes 7, 8  - [0, 7, 8] 
Pops 8, 7  - [0] 
Pushes 9   - [0, 9] 
Pops 9, 0  - [] 

**Third line** - Stack is 
Pushes 0   - [0] 
Pops 0   - [] 
Pushes 1, 2, 3, 4 - [1, 2, 3, 4] 
Pops 4,   - [1, 2, 3] 
Pushes 5, 6  - [1, 2, 3, 5, 6] 
Pops 6, 5, 3  - [1, 2] 
Pushes 7, 8  - [1, 2, 7, 8] 
Pops 8   - [1, 2, 7] 
Pops ?    

các pop tiếp theo pHẢI là 7, bởi vì nó được đẩy trước 8, nó không thể là 1.

Answer 2

Bạn có 8 in trước 1 vì vậy khi 1 đã xuất hiện các con số cho đến khi 8 đã được đẩy. Nhưng nếu trường hợp đó xảy ra, 2 cũng đã bị đẩy và do đó cần được bật lên trước 1.

CHỈNH SỬA: để tiết lộ thêm - nếu bạn có giá trị x và sau đó là giá trị y theo trình tự và bạn có x > y và x trước y trong chuỗi, không có giá trị trong khoảng [y, x] có thể được đáp ứng trong dãy sau y.

Answer 3

Điều này không khó để giải quyết. Bạn chỉ cần bắt đầu viết chuỗi cho đến khi bạn tìm thấy số popped đầu tiên; sau đó vượt qua và tiếp tục. Bây giờ chúng ta có thể thấy tại sao dãy thứ ba không thể xảy ra:

0 // Pop 0 
- 
1 2 3 4 // Pop 4 
1 2 3 
1 2 3 5 6 // Pop 6 
1 2 3 5 // Pop 5 
1 2 3 // Pop 3 
1 2 
1 2 7 8 // Pop 8 
1 2 7 // And here it fails; you cannot possibly pop a 1 from the stack 

Answer 4

Đối với bất kỳ giảm tiểu chuỗi trong chuỗi đầu ra, bạn không thể có [a1, ..., an] như vậy mà, có tồn tại k , trong đó ak > a1 và ak < an và ak chưa đến trước trong đầu ra và ak không phải là một phần của chuỗi phụ [a1, ..., an].

Ở đây [8, 1] là một chuỗi phụ như vậy, trong đó 7 đã không đến trước và vẫn không phải là một phần của chuỗi phụ.