3. a) A stack is an Abstract Data Type (ADT). Basic operations of stack arePUSH, POP, PEEK/TOP. Implement a stack using singly linked list thatsupport basic operations.b)Consider a circular queue as shown inFigure: 1. Demonstrate the followingoperations.Stepl: dequeue(), dequeue()frontStep2: enqueue(45), enqueue(55),enque(65), enqueue(75)Step3: enqueue(85), enque(95), enque(105)RearYou have to show the resultant queue as wellas value of two pointers – Front and Rearafter completion of each step.Figure: 1.

Answered: Image /qna-images/answer/6634332b-675f-4b9c-8e38-0b348086b996.jpg

3. a) A stack is an Abstract Data Type (ADI). Basic operations of stack are PUSH, POP, PEEK/TOP. Implement a stack using singly linked list that support basic operations. b) Consider a circular queue as shown in Figure: 1. Demonstrate the following front operations. Stepl: dequeue(), dequeue() Step2: enqueue(45), enqueue(55), enque(65), enqueue(75) Step3: enqueue(85), enque(95), enque(105) Rear You have to show the resultant queue as well as value of two pointers – Front and Rear after completion of each step. Figure: 1. 00

3. a) A stack is an Abstract Data Type (ADI). Basic operations of stack are PUSH, POP, PEEK/TOP. Implement a stack using singly linked list that support basic operations. b) Consider a circular queue as shown in Figure: 1. Demonstrate the following front operations. Stepl: dequeue(), dequeue() Step2: enqueue(45), enqueue(55), enque(65), enqueue(75) Step3: enqueue(85), enque(95), enque(105) Rear You have to show the resultant queue as well as value of two pointers – Front and Rear after completion of each step. Figure: 1. 00

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter18: Stacks And Queues

Section: Chapter Questions

Problem 21SA

See similar textbooks

Similar questions

1. Draw a picture of how a Stack and Queue is implemented with a single linked list.2. Explain and create algorithms for adding and removing on Stack and Queue
2. 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 queue
Stack, Queue and Deque5.1. Understand the basic operations for Stack, Queue and DequeExample: Suppose that Queue q is implemented by a circular array data with the size 3. Please drawthe state of the Queue q and circular array data after each of the following steps.1) Queue q = new Queue();2) q.enqueue(5);3) q.enqueue (2);4) q.enqueue (9);
The Deque ADT combines characteristics of the Stack and the Queue. The name “Deque" comes from "double-ended queue" and is usually pronounced "deck". Like the Stack and the Queue, a Deque permits elements to be accessed only at the ends. However, a Deque allows items to be added at either end and removed from either end. We can refer to the operations supported by the Deque as enqueueFront, enqueueRear, dequeueFront, and dequeueRear. Note that once you have a Deque, you can use it to implement both the Stack and the Queue. Implement the Deque using a dynamic, linked implementation (15pts) Use your Deque to implement a Stack (15pts). Use your Deque to implement a Queue (15pts). Test your implementation across the 3 data structures to tell the story of your work (10pts).
1. 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.
2. An ordered stack is a data structure that stores a sequence of items and supports the following operations. • OrderedPush(x): removes all items smaller than x from the beginning of the sequence and then adds x to the beginning of the sequence. • Pop: deletes and returns the first item in the sequence (or Null if the sequence is empty). Suppose we implement an ordered stack with a simple linked list, using the obvious OrderedPush and Pop algorithms. Prove that if we start with an empty data structure, the amortized cost of each OrderedPush or Pop operation is O(1).
Front and rear pointers are tracked in the linked list implementation of a queue. During insertion into the EMPTY queue, which of these pointers will change? (A Both front and rear pointer B Only front pointer Only rear pointer (D No pointer will be changed
3. a) A queue is an Abstract Data Type (ADT). Basic operations of queue are ENQUEUE, DEQUEUE, PEEK/FRONT. Implement a circular queue using array that supports basic operations. b) The Figure: 1 shows an integer stack. Demonstrate the following operations. Stepl: PUSH (35) Step 2: POP), POРО), РОР), Step 3: POP() 40 Step 4: PUSH(25), PUSH(35), PUSH(45), PUSH(55), 30 PUSH(65), PUSH(75) You have to show the resultant stack as well as the value ТОР %3D 1 of pointer TOP after completion of each step. Figure: 1
Data Structures and algorithms: Language: Java Please solve this on urgent basis: Attach output's picture, programe should must be error free and run able and explain every statement in commments: write a program for Stack implementation by using LinkedList it should follow the rules and have all the basic functionalities of a Stack.
Your 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)
Consider the following code segment , The variable q is an object of type Queue, the variable s is an object of type Stack. peek method looks at the first element in the queue without removing it. the remove method removes the first element from the queue. add method adds an element to the and of the queue or add an element to the top of the stack. pop method removes an element from the top of the stack What would be the content of the variable q (8 numbers) after we complete the second while loop in the code for (int i = 30; i <= 40; i ++) { if(i % 3 == 0) q.add(i); } while (!q.isEmpty()) { s.add(q.peek()); s.add(q.peek()); q.remove(); } while (!s.isEmpty()) { q.add(s.pop()); }
A SpecialStackTM is a stack modified to support the following two operations: PUSHCLEAR(v) successively pops consecutive items from the top of the stack that are less than u, then pushes v onto the stack. POP() deletes the item at the top of the stack. Assume these operations are implemented using a singly-linked list. PUSHCLEAR(v) iter- ates through the linked list to pop the applicable items and then adds v to the beginning. POP() deletes the first item. (a) Describe the ordering of values on the stack. (b) Explain how a single call to PUSHCLEAR(V) could take (n) time. (c) If we assume that every operation takes linear time, we get a naive bound of O(n²) on the total runtime. But this doesn't consider the fact that these expensive operations happen infrequently so let's analyze it more closely. Show that any sequence of n operations takes O(n) time. -