Stacks


Collapse Content

Stack Animation

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.

Implementation

A Stack class can be implemented with an Array or a LinkedList, and it just needs to provide the push and 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.

Stack Classes

In Java, you can use the library Stack class as your stack. In Ruby and Javascript, the standard Array class comes with the Stack's push and 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.

Challenge

Create a Stack with two methods push and 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.)

Sample Input

1
9
3 5 -1 -1 2 7 11 -1 -1

Sample Output

5 3 11 7

The first -1 pops the 5 off the stack and the next pops off the 3.

Challenge

Create a Stack that adds and removes items.

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Comments

Contact Us
Sign in or email us at [email protected]