Oct 08, 2019 push, which adds an element to the stack. Pop, which removes the most recent inserted element from the stack, if there is any. Top, gives you the topmost element from the stack if it exists. Elements are inserted and removed from the stack in a special manner, famously known as LIFO.
Implementing a Stack in PythonNow that we have clearly defined the stack as an abstract data type wewill turn our attention to using Python to implement the stack. Recallthat when we give an abstract data type a physical implementation werefer to the implementation as a data structure.As we described in Chapter 1, in Python, as in any object-orientedprogramming language, the implementation of choice for an abstract datatype such as a stack is the creation of a new class. The stackoperations are implemented as methods. Further, to implement a stack,which is a collection of elements, it makes sense to utilize the powerand simplicity of the primitive collections provided by Python.
We willuse a list.Recall that the list class in Python provides an ordered collectionmechanism and a set of methods. For example, if we have the list2,5,3,6,7,4, we need only to decide which end of the list will beconsidered the top of the stack and which will be the base. Once thatdecision is made, the operations can be implemented using the listmethods such as append and pop.The following stack implementation assumes thatthe end of the list will hold the top element of the stack. As the stackgrows (as push operations occur), new items will be added on the endof the list. Pop operations will manipulate that same end. Class Stack:def init(self):self.items = def isEmpty(self):return self.items def push(self, item):self.items.append(item)def pop(self):return self.items.popdef peek(self):return self.itemslen(self.items)-1def size(self):return len(self.items)Remember that nothing happens when we click the run button other than thedefinition of the class. We must create a Stack object and then use it.shows the Stack class inaction as we perform the sequence of operations from.
Notice that the definition of the Stack class isimported from the pythonds module. From pythonds.basic import Stacks=Stackprint(s.isEmpty)s.push(4)s.push('dog')print(s.peek)s.push(True)print(s.size)print(s.isEmpty)s.push(8.4)print(s.pop)print(s.pop)print(s.size)It is important to note that we could have chosen to implement the stackusing a list where the top is at the beginning instead of at the end. Inthis case, the previous pop and append methods would no longerwork and we would have to index position 0 (the first item in the list)explicitly using pop and insert. The implementation is shown in.
CodeLens: Alternative Implementation of the Stack class (stackcl1)This ability to change the physical implementation of an abstract datatype while maintaining the logical characteristics is an example ofabstraction at work. However, even though the stack will work eitherway, if we consider the performance of the two implementations, there isdefinitely a difference.
Recall that the append and popoperations were both O(1). This means that the first implementation willperform push and pop in constant time no matter how many items are onthe stack. The performance of the second implementation suffers in thatthe insert(0) and pop(0) operations will both require O(n) for astack of size n. Clearly, even though the implementations are logicallyequivalent, they would have very different timings when performingbenchmark testing.
Usually the first action we need to do on Stack is Push elements into it. The word Push is a computer science term that means 'add to the top.' Here we create a Stack.Start: A local variable is assigned to a new Stack containing 3 integers. The ints were added with the 10000 last.Then: We write each value of the stack to the Console in a foreach-loop with Console.WriteLine.Tip: We see that 10000 is displayed first. This is explained by the LIFO concept—last in, first out.LIFO: The last element added (with Push) to Stack is the first one removed (with Pop).