0% found this document useful (0 votes)

44 views6 pages

Stacks and Queues Exercises COMP 250

Q: What are the implications of stack and queue interconversion on operational complexity, especially in large-scale data processing?

Interconverting stacks and queues affects operational complexity mainly by elevating time complexity of traditionally O(1) operations to O(N), affecting performance in data-rich environments. This imposes constraints on real-time processing applications that demand efficient execution .

Q: Explain how to test for balanced parentheses using a stack and interpret the stack's state changes during the process.

To test for balanced parentheses, traverse each character of the expression. Push opening brackets onto the stack. On a closing bracket, pop from the stack and check for matching pairs. If the stack is empty after processing, it’s balanced; otherwise, it’s not. Update the stack state at each operation .

Q: If stacks can be used to simulate queue operations with potential inefficiencies in time complexity, describe one method and discuss its complexity implications.

Using a stack to simulate a queue involves transferring elements between two stacks for dequeue operations, which makes it O(N) where N is the number of elements. Enqueue remains O(1) but the requirement of additional operations for dequeue can lead to efficiency issues in large datasets .

Q: What is the sequence of operations needed to pop values from a stack filled with numbers 1 to 5, to achieve the order: 2, 4, 5, 3, 1, and is it possible to achieve this order?

It is possible to achieve the order 2, 4, 5, 3, 1 by performing the following push and pop operations: push 1, push 2, pop 2, push 3, push 4, pop 4, push 5, pop 5, pop 3, pop 1 .

Q: Describe the sequence of operations needed to rearrange three stacks from an initial configuration (A, B, C) to a final configuration (C, B, D, A) where the top element of the stack is specified.

Rearranging stacks from an initial (A, B, C) to (C, B, D, A) with B on top requires several specific push and pop operations: push elements from one stack to another to achieve the desired order. Detailed instruction depends on the specific setup of stacks s1, s2, and s3 .

Q: How can the order of stack operations affect the sequence of elements being popped, and what does this signify for stack-based algorithms?

The order of stack operations dictates the Last-In-First-Out nature of stacks. Modifying pop positions affects the returned sequence of elements, which is crucial for algorithms using stacks for depth-first traversal or backtracking, as order impacts result correctness .

Q: What method allows the efficient transfer of elements from a stack to simulate queue operations, and what is the main drawback?

Efficiently transferring stack elements involves using two stacks. Moving elements from a main stack to a temporary stack and back allows for queue simulation. The main drawback is increased time complexity during dequeue, as the operations are O(N).

Q: How can a queue be employed to function like a stack, specifically for push and pop operations using two queues?

To use a queue like a stack with two queues, for a push operation, enqueue the element into the main queue. For a pop operation, dequeue the main queue repeatedly to a temporary queue except for the last element, which is the stack-pop element. Then, revert elements back to the main queue .

Q: In a stack with elements 1, 2, and 3, describe how you would simulate a queue operation using two stacks.

To simulate a queue using two stacks, consider stack S1 as the main stack and stack S2 as a temporary stack. For dequeue, transfer elements from S1 to S2, pop the top of S2 (oldest element), then transfer remaining elements back to S1. For enqueue, push directly onto S1 .

Q: Can a particular sequence of operations always generate a desired popping order from a stack, and how does this relate to stack constraints?

Not all desired popping sequences are always possible due to LIFO constraints inherent in stacks. Operations must align with these rules; otherwise, certain orders can't be achieved without reordering push operations, illustrating limitations for flexible use scenarios .

This document discusses stacks and queues data structures. It provides examples of using stacks and queues to solve problems involving balanced parentheses, ordered pushing and popping of values, and simulating one data structure with the operations of another. Sample solutions are given using pseudocode to demonstrate pushing, popping, enqueueing and dequeuing elements from stacks and queues.

Uploaded by

Liaqat Hussain Bhatti

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

44 views6 pages

Stacks and Queues Exercises COMP 250

Uploaded by

Liaqat Hussain Bhatti

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

COMP 250 Fall 2017 Exercises 5 - stacks, queues

Questions
1. Consider the following sequence of stack operations:

push(d), push(h), pop(), push(f), push(s), pop(), pop(), push(m).

(a) Assume the stack is initially empty, what is the sequence of popped values, and what is
the final state of the stack? (Identify which end is the top of the stack.)
(b) Suppose you were to replace the push and pop operations with enqueue and dequeue
respectively. What would be the sequence of dequeued values, and what would be the
final state of the queue? (Identify which end is the front of the queue.)

2. Use a stack to test for balanced parentheses, when scanning the following expressions. Your
solution should show the state of the stack each time it is modified. The “state of the stack”
must indicate which is the top element.
Only consider the parentheses [,],(,),{,} . Ignore the variables and operators.

