Question

Write a program that uses linked lists in order to support the following operations:

1. PUSH (S, x) - pushes a value x into a stack S

2. POP (S, i) - gets a number i (positive integer) and pops i numbers of S. If S contains less than i values, the operation is impossible to execute (program prints ERROR in this case – see below).

3. REVERSE (S) - reverse the order of the elements in S (you might want to apply recursion). If, for example, S is a stack and x was the last inserted, from now on x is treated as the first inserted element.

4. QUEUE (S) - declares that from this moment S becomes and acts like a queue. Nothing is printed after this operation.

5. ENQUEUE(S, x) - adds x to a queue

6. DEQUEUE(S) - removes element when S is a queue.

7. STACK(S) - makes S into a stack. Nothing is printed after this operation is executed.

8. AVERAGE(S) - returns the average of the numbers in S The program reads a sequence of strings, names of the operations, and additional value (when required).

The program prints the values in S after each operation is executed unless it’s stated otherwise. If S is empty, program prints EMPTY. The program prints ERROR in case and the operation is impossible to execute. Assume, the program starts with empty stack. Assume, the values are positive integers. The program ends when the string END is entered. Assume, the operation AVERAGE returns 0.0 if S is empty. For every operation the program must state its running time – write this in comments. Each important statement in your program must be documented in comments.

Example 1: Input:

AVERAGE

PUSH 4

PUSH 5

PUSH 7

PUSH 9

POP 2

PUSH 11

PUSH 6

REVERSE

Answer 1

SOLUTION:

below here is the python code of your problem

class Stack: //Class stack
def _init_(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self,item): //Push(S, x)
self.items.append(item)
return self.items
def pop(self): //Pop(S, i)
if self.items == []:
return 0
self.items.pop()
def peek(self):
if self.items == []:
return 0
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)

def getStackItems(self): // STACK(S)
return self.items

def reverse(string): //Reverse(S)
stack = Stack()
ls = []
newstr = ""
for i in string:
stack.push(i)
ls = stack.getStackItems()
for j in range(len(ls)):
newstr += ls.pop()
print(newstr)

reverse("testing")

class Queue: //Queue Implementation
def _init_(self):
self.items=[]
def enqueue(self,item): //ENQUEUE(S, x)
self.items.insert(0,item)
def dequeue(self): //DEQUEUE(S)
if(not self.isEmpty()):
return self.items.pop()
def isEmpty(self):
return self.items==[]
def size(self):
return len(self.items)

All operations are O(1)

**Fell free to ask any queries in the comment section. I am happy to help you. if you like our work, please give Thumbs up**