Question

How to implement a queue using two stacks in Pascal

Answer 1

program QueueUsingTwoStacks;

{$mode objfpc}{$H+}

{
    Queue implemented using two stacks in Free Pascal.

    Concept:
    - stackIn  : receives new elements (enqueue)
    - stackOut : serves elements in correct queue order (dequeue)

    When stackOut is empty and we need to dequeue or peek:
    - Move all elements from stackIn to stackOut
      This reverses the order, making the oldest element accessible.

    This design provides amortized O(1) operations and keeps the code simple.
}

uses
    SysUtils;  { for BoolToStr }

type
    TIntArray = array of Integer;

    TStack = record
        Data: TIntArray;
        Size: Integer;
    end;

    TQueue = record
        StackIn:  TStack;
        StackOut: TStack;
    end;

procedure InitStack(var S: TStack);
begin
    SetLength(S.Data, 4);
    S.Size := 0;
end;

procedure Push(var S: TStack; Value: Integer);
begin
    if S.Size = Length(S.Data) then
        SetLength(S.Data, Length(S.Data) * 2);

    S.Data[S.Size] := Value;
    Inc(S.Size);
end;

function Pop(var S: TStack): Integer;
begin
    if S.Size = 0 then
    begin
        WriteLn('Stack underflow');
        Halt(1);
    end;

    Dec(S.Size);
    Pop := S.Data[S.Size];
end;

function Top(const S: TStack): Integer;
begin
    if S.Size = 0 then
    begin
        WriteLn('Stack is empty');
        Halt(1);
    end;

    Top := S.Data[S.Size - 1];
end;

function IsEmpty(const S: TStack): Boolean;
begin
    IsEmpty := (S.Size = 0);
end;

procedure InitQueue(var Q: TQueue);
begin
    InitStack(Q.StackIn);
    InitStack(Q.StackOut);
end;

procedure TransferIfNeeded(var Q: TQueue);
begin
    if IsEmpty(Q.StackOut) then
    begin
        while not IsEmpty(Q.StackIn) do
            Push(Q.StackOut, Pop(Q.StackIn));
    end;
end;

procedure Enqueue(var Q: TQueue; Value: Integer);
begin
    Push(Q.StackIn, Value);
end;

function Dequeue(var Q: TQueue): Integer;
begin
    TransferIfNeeded(Q);
    if IsEmpty(Q.StackOut) then
    begin
        WriteLn('Queue is empty');
        Halt(1);
    end;

    Dequeue := Pop(Q.StackOut);
end;

function Front(var Q: TQueue): Integer;
begin
    TransferIfNeeded(Q);
    if IsEmpty(Q.StackOut) then
    begin
        WriteLn('Queue is empty');
        Halt(1);
    end;

    Front := Top(Q.StackOut);
end;

function QueueEmpty(const Q: TQueue): Boolean;
begin
    QueueEmpty := IsEmpty(Q.StackIn) and IsEmpty(Q.StackOut);
end;

var
    Q: TQueue;

begin
    InitQueue(Q);

    Enqueue(Q, 10);
    Enqueue(Q, 20);
    Enqueue(Q, 30);

    WriteLn('Front element: ', Front(Q));

    WriteLn('Dequeued: ', Dequeue(Q));
    WriteLn('Dequeued: ', Dequeue(Q));

    Enqueue(Q, 40);

    WriteLn('Front element: ', Front(Q));

    WriteLn('Dequeued: ', Dequeue(Q));
    WriteLn('Dequeued: ', Dequeue(Q));

    WriteLn('Queue empty: ', BoolToStr(QueueEmpty(Q), True));
end.


{
run:

Front element: 10
Dequeued: 10
Dequeued: 20
Front element: 30
Dequeued: 30
Dequeued: 40
Queue empty: True

}

 

70+ SQL courses for beginners and professionals