编程介的小学生 2019-03-29 22:47 采纳率: 20.5%
浏览 752

用堆栈实现push和pop的操作的一个算法的问题,用C语言的程序来实现

Problem Description
Nowadays, cloud computing is a popular topic among business and technology circles. In cloud computing, everything can be stored in a cloud server, and clients deal with the data by sending operation-requests to the server. However, such client-server mode may cause some problems. For example, if you send two operations op1 and op2 to the server, expecting that op1 should be executed first and followed by op2. Due to the network delay, op1 may arrive at the server later than op2. In order to inform the server the correct operation order, each operation is associated with a timestamp. Now if the server gets two operations (op1, t1) and (op2, t2), where t1 < t2, the server will know that op1 should be executed earlier than op2. So, if (op2, t2) arrives first, the server will execute op2 immediately. And when (op1, t1) arrives, the server will find that op1 should be executed before op2 (because t1 < t2), thus it has to undo op2, execute op1, and re-execute op2 finally.

In this problem, you are asked to simulate the above process. To simplify the problem, we assume that there is only a stack, a last-in-first-out data structure as you know, stored in the server. Three types of operations are considered, whose formats and semantics are given as follows.

push x t -- push x into the stack, and t is a timestamp
pop t -- pop the top element from the stack, and t is a timestamp
peak t -- return the top element in the stack, and t is a timestamp

When an operation op with a timestamp t arrives, the server process it in the following three steps:

Step 1: undo all the "push" and "pop" operations having timestamp larger than t.
Step 2: execute op.
Step 3: redo all the "push" and "pop" operations which were undone in step 1.

The server do not need to undo or redo any "peak" operations. In another word, every "peak" operation is executed only once after it arrives at the server.

Given the operations arriving at the server in order, you are asked to simulate the above process. The stack is empty initially. To simplify the problem further, another two assumptions are made:

  1. All the "pop" operations are valid. In another word, if you simulate the process correctly, no "pop" operations will be performed on an empty stack.
  2. All timestamps are different.

Input
The input contains multiple test cases.

Each case begins with an integer N (1<=N<=50000), indicating the number of operations. The following N lines each contain an operation in one of the following three formats:

push x t
pop t
peak t
where 0<=x, t<=10^9.

The operations are given in the order in which they arrive at the server.
The input is terminated by N = 0.

Output
For each case, output "Case #X:" in a line where X is the case number, staring from 1. Then for each "peak" operation, output the answer in a line. If the stack is empty, output -1 instead.

Sample Input
7
push 100 3
push 200 7
peak 4
push 50 2
pop 5
peak 6
peak 8
4
push 25 1
pop 5
peak 6
peak 3
4
push 10 1
peak 7
pop 3
peak 4
0

Sample Output
Case #1:
100
50
200
Case #2:
-1
25
Case #3:
10
-1

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 MATLAB怎么通过柱坐标变换画开口是圆形的旋转抛物面?
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题
    • ¥15 Visual Studio问题
    • ¥20 求一个html代码,有偿