Questions tagged [stacks]
A stack is a Last In First Out (LIFO) data structure. A common use of stacks is to store subroutine arguments and return addresses.
123 questions
0
votes
0
answers
25
views
A twist on previous smaller element
Given an array of integers A, the previous smaller element problem is to find, for each position i in the array, the closest element before position i that is smaller than A[i]. This problem can be ...
0
votes
0
answers
29
views
Implement bubble sort with limited memory elements
Suppose you have elements (a,b,c,d), and you want to use bubble sort to sort them(either ascending or descending,doesnt really matter), but you can only use a single memory stack (with infinite ...
- 141
0
votes
0
answers
25
views
Understanding reduce operations in PyTorch and autodiff. Confused on Operation tracking
I am trying to understand how the Reduce Operation that PyTorch does in its backward pass for broadcasted tensors actually work under the hood. I am trying to make a cpp library for neural networks ...
0
votes
1
answer
71
views
Is there a term for the ordering of symbols in an expression as if one were using Reverse Polish Notation?
I assume we have a simple definition of "expressions" comprised of symbols, some of which map (perhaps polymorphically) to functions and others which hold values, either as variables or ...
1
vote
1
answer
117
views
Algorithm for finding a 'mountain' with the tallest height in O(n) time
Here's the problem:
you get an array of numbers. lets say you get an array of 5 numbers: {5,3,4,1,1}. Each of the numbers in the array represent a 'tower'. Your goal is to make the array in the shape ...
- 11
2
votes
1
answer
72
views
What is the loop invariant for stack-based algorithm for finding largest rectangle enclosed in a histogram?
I would like some help with proving the correctness of the following algorithm that solves LeetCode problem 84 of finding the largest rectangle enclosed by the bars of a histogram. For simplicity, we ...
- 45
0
votes
1
answer
222
views
Monotonic stack complexity with binary search
A monotonic stack is a stack whose elements are monotonically increasing or decreasing. To insert an element into the stack you need to remove elements that are greater/less than the provided element ...
- 53
1
vote
1
answer
60
views
How would setjmp differ in runtime environments with stack-allocated vs. heap-allocated stack frames?
I am stumped on Engineering a Compiler, 3rd ed. Section 6.3, Review Question 1. The book uses the term 'activation record' to refer to a generalized procedure frame. The question asks:
In C, '...
- 11
1
vote
1
answer
85
views
Is there a concept of multidimensional call stacks in computer science?
Had this random thought while running.
If I think of a conventional computer program function execution, I think of piece of paper. The program can only run down the page, it can never go backwards.
...
- 111
-2
votes
1
answer
192
views
Amortized cost for Stack Operations
In this problem we consider two stacks $A$ and $B$
manipulated using the following operations ($n$ denotes the size of $A$ and $m$ the size of $B$):
PushA($x$): Push element $x$
on stack $A$.
...
- 1
0
votes
2
answers
126
views
Why is the push operation in incrementally grown array stack is $O(n^2)$
This is from the Narasimha's data structure book
For nth element (n - 1 index), if we want to push an element, create a new array of size n and copy old array to the new, and at the end assign the ...
- 208
1
vote
1
answer
147
views
Memory efficient undo data structure
I was playing a puzzle game and started wondering how they implemented their undo feature. The game only has five possible moves, and only when the player does a move does the game state change, but ...
- 175
1
vote
1
answer
104
views
Does graph traversal require stack machine?
I'm writing a graph traversal function to be used in a garbage collector.
To avoid stack overflow, I used a finite state machine. Roughly, it descends into child nodes recursively to mark objects, and ...
- 448
-1
votes
1
answer
1k
views
Show that the language $L=\{w|w$ has odd length and the middle symbol is a $0\}$ is Context-Free and construct a PDA that accepts it
Were w is any string composed over the alphabet $\Sigma = \{0,1\}$.
For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the ...
- 3
0
votes
2
answers
547
views