(a) [ a + { b / ( c - d ) + e / (f + g ) } - h ]
(b) [ a { b + [ c ( d + e ) - f ] + g }

3. Suppose you have a stack in which the values 1 through 5 must be pushed on the stack in
that order, but that an item on the stack can be popped at any time. Give a sequence of push
and pop operations such that the values are popped in the following order:

(a) 2, 4, 5, 3, 1
(b) 1, 5, 4, 2, 3
(c) 1, 3, 5, 4, 2

It might not be possible in each case.

4. (a) Suppose you have three stacks s1, s2, s2 with starting configuration shown on the left,
and finishing condition shown on the right. Give a sequence of push and pop operations
that take you from start to finish. For example, to pop the top element of s1 and push
it onto s3, you would write [Link]( [Link]()).

start finish
A A
B B
C D
D C
--- --- --- --- --- ---
s1 s2 s3 s1 s2 s3

(b) Same question, but now suppose the finish configuration on s3 is BDAC (with B on top) ?

last updated: 29th Sept, 2017 at 16:48 1

COMP 250 Fall 2017 Exercises 5 - stacks, queues

5. Consider the following sequence of stack commands:

push(a), push(b), push(c), pop(), push(d), push(e), pop(), pop(), pop(), pop().

(a) What is the order in which the elements are popped ? (Give a list and indicate which
was popped first.)
(b) Change the position of the pop() commands in the above sequence so that the items are
popped in the following order: b,d,c,a,e.
You are not allowed to change the ordering of the push commands.

I discussed the next two questions in the lecture (slides only)

6. Assume you have a stack with operations: push(), pop(), isEmpty(). How would you
use these stack operations to simulate a queue, in particular, the operations enqueue() and
dequeue()?
Hints: Use two stacks one of which is the main stack and one is a temporary one. You are
allowed use a while loop.
If you have no idea how to do this question or what is even being asked, then look at the
solutions. Once you understand the solutions, try to do the next question and resist looking
at the solution for that one.

7. Assume you have a queue with operations: enqueue(), dequeue(), isEmpty(). How would
you use the queue methods to simulate a stack, in particular, push() and pop() ?
Hint: use two queues, one of which is the main one and one is temporary.

last updated: 29th Sept, 2017 at 16:48 2

COMP 250 Fall 2017 Exercises 5 - stacks, queues

Answers
1. (a) Sequence of popped values: h,s,f. State of stack (from top to bottom): m, d
(b) Sequence of dequeued values: d,h,f. State of queue (from front to back): s,m.

2. (a) - means empty stack

[
[{
[{( TOP OF STACK IS ON THE RIGHT
[{
[{(
[{
[
- empty stack, so brackets match
(b) -
[
[{
[{[ TOP OF STACK IS ON THE RIGHT
[{[(
[{[
[{
[ stack not empty, so brackets don’t match

24531 15423 13542

push 1 push 1 push 1

push 2 pop pop
pop push 2 push 2
push 3 push 3 push 3
push 4 push 4 pop
pop push 5 push 4
push 5 pop push 5
pop pop pop
pop x pop
pop (not possible) pop

last updated: 29th Sept, 2017 at 16:48 3

COMP 250 Fall 2017 Exercises 5 - stacks, queues

5. (a) c (popped first), e, d, b, a

(b) push(a), push(b), pop(), push(c), push(d), pop(), pop(), pop() push(e), pop()

6. Here I present two solutions. Note that each requires that at least one of the enqueue() or
dequeue() operation is O(N ) where N is the size of the queue.

Solution 1

The first solution is to implement enqueue(e) simply by pushing the new element onto the
main stack s.

enqueue(e){
[Link](e)
}

In this solution, the bottom of the stack would be the front of the queue (containing the
element that has been in the queue longest) and the top of the stack is the back of the queue
(containing the least recently added element). How can we implement dequeue, that is, how
do we remove the bottom element of the stack?
The idea is to use a second stack tmpS. We first pop all items from the main stack s, and
push each popped element directly onto the second stack tmpS. We then pop the top element
of the second stack (which is the oldest element in the set). Finally, we refill the main stack
s by popping all elements from the second stack and pushing each back on to the first stack.

dequeue(){
tmpS <- new empty stack
while ![Link](){
[Link]( [Link]() )
}

last updated: 29th Sept, 2017 at 16:48 4

COMP 250 Fall 2017 Exercises 5 - stacks, queues

returnValue <- [Link]() // the dequeued element

while !([Link]()){
[Link]( [Link]() )
}
return returnValue
}

Solution 2

Here we let dequeue() be simple and just pop the stack. For this to work, the stack needs to
store the elements such that the oldest element is on top of the stack and the most recently
added element is at the bottom of the stack.

dequeue(){
return [Link]()
}

With this solution, enqueue(e) needs to do the heavy lifting: enqueue uses a temporary
stack to invert the order of elements currently in the main stack, so that the newest element
is on top of this temporary stack. Then it pushes the new element onto the empty main
stack. Then it copies all the elements back from the temporary stack to the main stack, using
pop-push. This recreates the original stack, but now the newest element has been added on
the bottom.

enqueue(e){
tmp <- new empty stack
while ! ([Link]()){
[Link]( [Link]() )
}
[Link](e)
while ! ([Link]()){
[Link]( [Link]())
}
}

last updated: 29th Sept, 2017 at 16:48 5

COMP 250 Fall 2017 Exercises 5 - stacks, queues

7. The concepts are similar to the previous question.

Solution 1

push(e){
[Link](e)
}

pop(){
tmpQ <- new empty queue
while ! ([Link]()){
tmpE <- [Link]()
if ! ([Link]())
[Link]( tmpE )
else{
while !( [Link]())
[Link]( [Link]())
return tmpE
}
}
}

Solution 2

Here the idea is similar, but now push does most of the work.

pop(){
[Link]()
}

push(e){
make a new empty queue qTmp
[Link](e)
while ![Link](){
[Link]( [Link]() )
}
q <- qTmp
return qTmp
}

last updated: 29th Sept, 2017 at 16:48 6

Common questions