Mohamed Khaled Yousef

Posted on Jun 29, 2018

Stack - Data structure

#datastructures #algorithms #stack #linkedlists

A stack is a data structure that occasionally known as LIFO (Last In First Out), meaning that the last element added to the stack must be the first element removed from it.

The simplest way to understand stack, Box of books. We add the first one on bottom then the next on top and so on. If we want to choose any one, we should remove all books above it. for example if we want to get the last book in the box, we will remove all books on top of this book.

By stack we can:

Push(Key) : adds key to collection
Key Top() : returns the most recently added key
Key Pop() : removes and returns most recently added key
Boolean Empty() : are there any elements?????

Here stack implementation

We can also create stack using STL :

Last thing to say, One of the application of a stack is Balanced Brackets,

Here the problem

Input : A string str consisting of ‘(‘ , ‘)’ , ‘[‘ , ‘]’ characters
Output: returns whether or not the string’s parentheses and square brackets balanced
For examples:
Balanced like this:
“ ([]) “
“ ((([([])]))()) “
Unbalanced like this:
“ ([]]() “
“ ][ “

Algorithm

IsBalanced(str )
 Stack stack //create stack
 for char in str: //for every character in string
    if char in [‘(‘, ‘[‘]:
        stack.Push(char ) 
    else:
        if stack.Empty(): //means false ,not matches
            return False
        top <- stack.Pop()
        if (top = ‘[‘ and char != ‘]’) or (top = ‘(‘ and char != ‘)’):
            return False //dont match
 return stack.Empty()

Here the code :

You must know that:

1. Stacks are used for compilers and a lot of algorithms
2. We can also implement stack with linked list

One disadvantage is one limitation of the array is that we have maximum size base on the array that we initially allocated
The other potential problem is that we have potentially wasted space, So if we allocated a very large array to allow possibly large stack and we did not actually use much of it …. all the rest of it is wasted
We can keep pushing and the nice thing about this is there is no priority limit as to the number of elements you can add
As long as you have available memory ,you can keep adding
There is an overhead though like in the array ,we have each element size is just enough to store our key
There we have got the overhead of storing a pointer as well and on the other hand there is no wasted space in terms of allocated space that is not actually being used
You can see how to implement stack using linked list here

3. Stacks are known as LIFO (Last In First Out) or GIGO (Garbage In Garbage Out)

Last thing to say, Thanks for reading and I hope it would help and don’t hesitate to tell me your feedback and suggestions :))

All source codes in c++ in this repo

Top comments (1)

Patrick Lafferty • Jul 1 '18

Some suggestions (I'm not sure how indepth you want this ie if it should be treated as a complete implementation or just a sample):

Use templates so your stack can be used for more than just ints
Dynamically allocate memory, don't use a static array. Instead of doing it yourself, use std::vector as the array (now you can remove isFull)
Combining 1) and 2), take the collection type as a type parameter so you could use the same stack class for array based or linked list implementations (ie, what std::stack does), so there's no need to write two implementations
If the only reason you branch on a condition is to return a boolean, just return the condition (ie return top == -1, return top >= MAX - 1)
If you're writing your own collection in C++, implement iterators so you can use it with std::find, range-based for loops and other friends (see stackoverflow.com/questions/816456...)
Either expose isEmpty and don't call it in pop (require the user to check before popping - how C++ does it), or don't expose isEmpty and call it yourself in pop (and assert/throw an exception if it is, instead of returning a sentintel value)
Separate pop into top and pop, where top returns a reference to the top thing and pop does the popping (see cpptruths.blogspot.com/2005/10/why...)
Prefer to use std::vector::empty() rather than checking size() == 0 yourself
Combining 4 and 8, the end of isBalanced can be simplified to return openingBracketsStack.empty();

DEV Community