# 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.

104 questions
Filter by
Sorted by
Tagged with
45 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 ...
71 views

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 ...
72 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 ...
26 views

1 vote
564 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 ...
351 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 ...
44 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
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 ...