-
Notifications
You must be signed in to change notification settings - Fork 1
/
blogPost.html
252 lines (204 loc) · 12.4 KB
/
blogPost.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
<!DOCTYPE html>
<html>
<head>
<title>Stacks and Queues: Marco Angelo</title>
<link rel="stylesheet"
type = "text/css"
href = './stylesheets/blog-post.css'>
</head>
<body>
<div class = "container">
<header>
<h1 class="header-name">A Very Pink Blog Post</h1>
</header>
<ul class="navbar">
<li><a href="index.html">Home</a></li>
<li><a href="#">About Me</a></li>
<li><a href="#">Contact</a></li>
<li><a href="#">FAQ</a></li>
<li id="all_articles"><a href="#">All Articles</a></li>
</ul>
<article class="post">
<h1 class="article-title">Abstract Data Types: Stacks and Queues</h1>
<hr>
<h2 class = "post__author-name">by <u><em>Marco Angelo</em></u></h2>
<img src="./img/stq.png"/ alt = "a list of nodes with arrows coming from the top and bottom">
<p><span class="dropcap">S</span>tacks and queues are two types of abstract data types that you can use to store and retrieve data in different ways.</p>
<p><strong>Stacks</strong> have a last-in-first-out mechanism (LIFO), while <strong>Queues</strong>
have a first-in-first-out mechanism (FIFO). But what does this mean?</p>
<h1 class="post__header">Stacks (LIFO)</h1>
<img class="post-img" src="./img/stacks.jpg" alt = "a stack of plates"/>
<p>
Stacks can be compared to piles of plates.
When you have a whole pile of plates, you can only add a new plate on top of the pile, aka the top of the stack.
The last plate you put on top is also the same plate that first gets out, hence the
<strong>LIFO (last-in-first-out)</strong> mechanism.
</p>
<p>
The 2 most important methods in a stack are <strong><em>push()</em></strong>
and <strong><em>pop()</em></strong>. <em>Push()</em> adds a new item to the top of the stack, and
<em>pop()</em> removes the item at the top of the stack.
</p>
<figure>
<img id = "push_pop" src = "./img/push_pop.jpg" alt="a diagram displaying the difference between push() and pop()"/>
<figcaption><em>
You <strong>pop from</strong> the stack, and <strong>push to</strong> the stack.
</em></figcaption>
</figure>
<p>
Just like a stack of plates, you can only <strong>add — <em>push()</em></strong> —
and <strong>remove — <em>pop()</em></strong> — from the top of the stack.
Aka, adding or removing from the “last” plate.
</p>
<h2 class="post__subheader">Stack Implementation</h2>
<p>
All stacks require only <strong>one pointer</strong> looking to the end of the stack. Whenever a <em>push()</em>
or <em>pop()</em> operation is performed, the pointer should always increment/decrement to the “top” of the stack.
A common data structure used to implement stack is an array.
</p>
<p>For <em>push()</em>, the stack pointer will always <strong>increment</strong> to the index of the new element being “pushed.”</p>
<p>For <em>pop()</em>, the stack pointer will always <strong>decrement</strong> to the index of the element before the element being “popped.”</p>
<figure>
<img class="post-img" src = "./img/push_stack_pointer.jpg" alt = "pushing onto a stack with the stack pointer"/>
<figcaption>
<em>
stack_pointer increments by 1 when “pushing” onto the stack
</em>
</figcaption>
</figure>
<figure>
<img class="post-img" src = "./img/pop_stack_pointer.jpg" alt = "popping onto a stack with the stack pointer"/>
<figcaption>
<em>
stack_pointer decrements by 1 when “popping” from the stack
</em>
</figcaption>
</figure>
<p>
Note that <em>pop()</em> doesn’t take any parameters, but <em>push()</em> does. This is because <em>pop()</em>
removes the last element no matter what, while <em>push()</em> adds an element,
which means you’ll need to specify an element to add.
</p>
<p>When dealing with stacks in code, there are some considerations to take:</p>
<ul>
<li><strong>underflow</strong>: an exception will be thrown if popping from an empty stack.</li>
<li><strong>overflow</strong>: account for resizing the stack implementation when pushing to a full array.</li>
</ul>
<p>
Think back again on the analogy of a stack as a pile of plates. The more plates you pile on top of each other,
the first plate to get removed will always be the last plate you put on. Hence, the plate that’s always on top
is the first to get removed.
</p>
<h1 class="post__header">Queues (FIFO)</h1>
<img src="./img/queues.jpg" alt = "people falling in line: a 'queue'"/>
<p>
Queues are pretty much what their name implies: think of queues as a line of people.
Imagine a line of people at the box office of a movie theater: whoever gets there first is the first to get their ticket,
and whoever falls behind purchases their ticket in the order they got there. Pretty simple, right?
</p>
<p>
The 2 most important functions in a queue are <strong><em>dequeue()</em></strong> and
<strong><em>enqueue()</em></strong>. The function <em>dequeue()</em> removes the first element of a queue,
<em>and enqueue()</em> “pushes” an element to the end of the queue. This makes sense in the context of a line of
people — whoever is first in line <em>dequeues</em> (gets removed), and whoever joins the line
<em>enqueues</em> (gets added to the back of the line).
</p>
<img src="./img/queue_dequeue.jpg" alt = "dequeue() from the front, enqueue() onto the back"/>
<p>
The first element you <em>enqueue()</em> is the first element to be removed, hence the <strong>FIFO (first-in-first-out)</strong> mechanism.
</p>
<p>
<strong>Disclaimer</strong>: <em>dequeue()</em> can sometimes be referred to as <em>pop()</em>,
but for the sake of consistency and to avoid confusion with the <em>pop()</em> function for stacks,
I will refer to it as <em>dequeue()</em>.
</p>
<h2 class="post__subheader">Queue Implementation</h2>
<p>
A common implementation of a queue is with Doubly Linked Lists,
so we will use that data structure to analyze the handling of pointers.
Each element of the queue will be referred to as a <strong>Node</strong>.
</p>
<p>
Just like stacks, queues in a Doubly Linked List contain a pointer referring to the last item.
The only difference is that queues require 2 pointers looking to the beginning and end of the queue
to take advantage of the <em>dequeue()</em> and <em>enqueue()</em> functions.
</p>
<img src="./img/pointers.jpg">
<p>Once you <strong><em>enqueue()</em></strong> a node to the queue, the back_pointer increments by 1.</p>
<img src="./img/enqueue.jpg"/>
<p>
However, <em>dequeue()</em> is a lot trickier than <em>enqueue()</em>. This is because once you remove from the front of the queue,
you’d have to deallocate the memory from the previous node and make the pointers account for the new size of the queue.
</p>
<p>
So once you <strong><em>dequeue()</em></strong> an element from the front of the queue, the front_pointer moves to point to the
next node while retaining the same location in the Linked List, and you deallocate the space for the first node.
In effect, the back_pointer decrements by 1 to account for the new size.
</p>
<figure>
<img src="./img/dequeue.jpg"/>
<figcaption>
<em>
back_pointer decrements by 1 to account for the new size (n-1 = 7), front_pointer stays in the same
position but points to the next element after the front is removed
</em>
</figcaption>
</figure>
<p>
It is easy to think of a queue as a line of people. To <em>enqueue()</em> means that more people are falling
into the back of the line, and <em>dequeue()</em> means that the person who got there first, no matter who they are,
will be let through first. No matter how large the queue is, the person who arrives first will always be the
first to leave. Queues can also be thought of as a “first come, first serve” type of data structure, where
deletion and insertion happen on different ends.
</p>
<h1 class="post__header">Conclusions</h1>
<h2 class="post__subheader">Stacks</h2>
<ul>
<li>Stacks have a LIFO(last-in-first-out) structure, where deletion and insertion happen at the same end.</li>
<li>Stacks have 1 pointer looking to the end (“top”) of the stack.</li>
<li>Stacks use <em>pop()</em> and <em>push()</em> functions — removing and adding elements to the top of the stack.</li>
</ul>
<h2 class="post__subheader">Queues</h2>
<ul class="post-ul">
<li>Queues have a FIFO (first-in-first-out) structure, where deletion and insertion happen at opposite ends.</li>
<li>Queues have 2 pointers looking to the front and back of the queue.</li>
<li>Queues use <em>enqueue()</em> and <em>dequeue()</em> functions — adding to the end of the queue and removing from the front of the queue.</li>
</ul>
<p>This article was taken from my
<a href="https://medium.com/@angeloacebedo/data-structures-stacks-and-queues-7cc8790b9ce8">
Medium blog.
</a>
</p>
<div class="social-sharing">
<h2>Share this article!</h2>
<div class="social-sharing__icons">
<img class = "icon" src="./img/sharing/png/021-facebook.png">
<img class = "icon" src="./img/sharing/png/025-instagram.png">
<img class = "icon" src="./img/sharing/png/035-whatsapp.png">
<img class = "icon" src="./img/sharing/png/043-twitter.png">
</div>
<p class = "social-sharing__copyright" class="italic">
Icons made by
<a href="https://www.flaticon.com/authors/freepik" title="Freepik">
Freepik</a>
from
<a href="https://www.flaticon.com/" title="Flaticon">
www.flaticon.com</a>
</p>
</div>
</article>
<div class="author-photo">
<img src="./img/IMG_0840.jpg" alt="a man in a red formal shirt">
</div>
<div class="author-info">
<h3 class="author-name">Marco Angelo</h3>
<h4 class="author-title" class="italic">Aspiring Front-End Web Developer</h4>
<h4 class="author-education">Bachelor of Arts in Computer Science at New College of Florida</h4>
<p class="author-bio">When Marco is not brushing up on his code, you can usually find him playing the piano, reading, hanging out with friends,
or writing. Follow him on <a href="https://www.medium.com/@angeloacebedo">Medium</a> and catch up on his photography adventures
on <a href="https://www.instagram.com/lilazn97">Instagram</a>.
</div>
</div>
<footer>Copyright Marco Angelo Acebedo</footer>
</body>
</html>