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.
9
questions
7
votes
1
answer
2k
views
Is a LBA with stack more powerful than a LBA without?
Even so a linear bounded automata (LBA) is strictly more powerful than a pushdown automata (PDA), adding a stack to a LBA might make it more powerful.
A LBA with stack should not be Turing complete, ...
- 5,390
28
votes
1
answer
1k
views
Is there a 'string stack' data structure that supports these string operations?
I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing ...
- 9,086
3
votes
1
answer
107
views
Is "duplicate" in RPN enough for replacing variable binding in term expressions?
I try to work out some consequences of storing (or "communicating"/"transmitting") a rational number by a term expression using the following operators: $0$, $\mathsf{inc}$, $\mathsf{add}$, $\mathsf{...
- 5,390
8
votes
2
answers
1k
views
Is a stack machine with a forward read iterator Turing complete?
It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful ...
- 5,390
2
votes
1
answer
581
views
Finding the Equation for Potential Method and Amortization Analysis
I am trying to figure out the solution to this problem:
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 $...
- 23
1
vote
3
answers
562
views
Using Queues for a Stack and Stacks for a Queue
I was asked a question on how to use a pair of Queues to create a Stack and how to use a pair of Stacks to create a Queue. Any thoughts on how I would do this? Right now I don't even know where to ...
- 11
1
vote
1
answer
339
views
Why Prefer Two Stacks to an Array for Undo/Redo?
It seems to be a popular opinion that "the right way" to implement undo/redo is "using a stack." (particularly in the context of an algorithms and data structures interview.)
Here'...
- 111
0
votes
1
answer
248
views
Minimum descending stacks
Assume a randomly ruffled pack of n cards with numbers from 1 to n. Each time we pick the top card from the pack (while there are still cards) and we put them according to the following rules:
The ...
- 9
0
votes
1
answer
1k
views
Data addresses with ADD instruction in various architectures?
How many data addresses are specified in an ADD instruction in accumulator based architecture, stack based architecture, and in the most common register-based ...
- 13