Exercises: Unit 10 — Stacks, Queues & Deques

The first line contains N, and the optional second line contains a string of exactly N brackets from ()[]{}; use a stack to print YES if every closing bracket matches the most recent unmatched opening bracket and no opening bracket remains, or NO otherwise. When N is 0, the second line is absent and the empty string is balanced. A closing bracket when the stack is empty is unbalanced, as is any leftover opening bracket after the final character.

Constraints. 0 <= N <= 200000. The bracket string contains only (, ), [, ], {, and }, with no spaces. Use a deque as a stack and compare a closing bracket with stack[0].

Sample Input

6
([{}])

Sample Output

YES

The input is one valid space-separated postfix expression containing integers and the operators +, -, and *; evaluate it with a stack and print the final integer. Push integers as they arrive. For an operator, pop the right operand first and the left operand second, apply the operator, and push the result. In the sample, the final + token changes the answer from 10 to 15, so the result cannot be decided early.

Constraints. The expression contains between 1 and 200000 tokens and is guaranteed to be valid. Every integer token is between -1000000000 and 1000000000, and the expression is built so that every intermediate result is an integer whose absolute value is at most 10^18. Use a deque as a stack; direct expression-evaluation shortcuts are not allowed.

Sample Input

8 3 - 2 * 5 +

Sample Output

15

The first line contains Q, followed by Q command lines. TYPE c adds the one-character string c to the end of the document, and UNDO removes the most recently typed character that has not already been undone. Use an undo stack and print the final document, or print EMPTY if no characters remain.

Constraints. 1 <= Q <= 200000. Every c is one uppercase English letter, and every UNDO command has a character available to remove. Process each command once with a deque used as a LIFO stack.

Sample Input

8
TYPE C
TYPE O
TYPE D
UNDO
TYPE O
TYPE D
TYPE E
UNDO

Sample Output

COOD

The first line contains N, and the second line contains N integer signal strengths. For every position, print the first strictly greater strength to its right, or -1 if none exists, with answers separated by spaces. Scan from left to right while a monotonic stack holds indices whose answers are still unknown; compare the current strength with the index at stack[0], and resolve weaker indices by removing them from the stack.

Constraints. 1 <= N <= 200000. -1000000000 <= signal strength <= 1000000000. Use a deque as a monotonic stack; checking every later position for every signal is too slow.

Sample Input

8
4 2 7 7 1 3 8 5

Sample Output

7 7 8 8 3 8 -1 -1

The first line contains Q, followed by Q command lines. ARRIVE name adds a student to the back of the help-desk line, and SERVE removes and reports the student who has waited longest. Print served names in service order, one per line. If no SERVE command occurs, print an empty string. In the sample, FIFO order serves Maya and then Leo; treating the structure as a LIFO stack would incorrectly serve Leo before Maya.

Constraints. 1 <= Q <= 200000. Every name is a unique string of uppercase and lowercase English letters, and every SERVE command has a student waiting. Use append to enqueue and popleft to dequeue.

Sample Input

6
ARRIVE Maya
ARRIVE Leo
SERVE
ARRIVE Noor
SERVE
SERVE

Sample Output

Maya
Leo
Noor

The first line contains Q, followed by Q command lines for a queue that must be built from exactly two stacks. ENQUEUE x adds integer x, and DEQUEUE removes and reports the oldest stored integer. Push new values onto an input stack. When a dequeue finds the output stack empty, move every input value to the output stack one at a time before removing its top. Print dequeued integers one per line.

Constraints. 1 <= Q <= 200000 and -1000000000 <= x <= 1000000000. Every DEQUEUE command has a value available. Use two deques only as LIFO stacks, with stack push, peek, and pop operations.

Sample Input

7
ENQUEUE 10
ENQUEUE 20
DEQUEUE
ENQUEUE 30
ENQUEUE 40
DEQUEUE
DEQUEUE

Sample Output

10
20
30

The first line contains N, and the second line contains N distinct integer card labels in front-to-back order. Put the labels into a deque with append. Build a second deque by taking each original front label with popleft and placing it at the new front with appendleft, then print the reversed front-to-back order separated by spaces by reading with popleft.

Constraints. 1 <= N <= 200000. Every card label is between -1000000000 and 1000000000, and all labels are distinct. Use deque append, appendleft, and popleft; reverse the order by moving each label once.

Sample Input

7
10 20 30 40 50 60 70

Sample Output

70 60 50 40 30 20 10

The input is one uppercase string. Scan it from left to right using a stack: when the next character equals the character at stack[0], remove that stack character and discard the new character; otherwise push the new character. Removing one pair can bring another equal pair together. Print the final string, or EMPTY if every character disappears.

Constraints. The string contains between 1 and 200000 uppercase English letters. Each character may be pushed once and removed at most once. Build the result with string concatenation after the scan.

Sample Input

ABCCBADEED

Sample Output

EMPTY

The first line contains N, and the second line contains a desired departure order containing every car number from 1 through N exactly once. Cars arrive at the yard in order 1, 2, ..., N. Each arriving car may be pushed onto one side track, which is a stack, and only the car at stack[0] may depart. Print YES if the desired order can be produced by interleaving arrivals and stack departures, or NO otherwise.

Constraints. 1 <= N <= 200000. The desired order is a permutation of the integers from 1 through N. Simulate arrivals once and use a deque only as a LIFO stack.

Sample Input

5
2 1 4 3 5

Sample Output

YES