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
27
votes
1answer
1k views

Is there a 'string stack' data structure that supports these string operations?

I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing ...
25
votes
1answer
3k views

Is a stack overflow detected by hardware or software?

Is it the task of the software (operating system) to detect stack overflows or is a stack overflow detected in hardware, causing an exception in the CPU?
15
votes
6answers
9k views

How to implement two stacks in one array?

I want to begin by saying that this is NOT a homework question. I am reading Introduction to Algorithms - the famous CLRS text to become a better programmer. I am trying to solve the problems and ...
14
votes
2answers
2k 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 ...
8
votes
1answer
531 views

How to detect stack order?

We take the sequence of integers from $1$ to $n$, and we push them onto a stack one by one in order. Between each push, we can choose to pop any number of items from the stack (from 0 to the current ...
7
votes
2answers
727 views

Is a stack machine with a forward read iterator Turing complete?

It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful ...
5
votes
1answer
730 views

Is a LBA with stack more powerful than a LBA without?

Even so a linear bounded automata (LBA) is strictly more powerful than a pushdown automata (PDA), adding a stack to a LBA might make it more powerful. A LBA with stack should not be Turing complete, ...
5
votes
2answers
2k views

Data Structure for Representing a Math Expression

I'm looking to improve my object-oriented design skills and I came across a problem which asked to design classes to represent a mathematical expression such as (a + b) * ( c - d / e) in memory so ...
4
votes
4answers
538 views

Interleaving algorithm for 2 stacks

Suppose I have two stacks $<a_1,a_2,...a_m>$ and $<b_1, b_2,...b_n>$ and a third stack of size $m+n$. I want to have the third stack in the following manner, $$<a_1,b_1,a_2,b_2,...a_n,...
4
votes
2answers
103 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 ...
4
votes
1answer
56 views

Computing with number of stack items

For stack-oriented programming language, how many top-most items of the stack are needed to be accessible in order to be Turing complete? Is it enough to be able to access just the top-most item? Two ...
4
votes
1answer
133 views

What techniques could be used to support thread-local contexts and resources in a language?

I am interested in the subject of thread-local contexts, which is a feature that I use quite often in solutions, but seems to lack first-class support in any languages I have used. Quite often in ...
4
votes
2answers
149 views

Does the OS create its own bootstrapped stack frame when running a program?

I've been doing nand2tetris exercises and I'm quite interested in how compilation actually works. In nand2tetris when creating the VM language I had to create a "bootstrap" which called the main ...
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 ...
3
votes
2answers
98 views

Gauss-Jordan using stacks and list

I have a homework assignment in which I need to write an implementation of Gauss-Jordan with complete pivoting. Complete pivoting is a modification to the basic Gauss-Jordan algorithm in which rows ...
3
votes
2answers
163 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 ...
3
votes
1answer
92 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 ...
3
votes
1answer
81 views

Is “duplicate” in RPN enough for replacing variable binding in term expressions?

I try to work out some consequences of storing (or "communicating"/"transmitting") a rational number by a term expression using the following operators: $0$, $\mathsf{inc}$, $\mathsf{add}$, $\mathsf{...
3
votes
3answers
87 views

Recursive methods with stacks

I'm doing some practice papers for revision for my finals and I came across this question: "This question is about recursion. A recursive method can always be implemented by an iterative method ...
2
votes
1answer
2k views

Why do we use stacks and not queues on system-level?

From low OS-level function calls, to memory allocated to an application, all will primarily take a stack to perform LIFO operations. Why don't we use queues and FIFO operations? It's just a matter of ...
2
votes
1answer
52 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 ...
2
votes
2answers
47 views

How to write an algorithm which doubles stack in order to accommodate for new members where push is in constant time in the worst case?

We're given the algorithm which uses stack in order to store data (stack is implemented via an array). When the stack is full the algorithm does the following: Creates a new array double the ...
2
votes
1answer
82 views

Are registers stack, per core or per application based?

I am doing a study on I found on youtube called OpenSecurityTraining: Introductory Intel x86. From what I understand there are registers like EAX, ECD, EDX, ect... and each have a purpose and hold/...
2
votes
1answer
92 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
2answers
218 views

Stack memory questions

Are data and return addresses both pushed on the same stack space? If yes, couldn't this piece of code cause problems: ...
2
votes
0answers
20 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
62 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
3answers
155 views

How are variables accessed in the correct order from the stack?

I'm learning about the stack but one thing I am unable to understand is how variables can be accessed in the correct order. So if I had a basic program calculating the sum of some user entered values ...
1
vote
2answers
200 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 ...
1
vote
1answer
1k views

Efficient algorithm for a modified stack to pop the smallest element

I was practicing the following problem : There are a total of $N$ operations. At each operation, you can either add an element to the top or remove several elements as described below. ...
1
vote
1answer
83 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 ...
1
vote
3answers
332 views

Using Queues for a Stack and Stacks for a Queue

I was asked a question on how to use a pair of Queues to create a Stack and how to use a pair of Stacks to create a Queue. Any thoughts on how I would do this? Right now I don't even know where to ...
1
vote
2answers
145 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 ...
1
vote
1answer
116 views

Claimed problems with Lisp dynamic scoping

What would be the problem of running the following scala codes assuming we are working with dynamic scoping and a global stack to store environments as some variants of Lisp do? ...
1
vote
2answers
109 views

“Minimum Stack”

I am now preparing for a test in my algorithms course and I have stumbled upon a question about a data structure which seems too trivial for me, but is probably not trivial at all. The question is: ...
1
vote
1answer
252 views

A puzzle in Permutation

There are two stacks A and B. A : a,b,c,d ('a' is on top and 'd' is at the bottom of the stack) B : (empty) There are two rules. ...
1
vote
1answer
36 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 ...
1
vote
1answer
48 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 ...
1
vote
1answer
40 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
431 views

Sorting a stack using Bubble sort

How to sort a stack using bubble sort? Can use another stack if necessary.
1
vote
1answer
37 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
80 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
45 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
60 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
1answer
69 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 ...
1
vote
0answers
311 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 ...
1
vote
0answers
25 views

Impelementing a stack using a 2 queues, and a queue using 2 stacks [duplicate]

I have thought about it for a while, and I'm not really sure what is the best way to: 1.Implement a stack using 2 queues. 2.Implement a queue using 2 stacks. I have only though about ...
1
vote
1answer
40 views

How to get a base-3 representation of an integer using a stack? [closed]

Assuming that a stack data structure is available, how can this data structure be used to compute a representation of an integer in base three? For example, the algorithm for ...
0
votes
2answers
257 views

Can a 1-tape turing machine simulate a stack?

Is it possible to simulate a stack-based machine using a 1-tape turing machine? I cannot wrap my head around it as turing machines do not provide mechanisms such as pointers. I failed to find any ...