The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Hot answers tagged

25

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 ...


16

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

Another hint in addition to what Yuval said: it helps to place the stacks in a specific way in the arrays and fix their direction of growth accordingly. They don't have to grow in the same direction.


6

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 ...


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

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 $...


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 ...


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 ...


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

Here are some hints: One of the stacks should grow "up" and the other "down". There is no way of 'remembering' which element belongs to which stack - you are allowed to use additional variables to help you with stuff like that. (This makes more sense with the solution proposed by the first hint.)


4

You can simply push elements to the stack only if they are smaller than the element on the top of the stack.If they are bigger you will count them in different counter in order to know how much elements were pushed and keep those counters in another stack. When you have to pop you will pop only the top element. Here is sample pseudo code (some check for ...


4

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 ...


4

To answer the question in the comment above- Two queues to implement a stack(Assume Queue A is filled with elements in LIFO order and Queue B is empty): PUSH: Empty Queue A into Queue B. LIFO order will be persisted in Queue B. Now insert the new element into Queue A. Now empty Queue B into Queue A. POP: Dequeue from Queue A


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 ...


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

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

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 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.


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

Keep all the values $\frac{D_i - D_{i+1}}{V_i - V_{i+1}}$ in a min-heap. At each step, remove the minimum value, say $T = \frac{D_i - D_{i+1}}{V_i - V_{i+1}}$. We would first like to update all unaffected pairs, using $D'_j = D_j - TV_j$. The affect this has on the ratios is $$ \frac{D'_j - D'_{j+1}}{V_j - V_{j+1}} = \frac{D_j - TV_j - D_{j+1} + TV_{j+1}}{...


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

This problem looks like the problem of single stack sorting. "Single" because onle your stack B is used to sort, the stack A is only for input. Donald Knuth has analysed this, and characterized it as the 231-avoiding permutations, and has shown their number equals the Catalan numbers. Now if my observation is correct, you must have counted wrong (original ...


2

Your queue should append items to the rear of the stack, and get them off the top, so here's a pseudocode implementation of your two functions: $\texttt{Queue::Enqueue}(e):$ $\quad$Reverse; $\quad$Push($e$); $\quad$Reverse; $\texttt{Queue::Dequeue}():$ $\quad$__return__ Pop; Verify for yourself whether and why these functions produce the desired behaviour:...


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