5087. Implement a stack
Mary just learned
about a new, fashionable structure. It includes “push” and “pop” operations.
Implement a stack
with two operations. The “first” operation pushes a number onto the stack, and the
“second” operation removes an element from the top of the stack. For each “second”
operation, print the removed number. It is guaranteed that all operations are
correct.
Input. The first line contains the number of
operations n (1 ≤ n ≤ 105). In the next n lines, the first number is the
operation number, and the second (only for the “first” operation) is the number
to be added. This number is a positive integer and does not exceed 105.
Output. Print all removed numbers one per line.
|
Sample
input 1 |
Sample
output 1 |
|
6 1 1 1 2 2 1 4 2 2 |
2 4 1 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
3 1 1 1 2 1 3 |
|
SOLUTION
data structures – stack
Algorithm
analysis
In this problem, you need
to simulate stack operations.
Example
Consider the stack
operations in the first example:
Algorithm
realization
Declare the stack.
stack<int> s;
Read the number of operations n.
scanf("%d", &n);
Sequentially process n operations.
for (int i = 0; i <
n; i++)
{
scanf("%d",
&op);
Insert the element, push operation.
if (op == 1)
{
scanf("%d",
&x);
s.push(x);
}
Remove the element, pop operation.
else
{
printf("%d\n",
s.top());
s.pop();
}
}
Java realization
import java.util.*;
public class Main
{
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
Stack<Integer> s = new
Stack<Integer>();
int n = con.nextInt();
for (int i = 0;
i < n; i++)
{
int op = con.nextInt();
if (op ==
1)
{
int x = con.nextInt();
s.push(x);
}
else
System.out.println(s.pop());
}
con.close();
}
}
Java realization –
class MyStack
import java.util.*;
class MyStack
{
private
Vector<Integer> v;
MyStack()
{
v = new
Vector<Integer>();
}
public void
push(int x)
{
v.add(x);
}
public int
pop()
{
int last = v.lastElement();
v.remove(v.size()
- 1);
return last;
}
}
public class Main
{
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
MyStack s = new
MyStack();
int n = con.nextInt();
for (int i = 0;
i < n; i++)
{
int op = con.nextInt();
if (op ==
1)
{
int x = con.nextInt();
s.push(x);
}
else
System.out.println(s.pop());
}
con.close();
}
}
Python realization
Read the number of operations n.
n = int(input())
Use the list stack to simulate
the stack.
stack = []
Sequentially process n operations.
for i in range(n):
lst = list(map(int,input().split()))
Insert the element, push operation.
if (lst[0] == 1):
stack.append(lst[1])
Remove the element, pop operation.
else:
print(stack.pop())