Hot answers tagged

26

It can be software, or hardware, or both, or none. There are two kinds of overflows: overflow when growing the stack (when entering a function), and overflow when accessing an array on the stack. Overflows when growing the stack can be detected by making a bounds check on function entry, to verify that there is enough room (and either signal an error or ...


17

So, can stack-based programming languages be concurrent? Sure. Could they achieve concurrency by using multiple stacks at the same time or something alike? Already for normal languages multi-threading usually means having multiple "call" stacks. It would be completely natural to give each thread its own data stack. It would be straightforward to have an ...


8

First, let me comment on 2 misconceptions I see in your question: Landau notation ('Big $O$ notation') does not exclusively refer to running times, we can use it to describe any function we wish. The fact that the worst case running time is $O(n^2)$ doesn't mean the running time isn't also $O(n)$. The second part comes close to the point of this part in ...


8

I know a bit about FORTH so I will confine myself to that. It is a low level language, giving you as programmer access to all the hardware resources. So you can do whatever you like. Concurrency In order to have parallell programs (edit: used to say real concurrent programs) you need at least two execution units (CPU-s). It would be rather trivial to ...


7

Theorem The following are equivalent. $L$ is accepted by a deterministic LBA with stack $L$ is accepted by a nondeterministic LBA with stack $L$ is in $\operatorname{DTIME}(c^n)$ for some constant $c$. So the computational power of a LBA with stack for decision problems is well understood. The exponential runtime limits the usefulness of this knowledge in ...


7

It is not clear in the question what operations are allowed on the input and how to view or access the output. However, since we are dealing with all permutations, the answer is the same whether the input is a stack or queue and whether the output is a stack or a queue. From now on, we will assume both input and output are stacks. What is the minimum value ...


6

Your model is Turing-complete, unfortunately. You can simulate a queue in your data structure using the following algorithm. It introduced 3 new stack symbols: $d, x, y$. Enqueue(val) is just Push(val). For Dequeue(): ReadBegin(). Count the number of anything else - number of $d$ in the whole stack (which should be always non-negative). Push $y$ or pop $...


6

Ok here's my attempt 2 which won't construct the sequence of moves, but it at least proves what the optimal number of moves is and gives an indicator of how to construct the sequence. I'm addressing the inverse problem of turning "σ(1)σ(2)…σ(n)" to "12…n" using the moves "insert the current leftmost element somewhere different in the array", but they are ...


5

Different representations are useful for different purposes. Think what kinds of things you might want to do with the expression, and think how each of them would be done using the stack representation and using the binary tree representation, and choose for yourself. For fun, you may also want to consider something completely different, e.g. the english ...


5

Your question is very poorly stated, except for the title. There is not a single sentence that is really correct or meaningful semantically. So I will stick to the title, and explain what is wrongt with the text. Activation records are a programming language implementation concept. Programming languages can be used to implement algorithms in programs, but ...


5

Because some things need to be done LIFO and some things FIFO. For example, when a function call returns, it needs to return to the last item on the call stack, i.e., the function that called it. It would make no sense to return to the first item on the call-stack. Conversely, if you're serving requests, the next request you serve is the first one to enter ...


5

I thought for quite some time, but didn't find the problem with doing all of your operations in the most stupid possible way in a trie-like DAG structure: Add-Prefix-Set Create a trie of strings from $T$. Connect each leaf node to the root of the old trie. Complexity: $O(|T|)$ Merge Unite roots of two structures: make all children nodes of the second root ...


5

Your model is Turing complete (unlike what I previously thought), see user23013's answer a sketch of the proof (the essence is you can simulate a queue, and queue automata are Turing complete). There are several ways to weaken you model to drop to equivalence with linear bound automata or lower. Ginsburg, Greibach & Harrison [1] give a machine called a ...


4

Your problem is known as Pancake sorting and it is not true that $f(n) < n$. The minimum number of swaps is between $\frac{15n}{14}$ and $\frac{18n}{11}$. Currently we know empirically that $P_{17} = 19$, which is the Pancake number, giving lower bound of 19 flips in the stack of 17 elements. The sequence is known as AA058986.


4

The Control Data Cyber series had no stack pointer, but it had a Pascal compiler. Seymour Cray says your book is wrong. (The Subroutine Call instruction that this computer isn’t supposed to have would store the return address into the location after the instruction it branched to, forming an instruction that could be used to jump back to the caller). If your ...


4

Yes, it is certainly possible. It really depends if you want it enough to pay the price in terms of complication. First of all, I would strongly recommend that your array should have negative indices: a[-1], a[-2], and so on. This will be good because the stack grows downwards, and if you adopt this convention then you will not need to move all your ...


4

As phan801 commented, the first interpretation, a sequence of $n$ operations, each of which is either push or pop or multipop, is correct. Either one of the other two interpretations might stand a small chance without surrounding context or with a very different context. However, had it been the intended meaning, "the phrase would probably have a ...


3

This stack here is different from the data structure: you can access every element (typically). The stack is just a piece of memory the compiler uses with a certain structure; it's a stack of frames, one for each (nested) method call. Inside each frame, we don't have a stack. The compiler knows, at compile-time, the offset for every variable from the top-of-...


3

That depends on how your program is written, its language, and how exactly your compiler implements variables. Some languages just don't place variables on any stack (everything is global). This is how FORTRAN and early versions of BASIC used to work. "Normal" languages (like C, Pascal and such) allocate a structure (often called activation record) on the ...


3

"Local variable" is a concept in the source language. Some target languages have the concept (e.g. virtual machines with dictionary-based scopes), but many do not. Since you're using Java, let's look at the JVM. A local variable cannot be accessed by other methods (e.g. you can't pass a variable by reference like you can in C++ or Fortran), and cannot be ...


3

Note: I found a better technique which I give in a separate answer, which is more general, faster and simpler, though the complexity results remain somewhat similar. I chose to leave this answer rather than replace it, as it may be interesting to compare, and both solutions were too long for a single answer. Let A, B and C be the three stacks. I assume that ...


3

What you want is called indirection. Instead of physically moving the rows/columns, you move their names. Let's say I call row 1 r[0], and row 3 r[2], in a matrix A, which has size n by n. Initially, the rows are exactly as I call them, so we initialize r[i] = i for all i < n. Now I want to swap the third (r[2]) and the fifth row (r[4]). I could move ...


3

I don't think that it is possible to push an element to a full array-based stack in worst case $\mathcal{O}(1)$ time. However, you can rest assured that each push runs in constant amortized time whenever you multiply the length of the full array by a factor of $q > 1$ (like you do; $q = 2$ in your case). This is why: Suppose the initial array capacity is ...


3

Your instructor might have been reading the article Stackable and queueable permutations by Peter G. Doyle, who considers two exercises in Knuth's Art of Computer Programming. The context is that the string in question is a sequence of distinct numbers, and the task is to output them in increasing order (Doyle's article actually discusses the other ...


3

You can use dynamic programming to solve this problem in polynomial time. Create a table $A[i,l]$ with $0\le i \le m$ and $0\le l\le k$, where $A[i,l]$ reprensents the optimal allocation using at most $l$ pops among the first $i$ stacks. We initiate by $A[.,0]=A[0,.]=0$ and we have the following inductive step : $$ A[i+1,l]=\max\left\{A[i,l-t]+(t \text{ pops ...


3

The evaluation is easier for postfix-notation expressions. The evaluation is done easily using a stack. The expression is processed from left to right, one token at a time: operand -> put it on the stack; operator -> get from the stack the number of values it needs (two for +, three for ?:, one for unary - and so on), combine the values using the ...


3

The point you make at the very end of your question is the right one. No modern computer has a stack. In hardware terms it turns out to be superfluous, wasteful and useless. A stack is superfluous because one can easily perform the operations “write a value”, “retrieve the last value written”, and so on by having a pointer to a memory location. “Push” can be ...


3

Check amortized analysis. Note that usually array resizing requires (1) get memory for new version, (2) copy old contents over, (3) delete old version. The point of your approach 2 (double the size of the array each time, more generally extend by a fixed factor) is that it gives amortized constant cost for each push on the stack. The others get costlier when ...


2

Here's an algorithm that works without using recursion. I might say it's even easier to do without recursion. I'll be working off the underlying assumption that you don't have access to temporary variables, and that the only available operation to you is $pop(s, d)$ which pop the top element of s(source) and places it on top of d(destination). E.g.: we have ...


2

If you are allowed to use one extra variable, then a queue can simulate a stack, so in this model a queue plus a single extra storage location will suffice. The idea is to represent a stack, say $[\ a\ b\ c\ $(top), as a queue, (tail) $\langle c\ b\ a\rangle$ (head). Then the operation $\mathtt{push(x)}$ would correspond to $\mathtt{enque(x)}$, so $$ [\ a\ ...


Only top voted, non community-wiki answers of a minimum length are eligible