What Will I Learn?
- Create a stack in python language.
- Add items to the stack.
- Extract items to the stack.
Requirements
- PC (Laptop or Desktop)
- Python 3.6
Difficulty
- Intermediate
Tutorial Contents
- Abstract Data Type
An abstract data type (ADT), specifies a set of operations (or methods) and the semantics of operations (what they do), but does not specify the implementation of the operations. This is what makes it abstract. Why is this helpful? It simplifies the task of specifying an algorithm if you can denote the operations you need without having to think at the same time how the operations are performed. Since there are usually many ways to implement a ADT, it may be useful to write an algorithm that can be used with any of the possible implementations. Well-known ADT, such as the ADT Stack, are already implemented in standard libraries for python, so they can be written once and used by many programmers. ADT operations provide a common high-level language for specifying and talking about algorithms.
- Stack
A common ADT is a stack. A stack is a collection or data structure that contained multiple elements. A ADT is defined by the set of operations that can be performed on it, which is called the interface. The interface to a stack consists of these operations:
init: Initializes a new empty stack.
push: Adds a new item in the stack.
pop: Removes an item from the stack and returns it, The item that is returned is always the last one added.
isEmpty: Checks if the stack is empty. One is sometimes called a "last in, first out" or LIFO data structure because the last added item is the first to be removed.
See below for an illustration of how a stack works. In the first item of illustration (1), we have a stack composed of 5 elements, which were inserted chronologically in the following order: p0, p1, p2, p3, and finally p4. The second part of illustration (2) shows the state of the stack s after insertion of a new element (p5). The third part (3) shows the stack s after removal of an element. As you can see, the removed element was the last one to be inserted (p5). In the latter part of the illustration (4), a further removal of element from the stack is shown, this time p4. If there were more removal operations, we would have to remove, in order, the elements: p3, p2, p1 and p0.
________ |----p5----|
|----p4----| |----p4----| |----p4----|
|----p3----| |----p3----| |----p3----| |----p3----|
|----p2----| |----p2----| |----p2----| |----p2----|
|----p1----| |----p1----| |----p1----| |----p1----|
|----p0----| |----p0----| |----p0----| |----p0----|
Stack s --- s.push(p5) --- s.pop() ---- s.pop()
(1) ________ (2) _________ (3)________ (4)
- Implementation
For the implementation of stacks we can use a list as structure for data storage. Just now define how the operation will work.
This code is called an implementation of the ADT Stack. Generally, an implementation is a set of methods that satisfy the syntactic and semantic requirements of an interface.
Here is an implementation of ADT Stack that uses a Python list:
- Creating a Stack
init: A Stack object contains an attribute called items that is a list of items in the stack. The boot method defines items as an empty list.
def __init__(self) :
self.items = []
- Adding elements
Push: To add a new item on the stack, push puts it in items. The method append() appends a passed object into the existing list.This method adds an element to the stack. So it place that element above the top stack.
def push(self, item) :
self.items.append(item)
- Extracting elements
This function extracts an element to the stack.
If the stack is empty, we don't extract any element.
Pop: To remove a stack item, pop uses the list method to remove and return a last item from the list.
def pop(self) :
return self.items.pop()
Finally, to verify that the stack is empty, isEmpty will purchase items from an empty list.
def isEmpty(self) :
return (self.items == [])
Now let's show how the stack works.
- Work Result
Example 1:
First, let’s create a stack with 4 numbers. First we use the stack() function, that is the method that will call the class stack functions and save the result into a stack data type variable. Then we add the elements with the s.push() function.
Code of the main function.
s=stack() #Create and initialize the stack methods
s.push(10) #Insert the item ’10’ in to the stack
s.push(20) #Insert the item ’20’ in to the stack
s.push(30) #Insert the item ’30’ in to the stack
s.push(10) #Insert the item ’10’ in to the stack
print ("the stack is")
print (s.items) #Print the stack
the final result is as follows:
Example 2:
Let’s repeat the first example but now we are going to extract two elements from the stack.
Code of the main function.
s=stack() #Create and initialize the stack methods
s.push(10) #Insert the item ’10’ in to the stack
s.push(20) #Insert the item ’20’ in to the stack
s.push(30) #Insert the item ’30’ in to the stack
s.push(10) #Insert the item ’10’ in to the stack
s.pop() #Extract
s.pop() #Extract
print ("The stack is")
print (s.items)
the final result for this test is as follows:
Unlike the fist example, we modified the stack so it just has the elements 2 and 1 because 4 and 3 were extracted (in that order).
Example 3:
Another fundamental operation that should be available in a Stack is a method that returns a boolean indicating whether the stack is empty.
s=stack() #Create and initialize the stack methods
s.push(10) #Insert the item ’10’ in to the stack
s.push(20) #Insert the item ’20’ in to the stack
s.push(30) #Insert the item ’30’ in to the stack
s.pop() #Extract
s.pop() #Extract
print ("The stack is")
print (s.items)
print ("Empty Stack?")
print (s.isEmpty()) #returns Boolean indicating if the stack is empty
Full Code
class stack:
def __init__(self) :
self.items = []
def push(self, item) :
self.items.append(item)
def pop(self) :
if not self.isEmpty():
return self.items.pop()
def isEmpty(self) :
return (self.items == [])
s=stack() #Create and initialize the stack methods
s.push(10) #Insert the item ’10’ in to the stack
s.push(20) #Insert the item ’20’ in to the stack
s.push(30) #Insert the item ’30’ in to the stack
s.push(10) #Insert the item ’10’ in to the stack
s.pop() #Extract
s.pop() #Extract
print ("The stack is")
print (s.items)
Run the code and learn python.
Curriculum
Posted on Utopian.io - Rewarding Open Source Contributors