Stack - Data Structures & Algorithms Tutorial In Python #7
Вставка
- Опубліковано 19 лип 2024
- What is stack?: Stack is a very important data structure in any programming language. In this data structure tutorial, we will discuss what is stack and implement stack in python using a list and collections.deque. In the end there are couple of exercises for you to solve.
Code: github.com/codebasics/data-st...
Exercise: github.com/codebasics/data-st...
Topics
00:00 Introduction
00:14 What is stack?
04:51 Stack in different languages
05:06 Using list as a stack
07:50 Using deque as a stack
11:50 Exercise
#stack #stackdatasstructure #datastructures #algorithms #python
Do you want to learn technology from me? Check codebasics.io/?... for my affordable video courses.
Next Video: • Queue - Data Structure...
Previous video: • Collision Handling In ...
Complete playlist: • Data Structures And Al...
🌎 My Website For Video Courses: codebasics.io/?...
Need help building software or data analytics and AI solutions? My company www.atliq.com/ can help. Click on the Contact button on that website.
#️⃣ Social Media #️⃣
🔗 Discord: / discord
📸 Dhaval's Personal Instagram: / dhavalsays
📸 Instagram: / codebasicshub
🔊 Facebook: / codebasicshub
📝 Linkedin (Personal): / dhavalsays
📝 Linkedin (Codebasics): / codebasics
📱 Twitter: / codebasicshub
🔗 Patreon: www.patreon.com/codebasics?fa...
Do you want to learn python from me with a lot of interactive quizzes, and exercises? Here is my project-based python learning course: codebasics.io/courses/python-for-beginner-and-intermediate-learners
This series gotta be super hit in future
I'm watching it from the future and I can tell you is a super hit for me!
@@daniel280187 no I'm watching from future and it is no where near super hit considering the Indian origin. Like if even 0.5 percent indian started watching this, the views will be in millions. If ur not indian then u might have trouble understanding that 70-80 percent graduates are engineers and learning some coding language and even on those python is on top. So yeah it should have atleast 1 million views man.
@@rheumaticharm9551 I think I'm from future and these tutorials are masterclass hit now !!
@@rheumaticharm9551 okay but what about now?
No. I'm frm the future🚶
Absolutely hilarious bit at the end. I couldn't stop laughing! 😂 :
"If you look at the solution without first solving the problem, it's going to download the covid-19 virus to your computer".
@@IITVital kya bol raha hai bhai? IIT ka naam badnaam karega kya
This is literally the best explanation of a stack I have ever seen. I'm someone who dreads data structures and algorithms but after watching this video, I'm actually excited to watch the rest of your DS tutorials. Thank you!
You make some of the easiest to understand explanations for coding stuff that I have come across on the internet. Thank you so much!
The way, you explain things, I love it. Most loving part is the exercises.
So glad!
Your videos are amazing, you make learning Python much easier! Thankyou :)
Second exercise item in this tutorial is a brilliant use of push & pops in stack....!
Got the logic for similar set of questions in leetcode. Thank You.
Simplified way of explanation, I've been trying to find some resources for python dsa and this is the best. !!
Thank you. This playlist have been very helpful. Keep up the great work!
Thank you. You have a great way of explaining concepts . Codebasics for dummies :)
"Watch other data structures videos"
I will for sure.
At first I had curiosity. But now, this channel have my attention.
Django unchained, nice
lol nice
Data Structures became very interesting with your videos Thank You, sir!!
Glad you like them!
Read stacks & queues in 12th class,... but always wondered what its for... browser example really makes sense
thank you dear Sir! Your videos are easy to follow and they are very informative. Take care during outbreak
Glad you like them!
Thank you very much, for sharing knowledge for free!
Awesome content! It's great that you're able to squeeze in so much valuable information into a 13 minute video.
Also, sorry if I sound pedantic here... but I believe the correct pronunciation of deque is "deck" (written in the documentation at 7:59).
Thank you for the valuable content :D
Narin thanks for informing about pronunciation. My english is not the best and I take your feedback positively. Thanks for teaching me that and I will use "deck" going forward :)
sir please make full tutorial on data structures along with algorithm using python with every detail please we newbie programmer need this . and a thanku to you sir for this video
Thanks a lot, It helped me to understand the concept in python. Keep making such good contents. Here is the code of the exercise questions.
solution 1:
from collections import deque
class stack:
def __init__(self):
self.container=deque()
def push(self,val):
self.container.append(val)
def pop(self):
return self.container.pop()
def peek(self):
return self.container[-1]
def is_empty(self):
return len(self.container)==0
def size(self):
return len(self.container)
def reversestring(s):
st=stack()
for i in s:
st.push(i)
revstr=""
while(st.size()!=0):
revstr+=st.pop()
return revstr
print("this function is for reversing a string using stack")
print(reversestring("hello my name is rajnish"))
solution 2:
from collections import deque
class stack:
def __init__(self):
self.container=deque()
def push(self,val):
self.container.append(val)
def pop(self):
return self.container.pop()
def peek(self):
return self.container[-1]
def is_empty(self):
return len(self.container)==0
def size(self):
return len(self.container)
def isbalanced(s):
st=stack()
flag=0
ch=0
for i in s:
if i=="(" or i=="{" or i=="[":
ch+=1
st.push(i)
if (i==")" and ch==0) or (i=="}" and ch==0) or (i=="]" and ch==0):
flag=1
break
if i==")" or i=="}" or i=="]":
x=st.pop()
ch-=1
if x=="(" and i!=")":
flag=1
break
if x=="{" and i!="}":
flag=1
break
if x=="[" and i!="]":
flag=1
break
if flag==1:
return "False"
else:
return "True"
print(isbalanced("({a+b})"))
print(isbalanced("))((a+b}{"))
print(isbalanced("((a+b))"))
print(isbalanced("))"))
print(isbalanced("[a+b]*(x+2y)*{gg+kk}"))
For interview and for oral, this is helpful. Thanks for the videos/
It really helps me, Thank you so much!
simple and precise
Thank you!
Also, if you inherited deque you wouldn't have to redefine some methods, such as pop, you could just reference the base class method. (I get that this tutorial wasn't about OOP)
Thank you. This video help me to understand the subjet.
Covid virus cringe apart, this is a clean and concise video. Thanks!
I am happy this was helpful to you.
so detailed, i like the exercises
There's so much in my head i need to remember and idk what any of it is for sometimes.
Covid 19 virus 😂, i felt like classroom immediately
covid-19 on the PC good one :)
ThankYou
god lvl teaching,,pls expand the series more
great content ! how is memory management for deque? is it better than list
Thanks for this Video it's awesome!
Please can you tell me how to puch another value for every node in stack without to adjust the Class Node..?
The last one was hilarious..!! 🤣
thankyou very much sir :)
Well-explained
can we do 2nd ques with the help of regular expressions? if yes then please tell me
Hi Dhaval, I tried implemening the STACK using Linked list cause I was curious how the dequeue was working behind the scene so here is my solution for the 1st Exercise. Do have a look and if you have any suggestions then let me know..
# Stack using Linked List
class Node:
def __init__(self, prev = None, data = None, next = None) -> None:
self.prev = prev
self.data = data
self.next = next
class Stack:
def __init__(self) -> None:
self.head = None
self.top = None
def push(self, data):
if self.head == None:
node = Node(None, data, None)
self.head = node
return
itr = self.head
while itr.next:
itr = itr.next
node = Node(itr, data, None)
itr.next = node
self.top = node
def pop(self):
# print(self.top.data)
if self.head == None:
return print("Stack is Empty")
data = ''
if self.top.prev is not None:
data = self.top.data
self.top.prev.next = None
self.top = self.top.prev
else:
data = self.top.data
self.head = None
self.top = None
return data
def peek(self):
if self.head == None:
return print("Stack is Empty")
return self.top.data
def print(self):
if self.head == None:
return print("Stack is Empty")
itr = self.head
llstr = ''
while itr:
llstr += f"{ itr.data } => "
itr = itr.next
print(llstr)
def size(self):
count = 0
itr = self.head
while itr:
count += 1
itr = itr.next
return count
def reverse_string(string):
s = Stack()
for c in string:
s.push(c)
rstring = ''
while s.size():
rstring += s.pop()
print(rstring)
s.print()
reverse_string("We will conquere COVID-19")
very helpful
Man I have been scratching my heads how to do the second Excersise for 1 day then I had finally to open solution 2 and now m like wait I could have done that.... But seriously damn nice way of implementing hash table to stack earlier I was first trying to see if I can do this with list and ord (of those brackets) to compare them and came up with complicated program but at the end it doesn't work on all test cases I found this to be much better but the last part of the code is really difficult to understand
can we search for max or min value in stack and make it O(1)?
thank you so much
***solution spoiler***: the use of dictionary in problem 2 was so smart!
For the example of webbrowser back and forward button, why can't we use doubly linkedlist ?
in interviews we can use deque? Might be dumb question but im just now learning DS ALGO?
just a random vdo i clicked nd this is what i got the diamond ,while i was looking for gold.....!!! you're the best sir.
I am happy this was helpful to you.
Why is it that id(list) doesn't change even after append as list is basically a dynamic array?
I am not getting that if we are not giving the length of the List so how it can be get filled??
Thank you for another extremely useful video!
I would like to present my approach on the second exercise. Please reach out and provide feedback for this implementation:
from collections import deque
class Stack:
def __init__(self):
self.container = deque()
def push(self, val):
self.container.append(val)
def pop(self):
return self.container.pop()
def peek(self):
return self.container[-1]
def is_empty(self):
return len(self.container)==0
def size(self):
return len(self.container)
def reverse_string(a_string):
s = Stack()
for x in a_string:
s.push(x)
new_string = ''
for y in range(s.size()):
new_string += s.pop()
return new_string
def is_balanced(a_string):
s = Stack()
d = Stack()
check = Stack()
for char in a_string:
if char in "{}[]()":
s.push(char)
for char in range(len(s.container)-1, -1, -1):
d.push(s.container[char])
#print(s.container)
#print(d.container)
if len(s.container) != 0 and len(s.container) % 2 == 0:
mean = int(len(s.container)/2)
for i in range(mean):
check.push(s.container[i]+d.container[i])
for set in check.container:
if set not in ["[]","()","{}"]:
c = False
else:
c = True
return c
print(is_balanced("({a+b})"))
print(is_balanced("))((a+b}{"))
print(is_balanced("((a+b))"))
print(is_balanced("))"))
print(is_balanced("[a+b]*(x+2y)*{gg+kk}"))
Thanks for the answers veryvery helpfull
hye , can we implement stack in python without using in-build function like append and pop ??
some one told me coding people don't have humour and boring , then i showed them ur channel
Hey great content. Very very helpful.♥️
sir please create a playlist about python algorithm
i tried the exercise and run your solution.
On the last example if I run this print(is_balanced("[a+b]*(x+2y)*{gg+kk}"))
the answer is true.
But on the debug mode the answer is false.
not sure why though.
Hey in the last exercise why did we returned stack.size()==0 can you explain
Hello Sir, can you please create a video developing of project using only DSA ?
Diagram for Stack Implementation quick correction
4:52 - Python Code Sample
stk = deque()
stk.append(5)
stk.append(89) # correction 89 not 9
stk.pop() # returns 89
wow, thanks Glory for your keen observation.
How would you manage this history in terms of data structure if you are browser developer?
Not stack but Doubly Linked List. :-P. JFF. I would try stack too.
Wow. Just Amazing Content. Learning.so much through you 🙂
Happy to hear that!
i am so much grateful to you thank you very much for such clear and neat explanation
😊👍
Can anyone explain to me how the memory storage/allocation of stacks work? Do they face similar issues with dynamic arrays (copying and paste each individual data one at a time to the new memory location)? Any help will be much appreciated! Thanks!
stack is built using different data structures, In python as told in the video, if we use deque to implement it then it works as a doubly linked list so python memory allocation is similar to that of a linked list. watch again from 6:40
Nice tutorial and it helped me a lot. Waiting for the next set of Data structure tutorials.
Glad to hear that
If one is not able to solve the second exercise on his/her own this means his/her logical skills are weak? I heard a youtuber saying that if you know the basic operations of stacks then you should be able to do it.
"Download COVID-19 virus". That was really funny 😂. But tutorial was awesome. 🤩🤩
Should this be episode #6?
You are right. Updated the title. Thank you 😊
But how we can overcome the challenge of memory using deque rather than list ?
example of website is very useful
👍😊
in python: when you add new elements to a list its id address will not change! and I know that python list has no max size. so, if that true, is that mean it's no problem using it as a stack?
no watch the portion of this video ua-cam.com/video/p_9t8uhXQdk/v-deo.html
best
Instructions weren't clear, now i'm in quarantine
4:58 in python code sample typo correction stk.append(89) instead of stk.append(9)
Create a video on how to crack the coding interview
Sure
I'm watching on my phone and now I'll have to wait till tomorrow to click that link when I'm get my PC 😅 you never know right
ayooo
the repercussions for clicking the solution without doing the exercises has me weak🤣🤣🤣
he litterally said your laptop's going to get corona virus🤣🤣 if you don't do the work first😂
can someone please explain this part of code from the solution:
if ch==')' or ch=='}' or ch == ']':
if stack.size()==0:
return False
if not is_match(ch,stack.pop()):
return False
return stack.size()==0
Basically, you want to see that if u encounter either of the three brackets the top bracket on the stack should be its opening counterpart. I those two are the same then no False is set. In the end if no false is set and if last bracket is also processed ten return true.
class Check:
def __init__(self):
self.check = deque()
def push(self,val):
self.check.append(val)
def is_paranthesis(self):
para = ['{','}','(',')','[',']']
for i in para:
return self.check[-1].count(i)==1
seriously what the heck! i was looking to download covid19 virus but instead downloaded a big fat python.😜
why you use self.container? I am learning, I will think just self is enough, I don't know the reason self.container, thanks for help!
I think its better my friend if you make the container self._container instead of self.container , private property
Pandemic is over. So is it ok to click the solution link before I solve? hahahah Thanks for these videos!!
Pandemic is over but COVID infections are still going on 😧 So be careful when click on the solution link 😆🤣
Why is implementing Stack using a deque a better option than implementing stack using a linked list?
Its that we don't have to copy the already present elements in order to insert a new element....since linked list dynamic
12:10
didn't know about the digital variant of this virus
ha ha.. yes it exist :)
hi sir,How to print elements of stack
See def show in the below code. It shows all the elements in the stack :)
class Stack():
def __init__(self):
self.container = deque()
def push(self,val):
self.container.append(val)
def pop(self):
return self.container.pop()
def peek(self):
return self.container[-1]
def is_empty(self):
return len(self.container)==0
def size(self):
return len(self.container)
def show(self):
return self.container
i implemented same concept in leetcode problem. it's working but it failed for 9 testcases like '((' , '(['. then i modified it.
In Exercise problem:
class Solution:
def mapper(self, c1, c2):
operation = {
'}': '{',
')': '(',
']': '['
}
return operation[c1] == c2
def isValid(self, s: str) -> bool:
stack = Stack()
if len(s) == 1:
return False
for char in s:
if char == '(' or char == '{' or char == '[':
stack.push(char)
if char == ')' or char == '}' or char == ']':
if stack.is_empty():
return False
if not self.mapper(char, stack.pop()):
return False
if stack.size() != 0:
return False
return True
Hey man my laptop got virus I think this happend due to checking the solution before doing it 😂😂😜. Anyway Thankyou buddy.
Welcome 👍😄
@codebasics Sir The creation of class stack is not helping in VScode please help
Input:
from collections import deque
class Stack:
def __init__(self):
self.container = deque()
def push(self, val):
self.container.append(val)
def pop(self):
return self.container.pop()
def peek(self):
return self.container[-1]
def is_empty(self):
return len(self.container) == 0
def size(self):
return len(self.container)
s = Stack()
s.push("45")
s.push("34")
s.peek()
s.size()
s.pop()
s.peek()
Output:
No output is coming its empty
Please Help anyone
u've to print the operations like follows:
print(s.peek()) and so on !
@@tejassarnaik3108 shit that's some serious stupidity on my part... Thanks sir
Here is a different solution for second exercise
from collections import deque
def parenthesis_matching(equation):
stack=deque()
arr=deque()
for ch in equation:
stack.append(ch)
for ch in stack:
if ch=="(":
arr.append("(")
elif ch=="[":
arr.append("[")
elif ch=="{":
arr.append("{")
elif ch==")":
try:
arr.remove("(")
except:
return False
elif ch=="]":
try:
arr.remove("[")
except:
return False
elif ch=="}":
try:
arr.remove("{")
except:
return False
if len(arr)==0:
return True
else:
return False
if __name__=="__main__":
s=input("Enter the equation")
print(parenthesis_matching(s))
Put continue at the end of every condition too.
It really download COVID 19... All of the sudden, I'm sick, and so is my computer
what is the difference between append and push?
They are the same thing ashwin . In arrays or linked list when we add element we are appending elements while in stack we say we are pushing elements .
append, push, put are all the same..just based on different data structures.
12:10 😂
I did code in a different way. please anyone review my code
def reverse_string(self,string):
for i in range(len(string)):
self.push(string[i])
rev_string = ''
for i in range(len(string)):
rev_string += self.pop()
return rev_string
sir please give some easy exercise,the second exercise kills my whole day but i can't find the answer,so i open the sollution,after the open solution i can't understand,most of the comment below in this tutorial is they cant do second exercise sir
Sure. To be honest the exercise is not that hard. But sure I will look into it in future and also add more comments to solution so that you understand
@@codebasics after open sollution then only realize the problem is not hard,then only realize I have to change the way of thinking ,thank you sir for your reply, I'm big fan of you sir,you r a best teacher ,take care of ur health sir
thanks for the support you are adding to the community 🙏
In my computer have covid virus
I got corona on my pc what do i do now!?!?!?!??! Help!
ha ha. you need to send your pc for quarantine. dont use it for next 14 days :)
Someone said when you were making this video you are the person who was closest to god
The answer is
from collections import deque
class Stack:
def __init__(self):
self.container = deque()
def push(self, val):
self.container.append(val)
def pop(self):
return self.container.pop()
def peek(self):
return self.container[-1]
def is_empty(self):
return len(self.container) == 0
def size(self):
return len(self.container)
def reverse_string(s):
stack = Stack()
for ch in s:
stack.push(ch)
rstr = ''
while stack.size()!=0:
rstr += stack.pop()
return rstr
if __name__ == '__main__':
print(reverse_string("We will conquere COVI-19"))
print(reverse_string("I am the king"))
Solution 1
class stack:
def __init__(self):
self.stack=deque()
self.ans=""
def insert(self,ele):
self.stack.append(ele)
def remove(self):
self.stack.pop()
def reverse_string(self):
ele=self.stack.pop()
self.ans+=ele
if len(self.stack)!=0:
return self.reverse_string()
else:
return self.ans
from collections import deque
s1=stack()
s1.insert("0")
s1.insert("1")
s1.insert("2")
s1.insert("3")
s1.insert("4")
print(s1.reverse_string())
Sir I am so sorry, I clicked the solution link by mistake, I don't want covid.- 19... please someone help meee!!
Ha ha.. no one can help you now other than your own immunity :)
@@codebasics sir but speaking seriously I felt that you could have taught stack in much more detail (comparing to the linked list video (perfect video btw)). For example implementation of peek function with an index etc.
Also I have one doubt: at 1:40 you said that if we use linked list as a stack we will need to traverse it again and again, but can't we use the linked list from the left side? Like append and delete the elements at the head of the linked list?
class Check:
def __init__(self):
self.check = deque()
def push(self,val):
self.check.append(val)
def is_paranthesis(self):
para = ['{','}','(',')','[',']']
for i in para:
return self.check[-1].count(i)==1
CodeWithHarry