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.
88
questions
0
votes
0answers
24 views
Implement Immediate Smaller Element problem using Stack
Immediate Smaller Element Problem:
Given an integer array arr of size $n$. For each element in the array, check whether the right adjacent element (on the next ...
1
vote
0answers
16 views
Why divide a stack into two parts and store them separately in main-memory and hard-drive a bad idea?
I'm learning data structure and trying to solve problem related to Computer Game like Chess/Go. There is a line in my book on the section of DFS algorithm, which is implemented by two stacks: one for ...
1
vote
1answer
19 views
write adt for stack operations
Ok, I dont understand whats the difference between:
write code for stack operations and write adt for stack operations?
lets say the operation is push() and pop(). So what different code is to be ...
0
votes
1answer
43 views
Black-Box Machine
Suppose we have mysterious machine which return median $m$ of given set $S$ and set $S/\{m\}$ in constant time, where $S/\{m\}$ denotes the difference of $S$ and element $m$. Prove that we can sort ...
0
votes
1answer
67 views
How to draw the heap for an array in Java?
I have an assignment to draw the heap after an ArrayList and a LinkedList is created.
...
0
votes
1answer
30 views
2
votes
1answer
119 views
How to convert a recursive function to a non recursive one using stack while keeping memoization?
Let's say I want to count the number of ways a string can be decoded, once encoding algorithm follows this map: 'a'=>'1', 'b'=>'2', ... 'z'=>'26'.
I could ...
0
votes
3answers
64 views
How does the OS handle multiple stacks in its physical memory?
Without assuming ASLR...
Processes have virtual addresses, and they manage stacks & heaps of their own. However, these all get mapped to physical addresses somewhere on the memory.
Let's say we ...
0
votes
0answers
30 views
Automatic stack
Each context-free language has an automatic stack received by a non-deterministic blank.
That is, it will not uphold the following determinism requirement:
0
votes
2answers
38 views
Call stack is hard to maintain in my brain. What should I?
When I study Binary Search Tree, I try to use a pencil and paper to scratch the process of in-order traversal. However, I find that it is hard to maintain the call stack in my brain without paper and ...
1
vote
0answers
59 views
Is there a known way to make an efficient, compact, and fully persistent stack or queue?
In the world of mutable/ephemeral data structures and imperative programming languages, one of the classic ways to implement a stack or queue is to use array doubling: use mutation to fill up or empty ...
0
votes
0answers
30 views
Same computation order using postfix notation?
I'm trying to understand arithmetic using stacks. Specifically converting infix notation to postfix notation. My question is how you convert an expression like: 1 + (2 + 3) + (4 + 5)
that computes in ...
0
votes
1answer
38 views
Formal definition of a language accepted by PDA
I am a bit confused on how to give a formal definition of the language accepted by A?
I can describe it by "The language of all strings starting with n-many a's or n-many c's followed by n-many b's" ...
2
votes
2answers
212 views
Implementing an efficent priority queue using only stacks
Is it possible to implement an efficient priority queue (as efficient as a heap) only using the stack data structure?
The usual efficiency for a priority queue which is implemented using a heap is :
...
3
votes
2answers
85 views
Why are primitive types stored in a stack in systems level software?
Firstly 2 disclaimers, I am very new to the concept of a stack at a low level. I've only encountered it because I'm learning rust and the docs mention it. Secondly, I am aware of another similar ...
0
votes
1answer
178 views
Why do we do topological sorting to find shortest or longest path in weighted DAG?
I was wondering why do we need to do the topological sort before performing relaxing of edges.
Wouldn't it'd be better if we do :
if starting vertex is "s"
...
1
vote
1answer
190 views
Why postfix is used more often than prefix expression?
i was reading stack and i came across the infix, preifx and postfix expression.So i understood that why postfix /prefix expressions are preferred over infix expression ( due to its unambiguous nature) ...
1
vote
1answer
143 views
Priority Queue Using Stack
Can one build a priority queue using stacks, such that the priority queue has the same complexity for each operation.
Could it be done? If so how? If not what is the best solution that can be done?
...
0
votes
1answer
37 views
When does kernel accessing virtual memory cause problems
I'm working with the CPU Pintos and have a question that is:
In which situations can the kernel accessing the data in virtual memory via a pointer lead to problems? And how do you avoid them?
I know ...
1
vote
2answers
129 views
Is call stack compile time or runtime detail?
I'm sorry if the question is quite naive, but I don't understand if a call stack is a language implementation detail or it depends on OS?
What I'm trying to understand is what decides how to store ...
8
votes
4answers
931 views
Stack Permutation Algorithm
I was recently designing a Forth stack machine. I have an atomic instruction which rotates the top N elements.
For example if the top of the stack is on the left, then say the N=3 rotate instruction ...
1
vote
3answers
109 views
Can a programming language be designed to use a fixed amount of memory?
I have been toying around with the idea of creating a programming language as a side-project, specifically trying to get extreme performance out of a machine.
I have been thinking about the ...
-1
votes
1answer
226 views
Implement heap using stack data structure
I want to implement a heap using the stack data structure. I have searched a lot on the internet. But I do not get any clue how to implement it.
Can you please help me to implement a heap using the ...
0
votes
1answer
217 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 ...
0
votes
0answers
28 views
Manage event programming under a stack-oriented language
I wonder how events, or more broadly reactive programming, could be managed in a simple stack-oriented language.
For example, let's imagine a context where there is a button that displays a small ...
2
votes
1answer
312 views
Is it theoretically possible to dynamically grow array size in stack memory?
I was wondering, given the usual stack memory functioning, whether it is possible for an array like primitive type allowed to grow in size to exist.
The functioning of such primitive type is as ...
3
votes
1answer
440 views
Generate all permutations of 1 to n with i stacks
Assume we have i stacks. the possible actions are:
push to first stack form input
pop from stack i and push it to stack i+1
pop from last stack to output
If we have numbers of 1 to n starting from 1 ...
2
votes
0answers
26 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
284 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
1answer
210 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
40 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
228 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
494 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 ...
2
votes
1answer
124 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
52 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
222 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
108 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
395 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
376 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 ...
2
votes
2answers
624 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
...
6
votes
2answers
746 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
1answer
48 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
462 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 ...
15
votes
2answers
3k 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
996 views
Sorting a stack using Bubble sort
How to sort a stack using bubble sort? Can use another stack if necessary.
-1
votes
1answer
40 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
130 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
731 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 ...
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
95 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 ...
