Stacks

C++

C++

• push: adds an element to the top of the stack
• pop: removes an element from the top of the stack
• top: retrieves the element at the top without removing it

Copy
stack<int> s;
s.push(1);                 // [1]
s.push(13);                // [1, 13]
s.push(7);                 // [1, 13, 7]
cout << s.top() << endl;   // 7
s.pop();                   // [1, 13]
cout << s.size() << endl;  // 2

Java

Java

• push: adds an element to the top of the stack
• pop: removes an element from the top of the stack
• peek: retrieves the element at the top without removing it

Copy
Stack<Integer> s = new Stack<Integer>();
s.push(1);                     // [1]
s.push(13);                    // [1, 13]
s.push(7);                     // [1, 13, 7]
System.out.println(s.peek());  // 7
s.pop();                       // [1, 13]
System.out.println(s.size());  // 2

Python

Python

Python does not have a built-in stack type, but a list can function like a stack.

• list.append(): Appends an element to the end.
• list[-1]: Retrieves the last element without removing it.
• list.pop(): Removes the last element and returns it (but you don't need to use the returned value).
• list.pop(n): Removes the nth element, 0-indexed. Note that removing elements is an O(n) operation.

Copy
stack = []  # []
stack.append(1)  # [1]
stack.append(2)  # [1, 2]
stack.append(3)  # [1, 2, 3]
v = stack[-1]  # stack = [1, 2, 3] (unchanged), v = 3
stack.pop()  # [1, 2]
v = stack.pop()  # stack = [1], v = 2
stack.append(4)  # [1, 4]
v = stack.pop(0)  # stack = [4], v = 1

C++

Copy
#include <bits/stdc++.h>

using namespace std;

int N;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

Java

Copy
/**
 * author: Kai Wang
 */

import java.io.*;
import java.util.*;
public class NearestSmallestVals {

	/**
	 * We keep a stack of pairs (ind, value)

Python

Copy
n = int(input())
nums = list(map(int, input().split()))

ans = []
stack = []  # stores (a_i, i)
for idx, num in enumerate(nums):
	while stack and stack[-1][0] >= num:
		stack.pop()

	ans.append(0 if not stack else stack[-1][1] + 1)
	stack.append((num, idx))

print(*ans)