Stacks First In Last Out Push Pop Queues First In First Out
<aside> đź’ˇ
Stacks are a data structure that follow a “first in last out” order when it comes to adding and removing elements. This data structure is synonymous with the stack you’ve probably heard from in ECS 50, which is accessed from in main memory and where the return addresses of functions are added and removed.
</aside>
<aside> 💡 Pushing to the stack involves adding elements to the stack in. Following the “first in last out” principle, when pushing multiple entities on the stack. The very first item that is pushed will be at the bottom of the stack.
For example, when calling
push(13) push(21) push(12)
The number 13 is at the bottom of the stack.
</aside>
<aside>
💡 Popping involves ****removing an element from the stack. Following the “first in last out” order, in the following example, when calling pop() the first time, 13 will be removed from the stack. If we call pop() 2 more times, 21 will be removed, then 12 will be the last number to be removed from the stack.
</aside>
<aside>
đź’ˇ push() and pop() can be performed on linked lists! push() is just simply appending to the end of the linked list and pop() is just removing after the last element of the list.
</aside>
| Operation | Singly Linked List | Doubly Linked List |
|---|---|---|
push() |
$O(n)$ | $O(1)$ |
pop() |
$O(n)$ | $O(1)$ |
<aside> 💡 Queues are another data structure that follow a “first in first out” order (FIFO) when it comes to adding and removing elements. The first element added is the first to be removed from the queue. We see queues implemented in everyday life such as a song playlist. The first song on a playlist is the first to be played. The first person in line at a sandwich shop is the first to get their sandwich and leave.
</aside>
<aside>
💡 Queues also contain push() and pop() operations similar to stacks. push() pushes elements to the queue in the “first in first out” order.
For example, when calling
push(13) push(21) push(12)
The number 13 is at the top of the queue.
</aside>
<aside>
đź’ˇ pop() removes elements from the queue following the FIFO order as well. So when calling pop() on the queue above, 13 is the first number to be removed from the queue. If we called pop() 2 more times, 21 will be removed, then 12.
</aside>
<aside>
đź’ˇ push() and pop() for queues can be performed on linked lists! push() is just simply prepending to the beginning of the linked list and pop() is just removing from the beginning of the list.
</aside>
| Operation | Singly Linked List | Doubly Linked List |
|---|---|---|
push() |
$O(n)$ | $O(1)$ |
pop() |
$O(n)$ | $O(1)$ |