I have this pseudo-code for implementing a queues with 2 stacks: makeQueue { Que
ID: 441410 • Letter: I
Question
I have this pseudo-code for implementing a queues with 2 stacks: makeQueue { Queue Q = new Queue(); Stack S1 = new Stack(); //represents Head of Queue Stack S2 = new Stack(); // represents Tail of Queue } //x is the object we want to Enqueue or Dequeue enqueue (Q , x) { Push(S2, x); } dequeue (Q) { if StackEmpty(S1) { while (!(S2.isempty()) { x = Pop(S2) push(S1, x) } } return pop(S1) } Now my question is: The time bounds in your analysis be improved by amortization. Come up with an appropriate 10 potential function and prove that your implementation enables each queue operation to be performed in O(1) amortized time. I'm not very sure what to do here. Any help would be great, and no copy paste answers from the internet please!Explanation / Answer
follow this defun enqueue (x xs) (cons x xs)) (defun dequeue (xs) (declare (xargs :guard (and (consp xs) (true-listp xs)))) (if (or (endp xs) (endp (rest xs))) (mv (first xs) nil) (mv-let (x ys) (dequeue (rest xs)) (mv x (cons (first xs) ys))))) (defun empty (xs) (endp xs)) [edit]Ada The first example below demonstrates a FIFO created for single-threaded computing. This version has the advantage of using a minimum of memory per FIFO element, and being very fast. The interface specification for a FIFO is described in the package specification. generic type Element_Type is private; package Fifo is type Fifo_Type is private; procedure Push(List : in out Fifo_Type; Item : in Element_Type); procedure Pop(List : in out Fifo_Type; Item : out Element_Type); function Is_Empty(List : Fifo_Type) return Boolean; Empty_Error : exception; private type Fifo_Element; type Fifo_Ptr is access Fifo_Element; type Fifo_Type is record Head : Fifo_Ptr := null; Tail : Fifo_Ptr := null; end record; type Fifo_Element is record Value : Element_Type; Next : Fifo_Ptr := null; end record; end Fifo; The FIFO implementation is described in the package body: with Ada.Unchecked_Deallocation; package body Fifo is ---------- -- Push -- ---------- procedure Push (List : in out Fifo_Type; Item : in Element_Type) is Temp : Fifo_Ptr := new Fifo_Element'(Item, null); begin if List.Tail = null then List.Tail := Temp; end if; if List.Head /= null then List.Head.Next := Temp; end if; List.Head := Temp; end Push; --------- -- Pop -- --------- procedure Pop (List : in out Fifo_Type; Item : out Element_Type) is procedure Free is new Ada.Unchecked_Deallocation(Fifo_Element, Fifo_Ptr); Temp : Fifo_Ptr := List.Tail; begin if List.Head = null then raise Empty_Error; end if; Item := List.Tail.Value; List.Tail := List.Tail.Next; if List.Tail = null then List.Head := null; end if; Free(Temp); end Pop; -------------- -- Is_Empty -- -------------- function Is_Empty (List : Fifo_Type) return Boolean is begin return List.Head = null; end Is_Empty; end Fifo; A "main" procedure for this program is: with Fifo; with Ada.Text_Io; use Ada.Text_Io; procedure Fifo_Test is package Int_Fifo is new Fifo(Integer); use Int_Fifo; My_Fifo : Fifo_Type; Val : Integer; begin for I in 1..10 loop Push(My_Fifo, I); end loop; while not Is_Empty(My_Fifo) loop Pop(My_Fifo, Val); Put_Line(Integer'Image(Val)); end loop; end Fifo_Test; The following implementation produces equivalent functionality by deriving from the standard Ada Container type Doubly_Linked_Lists. This example needs fewer lines of code on the part of the application programmer, but the implementation is less efficient than the previous example. Each element has all the data members needed for a doubly linked list. It also links in all the functionality of a doubly linked list. Most of that functionality is unneeded in a FIFO. with Ada.Containers.Doubly_Linked_Lists; generic type Element_Type is private; package Generic_Fifo is type Fifo_Type is tagged private; procedure Push(The_Fifo : in out Fifo_Type; Item : in Element_Type); procedure Pop(The_Fifo : in out Fifo_Type; Item : out Element_Type); Empty_Error : Exception; private package List_Pkg is new Ada.Containers.Doubly_Linked_Lists(Element_Type); use List_Pkg; Type Fifo_Type is new List with null record; end Generic_Fifo; package body Generic_Fifo is ---------- -- Push -- ---------- procedure Push (The_Fifo : in out Fifo_Type; Item : in Element_Type) is begin The_Fifo.Prepend(Item); end Push; --------- -- Pop -- --------- procedure Pop (The_Fifo : in out Fifo_Type; Item : out Element_Type) is begin if Is_Empty(The_Fifo) then raise Empty_Error; end if; Item := The_Fifo.Last_Element; The_Fifo.Delete_Last; end Pop; end Generic_Fifo; with Generic_Fifo; with Ada.Text_Io; use Ada.Text_Io; procedure Generic_Fifo_Test is package Int_Fifo is new Generic_Fifo(Integer); use Int_Fifo; My_Fifo : Fifo_Type; Val : Integer; begin for I in 1..10 loop My_Fifo.Push(I); end loop; while not My_Fifo.Is_Empty loop My_Fifo.Pop(Val); Put_Line(Integer'Image(Val)); end loop; end Generic_Fifo_Test; The function Is_Empty is inherited from the Lists type. The next two examples provide simple FIFO functionality for concurrent tasks. The buffer in each example holds a single value. When running concurrent tasks, one writing to the buffer, and one reading from the buffer, either the writer will be faster than the reader, or the reader will be faster than the writer. If the writer is faster a dynamic FIFO will grow to consume all available memory on the computer. If the reader is faster the FIFO will either contain a single value or it will be empty. In either case, no implementation is more efficient than a single element buffer. If we wish for the reader to read every value written by the writer we must synchronize the tasks. The writer can only write a new value when the buffer contains a stale value. The reader can only read a value when the value is fresh. This synchronization forces the two tasks to run at the same speed. generic type Element_Type is private; package Synchronous_Fifo is protected type Fifo is entry Push(Item : Element_Type); entry Pop(Item : out Element_Type); private Value : Element_Type; Is_New : Boolean := False; end Fifo; end Synchronous_Fifo; package body Synchronous_Fifo is ---------- -- Fifo -- ---------- protected body Fifo is --------- -- Push -- --------- entry Push (Item : Element_Type) when not Is_New is begin Value := Item; Is_New := True; end Push; --------- -- Pop -- --------- entry Pop (Item : out Element_Type) when Is_New is begin Item := Value; Is_New := False; end Pop; end Fifo; end Synchronous_Fifo;