Top Coding Algorithms — Stack

Stack is like a list but with limited operations on it, basically the essence is last come first out. There are 2 fundamental operations on stack, push and pop. Consider we have a stack as following:

Image for post
Image for post

With 2 elements, now PUSH operation stacks on element on top of the existing stack:

Image for post
Image for post

POP operation removes the element on top of the stack and bring it back to the original stack:

Image for post
Image for post

Implement a Stack

Following a question on leetCode, let’s implement a customised stack in python.

Design a stack which supports the following operations.Implement the CustomStack class:- CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.- void push(int x) Adds x to the top of the stack if the stack hasn't reached the maxSize.- int pop() Pops and returns the top of stack or -1 if the stack is empty.- void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Here it requires to implement a stack with fixed size that if one tries to insert more elements to a stack that already reaches it max size would cause stack overflow, while popping element from an empty stack would cause underflow.

Implementation should be straight forward, now let’s consider solving a problem using the property of stack.

Matched Parentheses

Consider the following example that could be solved with stack.

Given an expression string exp , write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp.

Input: exp = “[()]{}{[()()]()}”
Output: Balanced

The key here is to pop out the element whenever there is a matched pair.

Check code here.

Written by

Hmm…I am a data scientist looking to catch up the tide…

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store