Skip to main content
17 votes
Accepted

Is it possible for a stack-based programming language to be concurrent?

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-...
Derek Elkins left SE's user avatar
9 votes
Accepted

Why is a sequence of n Push, Pop, Multipop operations O(n²)?

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. ...
Discrete lizard's user avatar
  • 8,303
8 votes

Is it possible for a stack-based programming language to be concurrent?

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 ...
ghellquist's user avatar
7 votes

Generate all permutations of 1 to n with i stacks

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 ...
John L.'s user avatar
  • 39.1k
6 votes
Accepted

Stack Permutation Algorithm

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 ...
Matthew C's user avatar
  • 499
5 votes

Is the reason for a stack to decrease the size of a program (by adding the use of subroutines)?

The reason for having a stack is recursion. You don’t need a stack if you don’t have recursion. CDC super computers in the 70s worked just fine without a stack - until they implemented Pascal. On ...
gnasher729's user avatar
  • 30.7k
4 votes

Minimum amount of swaps needed to sort a stack

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}...
Evil's user avatar
  • 9,465
4 votes

Can a processor without stack pointer registers, have a subroutine calls and interrupts?

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 ...
gnasher729's user avatar
  • 30.7k
4 votes
Accepted

Is it theoretically possible to dynamically grow array size in stack memory?

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:...
Martin Kochanski's user avatar
4 votes
Accepted

Array Doubling Size Strategies

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 ...
vonbrand's user avatar
  • 14.1k
4 votes
Accepted

What is the meaning of the statement "a sequence of n PUSH, POP and MULTIPOP opreations"

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 ...
John L.'s user avatar
  • 39.1k
3 votes
Accepted

Maximizing the sum from m stacks using k pop's

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 ...
Mathieu Mari's user avatar
3 votes
Accepted

Analysis of the Banana Game

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 ...
Yuval Filmus's user avatar
3 votes
Accepted

How to write an algorithm which doubles stack in order to accommodate for new members where push is in constant time in the worst case?

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 ...
coderodde's user avatar
3 votes

Are registers stack, per core or per application based?

Each virtual core has its own registers. Let's say you have a quad core Intel processor with hyperthreading. Each core has two virtual cores, the processor has four cores, so you have a total of eight ...
gnasher729's user avatar
  • 30.7k
3 votes
Accepted

Are registers stack, per core or per application based?

Each processor has it's own registers. each process has it's own values to the registers which getting stored/reload during context-switch.
dave's user avatar
  • 628
3 votes

Gauss-Jordan using stacks and list

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 ...
orlp's user avatar
  • 13.6k
3 votes

Can a 1-tape turing machine simulate a stack?

In addition to what @Raphael said, it's very easy to actually do it. Just make a rule for your Turing Machine that every time it moves left, it will also write null. Voilà! You have made a Pushdown ...
Ben I.'s user avatar
  • 1,710
3 votes
Accepted

Can a 1-tape turing machine simulate a stack?

Machines that have only a stack are called pushdown automata. They are less powerful than Turing machine, so yes: TMs can simulate stacks. Turing machines are a fairly simplistic model of computation,...
Raphael's user avatar
  • 72.6k
3 votes

Why postfix is used more often than prefix expression?

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 ...
axiac's user avatar
  • 131
3 votes
Accepted

Why do we do topological sorting to find shortest or longest path in weighted DAG?

By using this algorithm the expected time complexity would not be O(V+E) as we have to visit an edge multiple times. ...
vivek gupta's user avatar
3 votes
Accepted

How does the OS handle multiple stacks in its physical memory?

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 ...
Martin Kochanski's user avatar
3 votes
Accepted

Check if a string can be obtained by a sequences of insertion of "abc"

Congratulation, your algorithm works fast and correctly like magic. However, why is it correct? Claim: A string $s$ is valid iff either $s$ is empty or the two letters to the left of the leftmost ...
John L.'s user avatar
  • 39.1k
3 votes
Accepted

Question about stack permutations

First, lets try to understand this scenario We have three elements $i,j,k$ Their order of arriving at the stack is $j,k,i$ ($p_j<p_k<p_i$) Their order of getting out of the stack is $i,j,k$ ($i&...
Anwar's user avatar
  • 659
3 votes
Accepted

Finding the Equation for Potential Method and Amortization Analysis

Amortized analysis is a technique for showing how to distribute the total cost of a worst case sequence of operations among all the operations in the sequence to get an average cost. So, even if there ...
Russel's user avatar
  • 2,780
2 votes
Accepted

Computing with number of stack items

It depends on what kinds of things you can store on the stack. If each item on the stack is of unbounded size, you can simulate a two-counter machine, which is Turing-complete. Therefore, in this ...
D.W.'s user avatar
  • 162k
2 votes
Accepted

Claimed problems with Lisp dynamic scoping

With fact, the primary problem is with f. If n is 0, ...
Nathan Davis's user avatar
2 votes

What techniques could be used to support thread-local contexts and resources in a language?

One example of a language system built from bottom up to support this kind of situation is Erlang. It is well worth looking into. It is built around the concept that you create a lot of tasks. The ...
ghellquist's user avatar
2 votes
Accepted

Why is average waiting time is the same for FIFO and LIFO

Maybe an example will help, consider lets say for 3 minutes we add 2 tasks each minute, and we process 1 task a minute. With a FIFO queue the timeline will be: t(0): 'a' and 'b' added: [a, b] - 'a' ...
Matt D's user avatar
  • 313
2 votes

Data addresses with ADD instruction in various architectures?

First some terminology: Let's consider the ADD operation that is a logically three operand operation: two sources and one target, so these 3 are the maximum that could be provided. A (hardware) ...
Erik Eidt's user avatar
  • 451

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