1.
STACK DATA STRUCTURE
1.1 Stack Declaration and Initialization
CONSTANT MAXSIZE = 10
DECLARE Stack : ARRAY[0:MAXSIZE] OF INTEGER
DECLARE Top : INTEGER
Top ← -1
1.2 Stack Operations
FUNCTION IsEmpty() RETURNS BOOLEAN
IF Top = -1 THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
FUNCTION IsFull() RETURNS BOOLEAN
IF Top = MAXSIZE THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
FUNCTION Peek() RETURNS INTEGER
IF NOT IsEmpty() THEN
RETURN Stack[Top]
ELSE
OUTPUT "Stack is empty"
RETURN -1
ENDIF
ENDFUNCTION
FUNCTION Pop() RETURNS INTEGER
DECLARE Data : INTEGER
IF NOT IsEmpty() THEN
Data ← Stack[Top]
Top ← Top - 1
RETURN Data
ELSE
OUTPUT "Stack is empty"
RETURN -1
ENDIF
ENDFUNCTION
PROCEDURE Push(Data : INTEGER)
IF NOT IsFull() THEN
Top ← Top + 1
Stack[Top] ← Data
ELSE
OUTPUT "Stack is full"
ENDIF
ENDPROCEDURE
2. CIRCULAR QUEUE DATA STRUCTURE
2.1 Circular Queue Declaration
CONSTANT SIZE = 10
DECLARE Queue : ARRAY[0:SIZE-1] OF INTEGER
DECLARE Front, Rear : INTEGER
Front ← -1
Rear ← -1
2.2 Circular Queue Operations
FUNCTION IsFull() RETURNS BOOLEAN
IF (Front = 0 AND Rear = SIZE - 1) OR (Front = Rear + 1) THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
FUNCTION IsEmpty() RETURNS BOOLEAN
IF Front = -1 THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
PROCEDURE EnQueue(Element : INTEGER)
IF IsFull() THEN
OUTPUT "Queue is full"
ELSE
IF Front = -1 THEN
Front ← 0
ENDIF
Rear ← (Rear + 1) MOD SIZE
Queue[Rear] ← Element
OUTPUT Element, " inserted"
ENDIF
ENDPROCEDURE
FUNCTION DeQueue() RETURNS INTEGER
DECLARE Element : INTEGER
IF IsEmpty() THEN
OUTPUT "Queue is empty"
RETURN -1
ELSE
Element ← Queue[Front]
IF Front = Rear THEN
Front ← -1
Rear ← -1
ELSE
Front ← (Front + 1) MOD SIZE
ENDIF
RETURN Element
ENDIF
ENDFUNCTION
PROCEDURE Display()
DECLARE i : INTEGER
IF IsEmpty() THEN
OUTPUT "Queue is empty"
ELSE
OUTPUT "Front -> ", Front
i ← Front
WHILE TRUE
OUTPUT Queue[i]
IF i = Rear THEN
EXIT WHILE
ENDIF
i ← (i + 1) MOD SIZE
ENDWHILE
OUTPUT "Rear -> ", Rear
ENDIF
ENDPROCEDURE
3. LINKED LIST DATA STRUCTURE
3.1 Type Declaration and Constants
CONSTANT NullPointer = -1
CONSTANT ListSize = 10
//Create record of node
TYPE ListNode
DECLARE Data : STRING
DECLARE Pointer : INTEGER
ENDTYPE
DECLARE StartPointer : INTEGER
DECLARE FreeListPtr : INTEGER
DECLARE List : ARRAY[0:ListSize] OF ListNode
3.2 Linked List Operations
PROCEDURE InitialiseList()
StartPointer ← NullPointer
FreeListPtr ← 0
FOR Index ← 0 TO ListSize - 1
List[Index].Pointer ← Index + 1
NEXT Index
List[ListSize].Pointer ← NullPointer
ENDPROCEDURE
FUNCTION IsListFull() RETURNS BOOLEAN
IF FreeListPtr = NullPointer THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
Insert Node at Start
1. Take a new node from the free list.
2. Move the free pointer to the next free node.
3. Store the data in the new node.
4. Set the next pointer of the new node to the value of start.
5. Replace start with the address of the new node.
PROCEDURE InsertNode(NewItem : STRING)
DECLARE NewPtr : INTEGER
IF IsListFull() THEN
OUTPUT "List is full"
ELSE
NewPtr ← FreeListPtr
FreeListPtr ← List[FreeListPtr].Pointer
List[NewPtr].Data ← NewItem
List[NewPtr].Pointer ← StartPointer
StartPointer ← NewPtr
ENDIF
ENDPROCEDURE
Find a Node in Linked List
1. Start searching from the start node.
2. Save the start pointer in a new pointer called current.
3. Use a while loop to traverse the list until
o the required item is found, or
o the list ends.
4. If the item is found, return the current pointer.
5. If the list ends and the item is not found, return NULL.
FUNCTION FindNode(DataItem : STRING) RETURNS INTEGER
DECLARE CurrentNodePtr : INTEGER
CurrentNodePtr ← StartPointer
WHILE CurrentNodePtr <> NullPointer AND List[CurrentNodePtr].Data <> DataItem
CurrentNodePtr ← List[CurrentNodePtr].Pointer
ENDWHILE
RETURN CurrentNodePtr
ENDFUNCTION
Delete Node from Linked List
1. Save the start pointer in a new pointer called current.
2. Set the previous pointer to NULL.
3. Use a while loop to move through the list until
o the node to be deleted is found, or
o the list ends.
4. Inside the loop, move both pointers forward:
o Set previous to current
o Set current to the next node of current
5. After the loop:
o If current is NULL, the data item is not found (stop).
6. If previous is NULL: //or start=current
o Delete the first node
o Set start to the next node of current
7. Otherwise:
o Delete a node from the middle or end
o Set the next pointer of previous to the next pointer of current
8. Attach the deleted node to the free list:
o Set the next pointer of current to free
o Set free to current
PROCEDURE DeleteNode(DataItem : STRING)
DECLARE ThisNodePtr, PreviousNodePtr : INTEGER
IF StartPointer = NullPointer THEN
OUTPUT "List is empty"
ELSE
ThisNodePtr ← StartPointer
PreviousNodePtr ← NullPointer
WHILE ThisNodePtr <> NullPointer AND List[ThisNodePtr].Data <> DataItem
PreviousNodePtr ← ThisNodePtr
ThisNodePtr ← List[ThisNodePtr].Pointer
ENDWHILE
IF ThisNodePtr <> NullPointer THEN
IF PreviousNodePtr=NullPointer THEN
StartPointer ← List[StartPointer].Pointer
ELSE
List[PreviousNodePtr].Pointer ← List[ThisNodePtr].Pointer
ENDIF
List[ThisNodePtr].Pointer ← FreeListPtr
FreeListPtr ← ThisNodePtr
ELSE
OUTPUT "Data not found"
ENDIF
ENDIF
ENDPROCEDURE
PROCEDURE OutputAllNodes()
DECLARE CurrentNodePtr : INTEGER
CurrentNodePtr ← StartPointer
WHILE CurrentNodePtr <> NullPointer
OUTPUT List[CurrentNodePtr].Data
CurrentNodePtr ← List[CurrentNodePtr].Pointer
ENDWHILE
ENDPROCEDURE
Ordered Insert in Linked List
1. Take a new node from the free list.
2. Move the free pointer to the next free node.
3. Store the data in the new node.
4. Traverse the list using pointers until the correct position is found
(where the current node’s data is greater than the new data).
5. If the new node is to be inserted at the start:
o Set the next pointer of the new node to the value of start
o Replace start with the address of the new node
6. If the new node is to be inserted in the middle or at the end:
o Set the next pointer of the new node to the value of current
o Set the next pointer of previous to the address of the new node
PROCEDURE InsertNodeOrdered(NewItem : STRING)
DECLARE NewNodePtr, ThisNodePtr, PreviousNodePtr : INTEGER
IF IsListFull() THEN
OUTPUT "List is full"
ELSE
NewNodePtr ← FreeListPtr
FreeListPtr ← List[FreeListPtr].Pointer
List[NewNodePtr].Data ← NewItem
ThisNodePtr ← StartPointer
PreviousNodePtr ← NullPointer
WHILE ThisNodePtr <> NullPointer AND List[ThisNodePtr].Data < NewItem
PreviousNodePtr ← ThisNodePtr
ThisNodePtr ← List[ThisNodePtr].Pointer
ENDWHILE
IF PreviousNodePtr = NullPointer THEN
List[NewNodePtr].Pointer ← StartPointer
StartPointer ← NewNodePtr
ELSE
List[NewNodePtr].Pointer ← List[PreviousNodePtr].Pointer
List[PreviousNodePtr].Pointer ← NewNodePtr
ENDIF
ENDIF
ENDPROCEDURE
4. BINARY TREE DATA STRUCTURE
4.1 Type Declaration and Constants
CONSTANT NullPointer = -1
CONSTANT TreeSize = 10
TYPE TreeNode
DECLARE Data : STRING
DECLARE LeftPointer : INTEGER
DECLARE RightPointer : INTEGER
ENDTYPE
DECLARE RootPointer : INTEGER
DECLARE FreePtr : INTEGER
DECLARE Tree : ARRAY[0:TreeSize] OF TreeNode
4.2 Binary Tree Operations
PROCEDURE InitialiseTree()
RootPointer ← NullPointer
FreePtr ← 0
FOR Index ← 0 TO TreeSize - 1
Tree[Index].LeftPointer ← Index + 1
NEXT Index
Tree[TreeSize].LeftPointer ← NullPointer
ENDPROCEDURE
FUNCTION IsTreeFull() RETURNS BOOLEAN
IF FreePtr = NullPointer THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
PROCEDURE InsertNode(NewItem : STRING)
DECLARE NewPtr, CurrentPtr, PreviousPtr : INTEGER
DECLARE Left : BOOLEAN
IF IsTreeFull() THEN
OUTPUT "Tree is full"
ELSE
NewPtr ← FreePtr
FreePtr ← Tree[FreePtr].LeftPointer
Tree[NewPtr].Data ← NewItem
Tree[NewPtr].LeftPointer ← NullPointer
Tree[NewPtr].RightPointer ← NullPointer
CurrentPtr ← RootPointer
IF CurrentPtr = NullPointer THEN
RootPointer ← NewPtr
ELSE
WHILE CurrentPtr <> NullPointer
PreviousPtr ← CurrentPtr
IF NewItem < Tree[CurrentPtr].Data THEN
Left ← TRUE
CurrentPtr ← Tree[CurrentPtr].LeftPointer
ELSE
Left ← FALSE
CurrentPtr ← Tree[CurrentPtr].RightPointer
ENDIF
ENDWHILE
IF Left = TRUE THEN
Tree[PreviousPtr].LeftPointer ← NewPtr
ELSE
Tree[PreviousPtr].RightPointer ← NewPtr
ENDIF
ENDIF
ENDIF
ENDPROCEDURE
5. QUEUE DATA STRUCTURE(2)
5.1 Queue Declaration
CONSTANT MaxSize = 10
DECLARE Queue : ARRAY[0:MaxSize-1] OF INTEGER
DECLARE Front, Rear, ItemCount : INTEGER
Front ← 0
Rear ← -1
ItemCount ← 0
5.2 Queue Operations
FUNCTION IsEmpty() RETURNS BOOLEAN
IF ItemCount = 0 THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
FUNCTION IsFull() RETURNS BOOLEAN
IF ItemCount = MaxSize THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
FUNCTION GetSize() RETURNS INTEGER
RETURN ItemCount
ENDFUNCTION
PROCEDURE Enqueue(Data : INTEGER)
IF IsFull() THEN
OUTPUT "Queue is full"
ELSE
Rear ← (Rear + 1) MOD MaxSize
Queue[Rear] ← Data
ItemCount ← ItemCount + 1
ENDIF
ENDPROCEDURE
FUNCTION Dequeue() RETURNS INTEGER
DECLARE Data : INTEGER
IF IsEmpty() THEN
OUTPUT "Queue is empty"
RETURN -1
ELSE
Data ← Queue[Front]
Front ← (Front + 1) MOD MaxSize
ItemCount ← ItemCount - 1
RETURN Data
ENDIF
ENDFUNCTION
KEY CONVENTIONS USED
1. Keywords: All keywords are in UPPERCASE (IF, THEN, ELSE, WHILE, etc.)
2. Assignment: Uses ← symbol for assignment
3. Data Types: INTEGER, STRING, BOOLEAN, ARRAY
4. Constants: Defined using CONSTANT keyword
5. Functions: Use FUNCTION...RETURNS...ENDFUNCTION structure
6. Procedures: Use PROCEDURE...ENDPROCEDURE structure
7. Comments: Use // for single-line comments
8. Array Declaration: DECLARE arrayName : ARRAY[lower:upper] OF dataType
9. Modulus Operation: Uses MOD keyword
10. Boolean Values: TRUE and FALSE in uppercase