Above you can view a Stack for holding numbers. You can do two things with a stack:
- Add (or "push") an item to the top of the stack.
- Remove (or "pop") an item off the top of the stack.
You can add items without worrying about the size, but you only can access the top of the stack, not any of the items below.
A Stack returns items in Last-In-First-Out (LIFO) order. This means
pop will always retrieve the most recently added item that's still on the stack. This is useful for cases where you track things in the order they happened, such as an "undo" mechanism in a program.
A Stack class can be implemented with an Array or a LinkedList, and it just needs to provide the
pop methods on top of them.
Q: If internally it uses a data structure with more methods, why does it provide few external methods?
A: Sometimes less is more. For certain problems, you only want to add and remove items and do not want to access internal indices of a list. Using a stack in such cases makes your program clearer.
pop methods as well.
Uses of a Stack
A stack is used behind the scenes in many areas of programming. For example, the computer uses a Stack to handle recursive calls. Each function call is placed on the stack, and then popped off as the results are returned. In fact, you could replace any recursive code with your own loop and stack, though usually this makes the code much more messy.
Stacks are used in cases where you want to keep track of things in LIFO order, such as some of these Stack & Queue Challenges.
Create a Stack with two methods
pop. Use your LinkedList class to keep track of the elements internally.
The input will consist of the number
t followed by
t test cases. Each test case will consist of a number
n, followed by
n numbers of actual input.
For each number of the actual input, if the number is
-1, pop off a value from your stack and print it. Otherwise, push the number onto your stack.
(Print all numbers for one line of input on one line of output.)
1 9 3 5 -1 -1 2 7 11 -1 -1
5 3 11 7
-1 pops the
5 off the stack and the next pops off the