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.

16 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
25 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))=\...
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 ...
2
votes
0answers
77 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-...
1
vote
0answers
55 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 ...
1
vote
0answers
92 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
285 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 ...
0
votes
1answer
36 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
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
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
30 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 ...
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 ...
0
votes
1answer
169 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 ...
0
votes
0answers
1k 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 ...
0
votes
0answers
740 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 ...
-1
votes
1answer
128 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 ...
-1
votes
1answer
131 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 (...