Stack:
Stack is a container in which elements inserted and removed in LIFO (Last In First Out) manner.
- “top” is address of top element of stack.
- Basic stack operations are given below:
- push(): Insert an object into stack top.
- pop(): Delete object in stack top.
- top(): Get object in stack top.
Explanation of Solution
- a.
Given stack is “S” and the additional stacks are “S1” and “S2”.
The elements in stack “S” can be reverse as shown below:
- First pop each element from “S” and push it into “S1” till “S” becomes empty.
- Pop each element from “S1” and push it into “S2” till “S1” becomes empty.
- Pop each element from “S2” and push it into “S” till “S2” becomes empty.
- Now “S” contains elements in reverse order.
Example,
Initially “S” contains 1, 2, 3 and 4.
First pop each element from “S” and push it into “S1”.
Then pop each element from “S1” and push it into “S2”.
Last pop each element from “S2” and push it into “S”.
Finally “S” contains in reverse order.
Queue:
- Queue is another data structure in which insertion and removal of elements are in FIFO(First In First Out) manner.
- Basic operations are given below:
- Enqueue: Insert element into back of queue.
- Dequeue: Remove item from queue’s front.
Explanation of Solution
- b.
Given stack is “S” and additional queue is “Q”.
The elements in stack “S” can be reverse as shown below:
- Pop each element from “S” and insert it into “Q” till “S” becomes empty.
- Delete each element from “Q” and push it into “S” till “Q” becomes empty.
- Now stack “S” contains elements in reverse order.
Example,
Initially “S” contains 1, 2, 3 and 4.
First pop each element from “S” and insert it into “Q”.
Then delete each element from “Q” and push it into “S”.
Finally, “S” contains in reverse order.
Explanation of Solution
- c.
Given stack is “S”, additional stack is “S1” and additional variables are “Num”, Num2 and “top_element”. The elements in stack “S” can be reverse as shown below.
- “Num” is number of elements initially in stack “S”.
- Decrement “Num” by one.
- Till “Num” becomes zero.
- Equate “Num” into “Num2”.
- Pop stack top of “S” and store in “top_element”.
- Pop “Num2” elements from “S” and push into “S1”.
- Then push element in “top_element” into “S”.
- Then pop each element from “S1” and push into “S” till “S1” becomes empty.
- Decrement value of “Num” by one.
- Finally “S” contains elements in reverse order.
Example,
Initially “S” contains 1, 2, 3 and 4. Stack contains four elements. So, “Num” is 4. Decrement it by one.
First iteration:
“Num” is 3, pop stack top and store in “top_element”. Then pop other three elements from “S” and push into “S1”.
- Then push element in “top_element” into “S” and pop each element from “S1” and push into “S”.
Second iteration:
“Num” is 2, pop stack top and store in “top_element”. Then pop other two elements from “S” and push into “S1”.
- Push element in “top_element” into “S” and pop each element from “S1” and push into “S”.
Third iteration:
“Num” is 1, pop stack top and store in “top_element”. Then pop one element from “S” and push into “S1”.
- Push element in “top_element” into “S” and pop each element from “S1” and push into “S”
Fourth iteration:
“Num” is 0, exit loop.
Finally, the stack “S” contains elements in reverse order.
Want to see more full solutions like this?
Chapter 4 Solutions
EBK DATA STRUCTURES AND ALGORITHMS IN C
- Queues and stacks can be implemented by using linked list structure. To implement "pop" and "push" methods of stack, ... and .. methods of linked list can be used, respectively. To implement "enqueue" and "dequeue" methods of queue, .. and. methods of linked list can be used, respectively. Fill in the blank with correct answers. O pop_front - push_back - pop_back - push_back O pop_back - push_front - pop_front - push_front pop_back - push_back - pop_front - push_back O push_back - pop_back - push_back - pop_frontarrow_forward13. If a stack is implemented under a Single- LinkedList, how much time does a stack pop an item out and maintain the top information? а. О(1) b. O(n) с. 0(n?) d. 0(log n)arrow_forwardThere is one stacks and one queue q and then following operations are performed upon these two. Push A, enqueue B, push C, pop, pop, enqueue D, push E, dequeue, enqueue F .What is the total number of elements, which are left in the queue and stack in the end.arrow_forward
- Explain how to implementing the stack push(), pop(), and size() methods using Queue data structure. Derive complexities for each method in your stack. Just Explain (No code is required) Hint: Use multiple Queues.arrow_forwardConsider the Queue ADT: Queue: enqueue(x) adds x to the back of the queue dequeue () removes element at the front of the queue size() returns number of elements in queue Select all options that allow for an efficient implementation based on the discussions from class. For any array implementation, you can assume the array is large enough so that making a larger one is not needed when pushing an item to the stack. You can assume that a linked list will have both a head and tail reference. Using an array with the front of the queue at the front of the array. Using an array with the front of the queue at the back of the array. Using a singly linked list with the front of the queue at the head of the list. Using a singly linked list with the front of the queue at the tail of the list. None of these choices allows for an efficient implementation of all methods.arrow_forwardConsider the Stack ADT: Stack: push(x) adds x to top of stack pop() removes top element of stack and returns it size() returns number of elements in stack Select all options that allow for an efficient implementation based on the discussions from class. For any array implementation, you can assume the array is large enough so that making a larger one is not needed when pushing an item to the stack. Using an array with the top at the front of the array. Using an array with the top at the back of the array. Using a singly linked list with the top at the head of the list. Using a singly linked list with the top at the tail of the list. ENGarrow_forward
- Why do we have to go to the trouble of building a circular array stack? The implementation of queues must take the form of a circular array for some reason.arrow_forwardYour job is to implement a Stack using only a Queue(s). That is, you will be responsible for writing the push and pop methods for a Stack but your internal data representation must be a Queue: void push(Queue& queue, int element) int pop(Queue& queue)arrow_forwardObjectives: The code for the different stack and queue operations in both implementations (array and linked list) are discussed in the lectures: and are written in the lectures power point. So the main object of this assignment is to give the student more practice to increase their understanding of the different implementation of these operations. - The students also are asked to write by themselves the main methods in the different exercises below; The Lab procedures: The following files must be distributed to the students in the Lab // it represents an array implementation of the stack. // it represents a Linked List implementation of the stack. arraylmpofStack.java pointerlmofStack.java pointerlmofQueue.java // it represents a pointer implementation of the queue. Then the students by themselves are required to write the code for the following questions Ex1) Given the file arraylmpofStack.java then write a main method to read a sequence of numbers and using the stack operation print…arrow_forward
- Compare an Array, Single Linked List and Circular Linked List. Which is better to use in general and why? Which one is better for implementing a Queue or Stack?arrow_forward2. Given the following stack A = { 29,18,10,15,20,9,5,13,2,4,15} Create a queue by taking the elements from the top of the stack and adding them to a queuearrow_forwardObjectives: The code for the different stack and queue operations in both implementations (array and linked list) are discussed in the lectures: and are written in the lectures power point. So the main object of this assignment is to give the student more practice to increase their understanding of the different implementation of these operations. - The students also are asked to write by themselves the main methods in the different exercises below; The Lab procedures: The following files must be distributed to the students in the Lab - arrayImpOfStack.java // it represents an array implementation of the stack. - pointerImOfStack.java // it represents a Linked List implementation of the stack. - pointerImOfQueue.java // it represents a pointer implementation of the queue. Then the students by themselves are required to write the code for the following questions Ex1) Given the file arrayImpOfStack.java then write a main method to read a sequence of numbers and using the stack…arrow_forward
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education