EXAM «Data Structure»
Nurlanova Adelina ITC-1-22
-Topic:
Write a Pseudo code to implement the stack and queue through a linked-list and
explain the Pseudo code.
Stack (LIFO) - A stack is a data structure where the last item added is the first
one removed (Last In, First Out, LIFO). The main operations are push (adding an
item) and pop (removing and returning the top item).
Pseudocode for Stack:
pseudo
Class Node
Data
Next
Class Stack
Top
Method Initialize
Top = Null
Method Push(value)
NewNode = New Node()
NewNode.Data = value
NewNode.Next = Top
Top = NewNode
Method Pop()
If Top == Null
Return Null // Stack is empty
Temp = Top
Top = Top.Next
Return Temp.Data
Method IsEmpty()
Return Top == Null
Explanation:
1. Node — a class for the node. A node has:
- Data — the value stored in the node.
- Next — a pointer to the next node in the list.
2. Stack — a class for the stack. The stack has:
- Top — a pointer to the top item of the stack.
3. Initialize — method to initialize the stack:
- Sets Top to Null, meaning the stack is empty.
4. Push(value) — method to add an item to the stack:
- Creates a new node (NewNode).
- Sets the data of the node to value.
- Sets NewNode.Next to the current top of the stack (Top).
- Updates Top to point to the new node, making it the top of the stack.
5. Pop() — method to remove and return the top item of the stack:
- If the stack is empty (Top == Null), returns Null.
- Otherwise, saves the current top node to Temp.
- Updates Top to point to the next node.
- Returns the data of the removed node (Temp.Data).
6. IsEmpty() — method to check if the stack is empty:
- Returns True if Top == Null, otherwise False.
Queue (FIFO) - A queue is a data structure where the first item added is the first
one removed (First In, First Out, FIFO). The main operations are enqueue (adding
an item) and dequeue (removing and returning the first item).
Pseudocode for Queue:
Class Queue
Front
Rear
Method Initialize
Front = Null
Rear = Null
Method Enqueue(value)
NewNode = New Node()
NewNode.Data = value
NewNode.Next = Null
If Rear == Null
Front = NewNode
Rear = NewNode
Else
Rear.Next = NewNode
Rear = NewNode
Method Dequeue()
If Front == Null
Return Null // Queue is empty
Temp = Front
Front = Front.Next
If Front == Null
Rear = Null
Return Temp.Data
Method IsEmpty()
Return Front == Null
Explanation:
1. Node — a class for the node. A node has:
- Data — the value stored in the node.
- Next — a pointer to the next node in the list.
2. Queue — a class for the queue. The queue has:
- Front — a pointer to the first item in the queue.
- Rear — a pointer to the last item in the queue.
3. Initialize — method to initialize the queue:
- Sets Front and Rear to Null, meaning the queue is empty.
4. Enqueue(value) — method to add an item to the queue:
- Creates a new node (NewNode).
- Sets the data of the node to value.
- Sets NewNode.Next to Null, since the new item will be at the end of the queue.
- If the queue is empty (Rear == Null), both Front and Rear point to the new
node.
- Otherwise, the current last node (Rear.Next) points to the new node, and Rear
is updated to the new node.
5. Dequeue() — method to remove and return the first item in the queue:
- If the queue is empty (Front == Null), returns Null.
- Otherwise, saves the current first node to Temp.
- Updates Front to point to the next node.
- If the queue becomes empty after removing the item (Front == Null), sets Rear
to Null.
- Returns the data of the removed node (Temp.Data).
6. IsEmpty() — method to check if the queue is empty:
- Returns True if Front == Null, otherwise False.
