Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
In this problem you will design a data structure that implements Stack ADT using singly-linked list instead of an array. In addition your stack will have the following additional operation: public catenate (Stack s); // appends the contents of Stack s to the current stack The new operation will have the following properties: Let n = s₁.size(), m= s2.size(). Then executing s₁.catenate(s2) results in the following: 1. The new size of s₁ is the sum of the size of s2 and the original size of s₁, i.e., the following evaluates to true: s₁.size() == n + m 2. Top n elements of s₁ after the call s₁.catenate(s2) are the same as the elements of s₁ before the call. The bottom m elements of s₁ after the call s₁.catenate(s2) are the same as the elements of S2 before the call. (a) The implementation described in the book, lecture notes and screencasts uses an array to implement Stack ADT. Can you implement catenate (Stack s) operation that runs in O(1) time for such imple- mentation? If yes, write down the algorithm that achieves that and demonstrate that it runs in O(1) time. If not, describe what goes wrong. (b) Write down algorithms that implement the original Stack ADT using a singly-linked list instead of the array. That is, write down pseudocode for implementing each operation of Stack ADT: Stack (), push (Object o), pop(), size (), isEmpty (), top (). Make sure that each of the above opera- tions takes at most O(1) time in your implementation. (c) Design an algorithm that implements catenate (Stack s) operation in O(1) time. Write down the algorithm and demonstrate that it runs in O(1) time.

In this problem you will design a data structure that implements Stack ADT using singly-linked list instead of an array. In addition your stack will have the following additional operation: public catenate (Stack s); // appends the contents of Stack s to the current stack The new operation will have the following properties: Let n = s₁.size(), m= s2.size(). Then executing s₁.catenate(s2) results in the following: 1. The new size of s₁ is the sum of the size of s2 and the original size of s₁, i.e., the following evaluates to true: s₁.size() == n + m 2. Top n elements of s₁ after the call s₁.catenate(s2) are the same as the elements of s₁ before the call. The bottom m elements of s₁ after the call s₁.catenate(s2) are the same as the elements of S2 before the call. (a) The implementation described in the book, lecture notes and screencasts uses an array to implement Stack ADT. Can you implement catenate (Stack s) operation that runs in O(1) time for such imple- mentation? If yes, write down the algorithm that achieves that and demonstrate that it runs in O(1) time. If not, describe what goes wrong. (b) Write down algorithms that implement the original Stack ADT using a singly-linked list instead of the array. That is, write down pseudocode for implementing each operation of Stack ADT: Stack (), push (Object o), pop(), size (), isEmpty (), top (). Make sure that each of the above opera- tions takes at most O(1) time in your implementation. (c) Design an algorithm that implements catenate (Stack s) operation in O(1) time. Write down the algorithm and demonstrate that it runs in O(1) time.

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question
In this problem you will design a data structure that implements Stack ADT using singly-linked list instead of an array. In addition your stack will have the following additional operation: public catenate (Stack s); // appends the contents of Stack s to the current stack The new operation will have the following properties: Let n = s₁.size(), m= s2.size(). Then executing s₁.catenate(s2) results in the following: 1. The new size of s₁ is the sum of the size of s2 and the original size of s₁, i.e., the following evaluates to true: s₁.size() == n + m 2. Top n elements of s₁ after the call s₁.catenate(s2) are the same as the elements of s₁ before the call. The bottom m elements of s₁ after the call s₁.catenate(s2) are the same as the elements of S2 before the call. (a) The implementation described in the book, lecture notes and screencasts uses an array to implement Stack ADT. Can you implement catenate (Stack s) operation that runs in O(1) time for such imple- mentation? If yes, write down the algorithm that achieves that and demonstrate that it runs in O(1) time. If not, describe what goes wrong. (b) Write down algorithms that implement the original Stack ADT using a singly-linked list instead of the array. That is, write down pseudocode for implementing each operation of Stack ADT: Stack (), push (Object o), pop(), size (), isEmpty (), top (). Make sure that each of the above opera- tions takes at most O(1) time in your implementation. (c) Design an algorithm that implements catenate (Stack s) operation in O(1) time. Write down the algorithm and demonstrate that it runs in O(1) time.
Transcribed Image Text:In this problem you will design a data structure that implements Stack ADT using singly-linked list instead of an array. In addition your stack will have the following additional operation: public catenate (Stack s); // appends the contents of Stack s to the current stack The new operation will have the following properties: Let n = s₁.size(), m= s2.size(). Then executing s₁.catenate(s2) results in the following: 1. The new size of s₁ is the sum of the size of s2 and the original size of s₁, i.e., the following evaluates to true: s₁.size() == n + m 2. Top n elements of s₁ after the call s₁.catenate(s2) are the same as the elements of s₁ before the call. The bottom m elements of s₁ after the call s₁.catenate(s2) are the same as the elements of S2 before the call. (a) The implementation described in the book, lecture notes and screencasts uses an array to implement Stack ADT. Can you implement catenate (Stack s) operation that runs in O(1) time for such imple- mentation? If yes, write down the algorithm that achieves that and demonstrate that it runs in O(1) time. If not, describe what goes wrong. (b) Write down algorithms that implement the original Stack ADT using a singly-linked list instead of the array. That is, write down pseudocode for implementing each operation of Stack ADT: Stack (), push (Object o), pop(), size (), isEmpty (), top (). Make sure that each of the above opera- tions takes at most O(1) time in your implementation. (c) Design an algorithm that implements catenate (Stack s) operation in O(1) time. Write down the algorithm and demonstrate that it runs in O(1) time.
AI-Generated Solution
AI-generated content may present inaccurate or offensive content that does not represent bartleby’s views.
steps

Unlock instant AI solutions

Tap the button
to generate a solution

SEE SOLUTION
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS