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.

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
18 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
34 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
54 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
42 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
57 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
0answers
223 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
34 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
44 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
897 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
608 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
118 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 (...