Data Structures in Python

 Data Structures in Python

What is a Stack?

A Stack is an abstract linear data type that serves as a collection of objects. Unlike queues, they use the Last In First Out or LIFO  technique to insert and delete elements. The insert and delete operations are referred to as push and pop in stack. Stack stores the data elements in a similar fashion as a bunch of plates that are kept one above the other in a kitchen. It allows operations (push or pop) only from one end, often called as top. You can add or remove elements only from the top of the stack.

The basic operations which are performed in the stack are mentioned below:

Push: Adds an item in the stack. Once the stack is full, it is said to be in an Overflow condition.

Pop: Removes an item from the stack. It follows a reversed order to pop items similar to the way when items are pushed. It is said to be an Underflow condition.

Peek or Top: Returns top element of stack.

isEmpty: Returns true if stack is empty, else false.

Applications of Stack

Stacks are considered as the backbone of Data Structures. Most of the algorithms and applications are implemented using stacks.

Some of the key applications of stacks are—

• They are used to reverse a string. Each of the characters are pushed in and then popped off, which results in a reversed string.
• It is used in Expression Evaluation and Expression Conversion (infix to postfix, infix to prefix, postfix to infix, prefix to infix).
• It is used for forward and backward features in web browsers.
• It is used for recursive parsing in Natural Language Processing.
• It is used in syntax parsing and parenthesis checking.
• It is used for Backtracking like finding paths to a maze or exhaustive searching.
• It is used in Algorithms like Tower of Hanoi, tree traversals, histogram problem and also in graph algorithms like Topological Sorting.

Balanced Symbols program:

Python Program to Reverse the Content of a File using Stack

Approach:

1. Create an empty stack.
2. One by one push every line of the file to the stack.
3. One by one pop each line from the stack and put them back to the file.

Python program to reverse a stack

Algorithm: 

1. Define some basic function of the stack like push(), pop(), show(), empty(), for basic operation like respectively append an item in stack, remove an item in stack, display the stack, check the given stack is empty or not.
2. Define two recursive functions BottomInsertion() and Reverse()..
3. BottomInsertion() : this method append element at the bottom of the stack and  BottomInsertion accept two values as an argument first is stack and the second is elements, this is a recursive method.
4. Reverse() : the method is reverse elements of the stack, this method accept stack as an argument Reverse() is also a Recursive() function. Reverse() is invoked BottomInsertion() method for completing the reverse operation on the stack.

Output:

Orginal Stack

5

4

3

2

1

Stack after Reversing

1

2

3

4

5

Reverse a string using stack

Following is simple algorithm to reverse a string using stack.

1) Create an empty stack.

2) One by one push all characters of string to stack.

3) One by one pop all characters from stack and put them back to string.