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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
40 views

Memory efficient undo data structure

I was playing a puzzle game and started wondering how they implemented their undo feature. The game only has five possible moves, and only when the player does a move does the game state change, but ...
SmileyCraft's user avatar
1 vote
1 answer
48 views

Does graph traversal require stack machine?

I'm writing a graph traversal function to be used in a garbage collector. To avoid stack overflow, I used a finite state machine. Roughly, it descends into child nodes recursively to mark objects, and ...
DannyNiu's user avatar
  • 192
-1 votes
1 answer
71 views

Show that the language $L=\{w|w$ has odd length and the middle symbol is a $0\}$ is Context-Free and construct a PDA that accepts it

Were w is any string composed over the alphabet $\Sigma = \{0,1\}$. For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the ...
Lorenzo's user avatar
0 votes
2 answers
94 views

What is the order of items being popped and pushed from a stack?

...
BeanieBaby's user avatar
1 vote
2 answers
37 views

Compile procedural code to pure stack operations

I asked this question specifically about why the JVM has a separate area for local variables: https://stackoverflow.com/q/76086392/1463507 It was answered satisfactorily within the scope of the ...
kqr's user avatar
  • 111
2 votes
1 answer
182 views

Finding the Equation for Potential Method and Amortization Analysis

I am trying to figure out the solution to this problem: In this problem we consider two stacks $A$ and $B$ manipulated using the following operations ($n$ denotes the size of $A$ and $m$ the size of $...
alienhunter's user avatar
1 vote
4 answers
196 views

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

The stack allows subroutines to be used. It can store return address for "return from subroutine" instruction (RTN) and also arguments for the function. It is not possible to store return ...
BipedalJoe's user avatar
1 vote
2 answers
96 views

Stack Program Counter

I am trying to understand stacks a little better. I don't understand why the content of the program counter is saved on the stack for the function call (call), but not for a jump (jmp)? can someone ...
DanielJackson1's user avatar
0 votes
0 answers
35 views

Choosing potential function in amortized analysis when knowing the initial and final state of our data structure

I've some trouble understanding how to choose the potential function in aggregate analysis, more specifically in the solution to this exercise from the book "Introduction to algorithms - Thomas H....
Alessandro Serra's user avatar
0 votes
0 answers
39 views

Isomorphism, one-to-one correspondence in Stack

From R C Lacher's slides on Data Structures, These axioms can be used to prove, among other things, that the stack is unique up to isomorphism: Given any two stacks on the same data type, there is a ...
ihsingh2's user avatar
0 votes
1 answer
683 views

Design a Pushdown automaton for $L = \{a^nb^m | n \le m \le 3n \} $

$L = \{a^nb^m | n \le m \le 3n \} $ This is by far the hardest pushdown automaton I had to design. I literally have no idea where to start. Here's my thought process. Firstly, I thought that for each ...
john doe's user avatar
  • 155
2 votes
1 answer
117 views

Question about stack permutations

I encountered an exercise in which I am struggling to understand the solution provided even though I spent a lot of time trying to figure it out. The exercise is the following and was taken from the ...
Yarin's user avatar
  • 229
2 votes
1 answer
119 views

What loop invariant can be used for this loop? (Algorithm to check if a sequence is stack permutable)

I've written a function that gets a permutation and checks if that permutation can be reached using a stack from an input sequence which is <1,2,3,...,n>. (we take elements from left) For ...
Pwaol's user avatar
  • 164
2 votes
1 answer
47 views

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

Let $a$ initially be an empty string. One can transform $a$ into $b$ in the following way: $a$ becomes $a_{left}+$"$abc$"$+a_{right}$, where $a=a_{left}+a_{right}$ in a prior state. $a_{left}...
user avatar
2 votes
1 answer
762 views

Array vs Linked List Implementation of Stacks (in JS)

Let's say I want to make a Stack class in JavaScript. The class will have a push() and a pop() method. I have two options for ...
Espresso's user avatar
  • 121
0 votes
0 answers
35 views

Are arrays “more abstract” than stacks or queues?

It seems to me that an array can be used as a stack or a queue and for various other things. In my mind this makes an array a higher order abstraction compared to those other two. Is this an ...
John Vandivier's user avatar
1 vote
1 answer
194 views

Why Prefer Two Stacks to an Array for Undo/Redo?

It seems to be a popular opinion that "the right way" to implement undo/redo is "using a stack." (particularly in the context of an algorithms and data structures interview.) Here'...
John Vandivier's user avatar
2 votes
1 answer
203 views

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

I am reading CLRS 3rd Ed, chapter 17.1 (Aggregate analysis pg453) and I came across this statement. Let us analyze a sequence of n PUSH, POP, and MULTIPOP operations on an initially empty stack. I ...
African_king's user avatar
0 votes
1 answer
269 views

Array Doubling Size Strategies

I would like to discuss resizing strategies for arrays please. If you have an array of $k$ initial size and it gets full, so you would like to choose from one of the following approaches: Approach 1: ...
Avv's user avatar
  • 493
2 votes
1 answer
183 views

Are recursion and a stack equivalent in terms of inplementing DFS?

It is well known that DFS can be implemented either with recursion or a stack, and that both approaches are equivalent, but how far can we take that statement? Consider the following LeetCode problem: ...
nalzok's user avatar
  • 1,081
0 votes
0 answers
130 views

Iterative version of depth-first-search code to detect cycle in a directed graph [duplicate]

I have solved a problem that required me to find if the given directed graph had a cycle or not. The deal is, I used a recursive approach to solve it in the depth-first-search method. I was just ...
Siddharth VS's user avatar
0 votes
1 answer
37 views

`STACK-FULL` and `QUEUE-FULL` with worst-case $\Theta(1)$

There are two problems in CLRS about implementing stacks and queues with singly linked lists. I know the solutions, I know how STACK-EMPTY and ...
Emad's user avatar
  • 411
6 votes
0 answers
820 views

How to sort a queue using a temporary stack?

Suppose we have N natural numbers in a queue. ex queue = [3, 14, 1, 20] and an empty stack We are allowed to make only two actions: Action "x": Dequeue an element from the queue and push it ...
entropyfever's user avatar
0 votes
0 answers
122 views

Why is the stack smaller than the heap?

From what I understand, stack and heap grow in opposite directions: However, why is it then the case that the stack is sometimes statically allocated, and generally smaller than the heap? We hear ...
Alex Coleman's user avatar
0 votes
1 answer
231 views

Using saved registers at the main function with no other function calls [RISC-V]

The convention when a function is going to use a saved register is to save the contents of that register to the stack in case the caller (if there's one? the main function doesn't have one) had been ...
Some1's user avatar
  • 111
0 votes
1 answer
286 views

Stack without duplicates

I was thinking about the implementation of a DFS on graphs, and particularly about space complexity. The DFS algorithm can be implemented with a stack data structure. When a vertex $v$ is met during ...
Nathaniel's user avatar
  • 12.4k
1 vote
0 answers
186 views

purpose of stack segment in assembly language

The code snippet below is the "beginning lines of an assembly language program" used to display a single line string . ...
Tina's user avatar
  • 11
0 votes
0 answers
482 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 ...
salazarin's user avatar
  • 101
1 vote
0 answers
21 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 ...
Kindred's user avatar
  • 314
1 vote
1 answer
58 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 ...
begineerdev's user avatar
-1 votes
1 answer
54 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 ...
Snowball's user avatar
  • 109
0 votes
1 answer
271 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. ...
riley's user avatar
  • 1
0 votes
1 answer
115 views

How is the space complexity O(LogN) for rangeSumBST problem

Recursive ...
Arjun Hegde's user avatar
2 votes
1 answer
552 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 ...
Yago Tomé's user avatar
0 votes
3 answers
269 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 ...
Alex Coleman's user avatar
0 votes
0 answers
31 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:
user123427's user avatar
0 votes
2 answers
103 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 ...
skytree's user avatar
  • 123
1 vote
0 answers
97 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 ...
dfeuer's user avatar
  • 409
0 votes
0 answers
35 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 ...
user100752's user avatar
0 votes
1 answer
113 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" ...
Yani's user avatar
  • 1
3 votes
2 answers
862 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 : ...
Command Master's user avatar
3 votes
2 answers
300 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 ...
QurakNerd's user avatar
  • 133
0 votes
2 answers
927 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" ...
vivek gupta's user avatar
1 vote
1 answer
711 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) ...
teddcp's user avatar
  • 159
1 vote
1 answer
327 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? ...
newhere's user avatar
  • 101
0 votes
2 answers
58 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 ...
Programming_Zeus's user avatar
1 vote
2 answers
367 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 ...
E. Shcherbo's user avatar
8 votes
4 answers
1k 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 ...
Guillermo Phillips's user avatar
1 vote
2 answers
136 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 ...
Ben Chislett's user avatar
-1 votes
1 answer
853 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 ...
Christopher Marlowe's user avatar