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.
2
votes
0answers
16 views
Formal semantics of a mutable/imperative stack
When introducing formal semantics for data structures, immutable stacks are a nice simple example :
$\mathit{is\_empty}(\mathit{create()})=\mathrm{True}$
$\mathit{is\_empty}(\mathit{push}(e, s))=\...
1
vote
1answer
23 views
Implementing a symbol table with a hash table and a stack
I was in class today, in a Language Translations course, thinking about the best way to write a symbol table for a compiler. My professor showed us a hash-table with linked-lists connecting different ...
0
votes
0answers
32 views
Turing Machine using finite control memory for distinctness problem
I am building a turing machine that recognizes the following element distinctness problem and I also need the state transition diagram for it, and I just realized after you compare the first two ...
0
votes
1answer
42 views
Multiple post-fix expressions for an in-fix expression
Today I was learning to convert post-fix expressions to in-fix expressions and vice versa. What I want to know is whether a post-fix expression can have more than one infix representations.
For ...
2
votes
0answers
31 views
kPDA handling multiple epsilon transtions
I'm assigned to build a kPDA with 2 stacks that handles {w#w, where w is a string of (0,1)*}. I understand the # delineates the two strings, but I'm unsure of the logic when popping off stacks with ...
1
vote
1answer
32 views
Amortized time complexity for double stack emulated queue
Assume that we have a data type $stack$ which has two operation $push$ and $pop$, both operations' time complexity is $O(1)$ in worst case. The $stack$ also has a property $size$ indicate how many ...
3
votes
2answers
101 views
Merging balls interview problem
Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks.
You are given $n$ balls on the table and all the balls are rolling towards the ...
1
vote
1answer
29 views
Binary trees and preallocated nodes
I want to design a binary tree with preallocated nodes, in order to avoid calling malloc/free every time I want to insert/delete a node. The problem is I don't know ahead of time how many nodes the ...
1
vote
1answer
38 views
Can such an operation be done with two stacks?
Assume a Forth-like environment with two stacks, a main one and an auxiliary one.
The following operations can be done on the main stack: DUP (duplicate the top ...
1
vote
1answer
47 views
Converting an infix expression to postfix
So the question is to convert the following expression to postfix:
(a+b)^(p+q)^(r*s*t)
The answer I get when I calculate is: ...
1
vote
0answers
36 views
Direct addressing on a huge array
A Question from CLRS book:
(CLRS 11.1-4) We wish to implement a dictionary by using direct addressing on a
huge array. At the start, the array entries may contain garbage, and initializing the
...
1
vote
0answers
52 views
What is the algorithm to determine valid push and pop sequences for stack when repetition of numbers are allowed?
Unlike traditional problems dealing with push and pop sequences of distinct numbers, I would like to know the procedure to determine the validity of the stack operations for sequences of non-distinct ...
1
vote
2answers
119 views
How to determine maximum stack size of LL(1) parser?
I am generating an LL(1) parser generator for LL(1) grammars that have a maximum stack size when executed in the table-driven parser. Specifically, I'm parsing HTTP headers using a parser generated by ...
1
vote
2answers
161 views
Can a processor without stack pointer registers, have a subroutine calls and interrupts?
Suppose a processor does not have any stack pointer registers, which of the following statements is true?
It cannot have subroutine call instruction
It cannot have nested subroutines call
...
4
votes
2answers
91 views
Why operating system needs interrupt stack, if it has process control block?
I'm reading about an operating system but some concept confuses me.
What doesn't confuse me:
When an interrupt or system call or processor exception occurs, it happens when user mode tries to ...
0
votes
0answers
121 views
Find optimal path in BFS and DFS
In UCS it is clear that we find the cheapest cost path. In BFS and DFS we can get the order of output nodes. But How can we find the optimal path in BFS ans DFS in following cases?
0
votes
1answer
38 views
How to keep track of changes done to concurrent stacks?
I am writing a small RPN calculator that works on some stacks concurrently. For example, if I have two functions:
...
1
vote
1answer
48 views
Maximizing the sum from m stacks using k pop's
Assume you have m stacks each some elements within it. If you are allowed to do k pops , the objective is to maximize the sum(sum increases by the value of the popped element). What is the best ...
14
votes
2answers
2k views
Is it possible for a stack-based programming language to be concurrent?
I have been reading about stack-based programming languages, such as FORTH and Cat, and it seems that given their nature, they can only execute one action at a time regardless of their paradigm (FORTH ...
1
vote
1answer
362 views
Sorting a stack using Bubble sort
How to sort a stack using bubble sort? Can use another stack if necessary.
-1
votes
1answer
38 views
Why the overall architecture of Android OS is a stack and why not any other data structure?
The overall architecture of the Android OS is a Stack. What specifically justifies Stack to design the overall architecture of Android? Are all mobile OS like Windows Mobile, iPhone OS developed as ...
3
votes
1answer
89 views
Analysis of the Banana Game
My computer science professor introduced an interesting game in order to get us (his students) more familiar with the Stack and Queue ADTs.
Game Description
The banana game is played with a ...
0
votes
1answer
269 views
Data addresses with ADD instruction in various architectures?
I have no idea how to figure this out, any explanations or help would be greatly appreciated!
How many data addresses are specified in an ADD instruction in accumulator based architecture, stack ...
3
votes
1answer
2k views
Why is a sequence of n Push, Pop, Multipop operations O(n²)?
From "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453:
Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The ...
1
vote
1answer
76 views
Minimum amount of swaps needed to sort a stack
Given a stack, what is the minimum amount of swaps needed to sort it?
Since the bottom of it stays intact and we slowly move to the upper part of it, if the stack contains n elements, the amount of ...
1
vote
0answers
202 views
Maximizing book picked using two stacks
There are two stacks(S1 and S2) of books. Each book in stack has a weight. You are given a net weight(W) of books that can be picked. You have to maximize the number of books that can be picked. Note ...
0
votes
0answers
837 views
stack vs queue efficiency
Is there any literature / research on the average size efficiency of stacks vs queues? I asked because I was recently working on a problem where, if using a queue, the size quickly blew up and the ...
2
votes
2answers
46 views
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?
We're given the algorithm which uses stack in order to store data (stack is implemented via an array). When the stack is full the algorithm does the following:
Creates a new array double the ...
2
votes
0answers
48 views
stacks in tree constructions
There are two nice tree constructions, that use a stack in a similar manner:
Construct a binary search tree from a pre-order traversal (e.g. see http://www.geeksforgeeks.org/construct-bst-from-given-...
0
votes
2answers
510 views
Why is average waiting time is the same for FIFO and LIFO
I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about FIFO and LIFO containers:
Support retrieval in first in, first out (FIFO) order. This is surely
...
3
votes
2answers
98 views
Gauss-Jordan using stacks and list
I have a homework assignment in which I need to write an implementation of Gauss-Jordan with complete pivoting. Complete pivoting is a modification to the basic Gauss-Jordan algorithm in which rows ...
0
votes
2answers
248 views
Can a 1-tape turing machine simulate a stack?
Is it possible to simulate a stack-based machine using a 1-tape turing machine? I cannot wrap my head around it as turing machines do not provide mechanisms such as pointers.
I failed to find any ...
4
votes
1answer
56 views
Computing with number of stack items
For stack-oriented programming language, how many top-most items of the stack are needed to be accessible in order to be Turing complete?
Is it enough to be able to access just the top-most item? Two ...
3
votes
1answer
81 views
Are registers stack, per core or per application based?
I am doing a study on I found on youtube called OpenSecurityTraining: Introductory Intel x86. From what I understand there are registers like EAX, ECD, EDX, ect... and each have a purpose and hold/...
1
vote
1answer
111 views
Claimed problems with Lisp dynamic scoping
What would be the problem of running the following scala codes assuming we are working with dynamic scoping and a global stack to store environments as some variants of Lisp do?
...
0
votes
0answers
577 views
Understanding time complexity of dynamic array implementation of stack
let me tell you first what is written in the book I am following.
If the array is full,create a new array of twice the size, and copy items.
At n=1,we do 1 copy operation,at n=2,we do 2 copy ...
4
votes
1answer
131 views
What techniques could be used to support thread-local contexts and resources in a language?
I am interested in the subject of thread-local contexts, which is a feature that I use quite often in solutions, but seems to lack first-class support in any languages I have used.
Quite often in ...
0
votes
1answer
97 views
Queue implemented using stacks
I have this problem I'm trying to solve: Implement a queue with a constant number of stacks so that each queue operation takes a constant (worst-case) number of stack operations.
I don't want ...
1
vote
3answers
154 views
How are variables accessed in the correct order from the stack?
I'm learning about the stack but one thing I am unable to understand is how variables can be accessed in the correct order.
So if I had a basic program calculating the sum of some user entered values ...
0
votes
1answer
64 views
Memory address of variable after reassignment
When a local variable is reassigned a different value/object, does its position/address change in the stack?
-1
votes
1answer
1k views
implementation of queue using stack with REVERSE
Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions.
I'm looking for implementation of ...
2
votes
1answer
2k views
Why do we use stacks and not queues on system-level?
From low OS-level function calls, to memory allocated to an application, all will primarily take a stack to perform LIFO operations.
Why don't we use queues and FIFO operations? It's just a matter of ...
5
votes
1answer
681 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, ...
7
votes
2answers
718 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 ...
25
votes
1answer
3k views
Is a stack overflow detected by hardware or software?
Is it the task of the software (operating system) to detect stack overflows or is a stack overflow detected in hardware, causing an exception in the CPU?
-1
votes
1answer
114 views
Collecting and combining data from iterative DFS on read-only trees
I am iterating over a tree through an API. This API provides a list of nodes sorted in post order DFS. I need to gather data for each node in the tree, combine that data with the parent's data (...
2
votes
2answers
214 views
Stack memory questions
Are data and return addresses both pushed on the same stack space?
If yes, couldn't this piece of code cause problems:
...
5
votes
2answers
2k views
Data Structure for Representing a Math Expression
I'm looking to improve my object-oriented design skills and I came across a problem which asked to design classes to represent a mathematical expression such as (a + b) * ( c - d / e) in memory so ...
0
votes
1answer
264 views
Which permutations can not be obtained by moving elements through two stacks?
I have a Stack1 which has the entries a,b,c ( with a on the Top) and Stack2 which is empty.The condition is.
An entry pooped out of the stack1 can be printed immediatly or pushed to stack2. An ...
3
votes
3answers
85 views
Recursive methods with stacks
I'm doing some practice papers for revision for my finals and I came across this question:
"This question is about recursion. A recursive method can always be implemented by an iterative method ...
