Solving a Problem using Queues ( BFS algorithm) : The basic operations of the queue like enqueue ,dequeue, peek and isEmpty will take O(1) time complexity but operations like contain (search) and remove an element from the middle will take O(n) time complexity since it’s required to dequeue all the element and enqueue then again. manage shared resources between some entities like CPU processes.Īs the stack the queue can be implemented using the arrays or the linked lists data structures, in our implementation we will use linked lists.request in web sites to know which client should be served.Queues can be used to model many real world problems like : In order to solve it using stack what we could do is to add each parenthesis to the stack one by one and each time check if the stack is not empty if the first element in the stack is the right one in example if we are adding the ‘(‘ and the the first element in the stack is ‘)’ then we simply delete the first element from the stack but if not we add the element that we wanted to add and at the end of all the string that we are looping over it’s characters (parenthesis) we check if stack is empty then we return true else we return false that’s indicates that there is a syntax error.Ī Queue is a linear data structure that models a real world queue with tow main operations dequeue and enqueue, the queue is similar to the stack but it has tow entry's for the operations one entry for enqueuing elements (from the end) and the other will be for dequeuing elements (from the front) so that the queue will follow the principal of FIFO (First In First Out) in a way that the first added element is the first accessed. Input : a string containing the parenthesis → Output : true or false. In this part we will take a problem and try to solve it using the stack and as an example we are taking the famous balanced brackets problem where you need to check if the syntax and the closing of the parenthesis is correct or not in a group of parenthesis ex : Solving a problem using stacks ( balanced brackets problem) : The following operations push, pop, peek,isFull,isEmpty all has a O(1) time complexity cause they all depends on a simple instructions but if we want to do something like search an element that will take O(n) time complexity since we have to pull every element and put it back in order to loop over all the elements. This data structure is already implemented in most of the languages and the implementation sometimes is different from one language to another one, but for the sake of understanding the mechanism of it, we will implement it with it’s operation. Mainly there is two ways to implement a stack either you use arrays or linked lists and in our example we will use linked lists. used in so many algorithms because it can model a lot of real world problems.used in DFS (Depth First Search) algorithm in graphs. used in compilers in things like storing the recursive calls and in syntax checking.the undo mechanism in the text editors.Stacks are used to solve many problems since it mimics the behaviour of many real world problems so it’s used as a model of those problems things like : A stack is a linear data structure that respects the principal of LIFO “Last In First Out” it means that the last element that was entered into the stack will be the first element to get out or the principal of FIFO “Fist In First Out”which means first in first out so the first element entered to the stack will be the first element that gets out, it’s used to model real world problems and it has tow main operations pop() which is used to get the first top element in the stack and push() which is used to add an element at the top of the stack along side with other operation like peek and ifEmpty that will discuss later.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |