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
0answers
54 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
1answer
79 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
173 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
90 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
265 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
27 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 something ...
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
1answer
3k views

What are activation records?

What are the open activation records of a recursive algorithm ? Edit: Activation records are the number of times that we call a function that is not finished yet. Correct? So we can find the number ...
0
votes
2answers
345 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 ...
0
votes
2answers
750 views

Why is average waiting time is the same for FIFO and LIFO

I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about FIFO and LIFO containers: Support retrieval in first in, first out (FIFO) order. This is surely ...
0
votes
1answer
100 views

Memory address of variable after reassignment

When a local variable is reassigned a different value/object, does its position/address change in the stack?
0
votes
1answer
590 views

Data addresses with ADD instruction in various architectures?

How many data addresses are specified in an ADD instruction in accumulator based architecture, stack based architecture, and in the most common register-based ...
0
votes
1answer
109 views

Queue implemented using stacks

I have this problem I'm trying to solve: Implement a queue with a constant number of stacks so that each queue operation takes a constant (worst-case) number of stack operations. I don't want ...
0
votes
1answer
32 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" ...
0
votes
1answer
54 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" ...
0
votes
1answer
151 views

Minimum descending stacks

Assume a randomly ruffled pack of n cards with numbers from 1 to n. Each time we pick the top card from the pack (while there are still cards) and we put them according to the following rules: The ...
0
votes
1answer
46 views

How to keep track of changes done to concurrent stacks?

I am writing a small RPN calculator that works on some stacks concurrently. For example, if I have two functions: ...
0
votes
1answer
291 views

Which permutations can not be obtained by moving elements through two stacks?

I have a Stack1 which has the entries a,b,c ( with a on the Top) and Stack2 which is empty.The condition is. An entry pooped out of the stack1 can be printed immediatly or pushed to stack2. An ...
0
votes
0answers
28 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
21 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
15 views

Manage nested recursions in the design of a concatenative language interpreter

I'm in the designing of an interpreter for a stack based concatenative language, and I'm currently stuck with a problem about recursion of some of my concatenative program to calculate factorial: <...
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
0answers
30 views

Is it still called “recursion” when you're using call-stack as a stack?

The most obvious way to solve a problem of balancing parentheses, like https://leetcode.com/problems/valid-parentheses/, is through a stack (a last-in-first-out (LIFO) datastructure). However, if you ...
0
votes
1answer
143 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
732 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
2k views

implementation of queue using stack with REVERSE

Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. I'm looking for implementation of ...
-1
votes
1answer
40 views

Why the overall architecture of Android OS is a stack and why not any other data structure?

The overall architecture of the Android OS is a Stack. What specifically justifies Stack to design the overall architecture of Android? Are all mobile OS like Windows Mobile, iPhone OS developed as ...
-1
votes
1answer
73 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 (...

1
2