ACSL Junior Division onwards includes data structure concepts. The data structures involveed are stacks, queues and binary search trees. This blog post talks about stacks and queues. We have covered binary search trees in another post.
What are Data Structures?
Data structures are important if you want to learn efficient algorithms. When you are working with a large amount of data, using data structures, you can manage and handle your data more efficiently and keep things organized. By using the correct and relevant type of data structure, you ensure that your algorithm and thereby program runs efficiently and without wasting time or cycles.
In ACSL Data Structures, you will be working with stacks, queues and binary search trees. Stacks and queues can be implemented using linked lists and arrays. There are different kinds of trees and binary search trees are a special kind of binary trees.
ACSL Junior Division includes only the basic math part of these three data structures.
Stacks
A stack is a data structure that uses the concept of Last In, First Out (LIFO). The first item added to a stack is the last item to be removed. The last item added to a stack is the first item that can be removed.
Examples of a stack are a stack of rocks and a bag of Pringles.
Stack of rocks
Stack of Parle-G biscuits
Stack Operations
There are two kinds of operations you can perform on stacks. They are PUSH and POP.
PUSH is used to add an item to the top of the stack. You cannot add an item to the middle or bottom of the stack.
PUSH("A") adds the item A to the top of the stack.
POP is used to remove an item from the top of the stack. You cannot remove an item in the middle or bottom of the stack.
X=POP() removes the item at the top of the stack and dumps it into variable X.
Stack Questions
We will work on a couple of stack-related questions that are relevant to ACSL contests.
Create a stack with these operations:
PUSH("A"), PUSH("C"), PUSH("E"), X=POP(), PUSH("S"), X=POP(), X=POP()
This is a sequence of the stack operations. The growth is from bottom to top.
Operation 1: PUSH("A"). A is the first item to be added and is at top of stack.
| Stack | PUSH("A") |
|---|---|
| A | â top of stack |
Operation 2: PUSH("C"). Now, C is at top of stack.
| Stack | PUSH("C") |
|---|---|
| C | â top of stack |
| A |
Operation 3: PUSH("E"). Now, E is at top of stack.
| Stack | PUSH("E") |
|---|---|
| E | â top of stack |
| C | |
| A |
Operation 4: X=POP(). We have our first POP operation, which removes E. Now, C is at top of the stack.
| Stack | X=POP() |
|---|---|
E |
E is removed. X takes the value of "E" |
| C | â top of stack |
| A |
Operation 5: PUSH("S"). Now, S is at top of stack.
| Stack | PUSH("S") |
|---|---|
| S | â top of stack |
| C | |
| A |
Operation 6: X=POP(). This POP operation removes S. Now, C is at top of stack.
| Stack | X=POP() |
|---|---|
S |
S is removed. X takes the value of "S" |
| C | â top of stack |
| A |
Operation 7: X=POP(). This POP operation removes C. Now, A is at top of stack.
| Stack | X=POP() |
|---|---|
C |
C is removed. X takes the value of "C" |
| A | â top of stack |
The resulting stack will look like this:
| Stack | |
|---|---|
| A | â top of stack |
1) Find the item at the top of the stack.
A
2) What was the last popped item?
C
Queues
A queue is a data structure that uses the concept of First In, First Out (FIFO). The first item added to a stack is the first item to be removed. The last item added to a stack is the last item that can be removed.
Examples of a queue are a queue of kids waiting for their turn to get ice cream.
Queue of children
Queue Operations
There are two kinds of operations you can perform on queues. They are PUSH and POP.
PUSH is used to add an item to the end of the queue. You cannot add an item to the front or middle of the stack.
PUSH("A") adds the item A to the end of the queue.
POP is used to remove an item from the front of the queue. You cannot remove an item at the middle or back of the queue.
X=POP() removes the item at the front of the queue and dumps it into variable X.
Queue Questions
We will work on a couple of stack-related questions that are relevant to ACSL contests.
Create a queue with these operations:
PUSH("A"), PUSH("C"), PUSH("E"), X=POP(), PUSH("S"), X=POP(), X=POP()
This is a sequence of the queue operations. The growth is from left to right.
Operation 1: PUSH("A"). A is the first item to be added and is at the front of the queue.
PUSH("A") |
|
|---|---|
| Queue â | A |
| front of queue |
Operation 2: PUSH("C"). Now, C is at the end of the queue.
PUSH("C") |
||
|---|---|---|
| Queue â | A | C |
| front of queue = "A" | end of queue = "C" |
Operation 3: PUSH("E"). Now, E is at the end of the queue.
PUSH("E") |
|||
|---|---|---|---|
| Queue â | A | C | E |
| front of queue = "A" | end of queue = "E" |
Operation 4: X=POP(). We have our first POP operation, which removes A. Now, C is at the front of the queue.
E is removed. X takes the value of "E"
X=POP() |
|||
|---|---|---|---|
| Queue â | C | E | |
| front of queue = "C" | end of queue = "E" |
Operation 5: PUSH("S"). Now, S is at the end of the queue.
PUSH("S") |
|||
|---|---|---|---|
| Queue â | C | E | S |
| front of queue = "C" |
Operation 6: X=POP(). This POP operation removes C. Now, E is at the front of the queue.
C is removed. X takes the value of "C"
X=POP() |
|||
|---|---|---|---|
| Queue â | E | S | |
| front of queue = "E" | end of queue = "S" |
Operation 7: X=POP(). This POP operation removes E. Now, S is at the front of the queue.
E is removed. X takes the value of "E"
X=POP() |
|||
|---|---|---|---|
| Queue â | S | ||
| front of queue = "S" |
Conclusion
I will update this blog post with practice questions on stacks and queues. Please bookmark this page. Thank you for reading.
Related Posts
If you have any questions, please contact me at arulbOsutkNiqlzziyties@gNqmaizl.bkcom. You can also post questions in our Facebook group. Thank you.