Question 1: Say that we want to maintain both a Stack and a Queue of the same el

Question

Question 1: Say that we want to maintain both a Stack and a Queue of the same elements. A new element that arrives implies a Push to the Stack and a ENQUEUE to the Queue. Any Pop operation should remove the element from the QUEUE and from the Stack as well (even though for the Queue its not the highest propriety element). Dequeue removes the head of the queue, but also removes this element from the Stack (even though its not the last to being inserted). Using two copies of every element and using additional pointers between elements, show that we can implement both a stack and a queue so that every operation requires O(1) time. Please Explain your answer in pseudocode.

Explanation / Answer

Pseudo Code:-

create a stack and queue then perform your task as follows.

int stk[10], queue[10]

// ask the user whether he wants to perform insertion or deletion. If he select insertion then

//take input from the user in a variable like value

// use switch case

switch(x)

case 1: Push(value)

Enqueue(value)

break;

case 2: Pop()

Dequeue()

break;

default: wrong input

// switch ends

//define functions

Push(int)

If TOP==10

Print: OVERFLOW, and Return.
TOP =TOP + 1
stack[TOP] = value

//end push function

Pop()

If TOP == -1
Print: UNDERFLOW, and Return.
ITEM = stack[TOP]
TOP = TOP-1

//end pop function

Enqueue(int)

If FRONT = 1 and REAR = N
Print OVERFLOW, and Return.
If FRONT == NULL
FRONT=1

REAR=1

Else
REAR = REAR + 1.
//End of If

queue[REAR] = value

//end of Enqueue function

Dequeue()

If FRONT == NULL
Print UNDERFLOW, and Return.
temp := QUEUE[FRONT].
If FRONT == REAR
FRONT = NULL and REAR = NULL.
Else
FRONT = FRONT+1

//end dequeue function

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.