Top Data Structures and Algorithms in Python

By the end of this lesson, you will have been introduced to the stack data structure and how it is implemented in Python, which we will utilize for problems throughout this chapter.

We are going to cover the following

What is Stack?
Stack Operations
- Push
- Pop
- Peek

In this lesson, we will consider the structure of the stack data and its implementation in Python.

In subsequent posts, we will provide specific problems where the stack is particularly useful. We're going to use the implementation that we develop in this lesson to solve these problems.

What is Stack?

First of all, let me explain what the stack is. It should be a relatively familiar concept based on the name. Suppose we have four books with the following riveting titles:

Right now, these books are scattered all over the floor, and we want to stack them up neatly.

And now we have a neat and clean stack of books! If we want to get a book out of this stack, we can get the book to the top. It's a bit precarious to take a book from the bottom, and we don't want to overturn the whole stack. So, we're going to take the top book down on the stack and read it or do whatever we want to do with it.

Let's assume that we want to take Book A. Right now, it's at the bottom of the stack, so we need to take Book D, put it down, do the same with Book C and Book B, and then we can access Book A.

This is the core concept behind a stack. The data structure stack is somewhat similar to the physical stack that you will most likely be familiar with. The Stack Data Structure allows one to put any programming object, vector or object on it, just like our example stack allowed us to place books on it.

Stack Operations

Push

The procedure to insert the elements into the stack is called a push. As we push the book to the stack, we place the book on the previous top element, which ensures that the new book becomes the top element. This is what we mean when we use the push process, we push the elements to the stack. We insert the elements into the stack, and the last element to be moved is the new top of the stack.

Pop

There's another process that we can do on the stack, popping. Popping is when we get the top book of the stack and bring it down. This means that when we remove an element from the stack, the stack follows the First-In, Last-Out property. This means that the top part, the last to be added, will be removed when we perform a pop operation.

Push and Pop are two simple routines that we're going to need for this data structure.

Peek

Another thing we can do is see the top element of the stack so we can ask the structure of the data: "What's the top element? "And that can be provided to us by using a peek process. Note that the peek operation does not remove the top element, it simply returns it.

We may also check whether or not the stack is empty, and a few other items, too, that will come along the way as we do it.

Now I'm going to create a stack class, and the class builder is going to initialize the Python list. The Python list has a ton of stuff that we're after, and it's going to make it easier for us to tweak Python's list implementation to match what we'd expect to see in a stack, namely, push/pop.

class Stack():
    def __init__(self):
        self.items = []

I define a class variable that I call items , and I assign it to an empty list. Self.items is generated when we build a stack object, so let's create a push method:

class Stack():
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

Push is going to be a part of this class, and it's going to be an argument. This item is the book in our example. We're bringing or moving the name of the book to the top of the stack.

append is a built-in method for a Python list that adds the item to the end of the list. This is just what we want to do for our stack in the push method.

class Stack():
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)                

    def pop(self):
        return self.items.pop()

The other approach that we need to incorporate is pop. Since we base this on a list, Python also makes it really simple. There is an implicit pop method that returns the last element to the list.

Another thing we're going to do is add a couple more approaches, but before that, I'm going to do a test drive.

class Stack():
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)                

    def pop(self):
        return self.items.pop()

    def get_stack(self):
        return self.items

myStack = Stack()
myStack.push("A")
myStack.push("B")
print(myStack.get_stack())
myStack.push("C")
print(myStack.get_stack())
myStack.pop()
print(myStack.get_stack())

Output
['A', 'B']
['A', 'B', 'C']
['A', 'B']

We're making a method called get stack (). This returns the list of things that forms the center of the stack. Then I describe the stack object, MyStack, on line 17, and I push A and B onto the stack, lines 18-19. After these operations, I can print myStack and the output is ['A' 'B']. A is at the bottom of the stack, and B is at the top. Then we push C to line 21, and the performance is ['A', 'B' 'C'], which means that C is the peak.

We grasp the fundamentals of the stack. Some of the other methods that we can use in this are useful, that is, we might have a method called is empty. It returns whether or not the stack is empty.

class Stack():
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)                

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return self.items == []

    def get_stack(self):
        return self.items

myStack = Stack()
print(myStack.is_empty())

Output
True

We're going to get True here because there's nothing on the stack at this point. If we push something and call is empty(), we're supposed to get false. You should try it out on your own.

class Stack():
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)                

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return self.items == []

 17   def peek(self):
 18      if not self.is_empty():
 19       return self.items[-1]

    def get_stack(self):
        return self.items

myStack = Stack()
myStack.push("A")
myStack.push("B")
myStack.push("C")
myStack.push("D")
print(myStack.peek())

Output
D

Now we have the peek operation on line 17 which tells us the topmost element of the stack.

If Peek is called to the stack in the code above, D should be returned. Peek checks if the stack is not empty on line 18 , and if it is not empty, returns the last element of the list, which in this case is the top element of the stack. We return self.items[-1] to line 19 , which is the last item in the Python list. So, at first, we get D as the element that Python thinks is at the top of the stack.

Go ahead and set up a stack object. You don't have to restrict yourself to letters or strings or something like that, you might push numbers as well. Only play with this data structure to get a sense of how it works. I'm going to see you in the next lesson.

QUIZ :

It's quiz time! Test yourself by solving these questions about stacks. Comment your answers

The peek operation of stack removes and returns the top of the stack.
```
 a. True
 b. False
```

Which of the following is true about stacks?

a. Stacks follow the First-In, First-Out property.
b. New elements are inserted at the bottom of the stack.
c. Stacks follow the First-In, Last-Out property.
d. Stack is always implemented using linked lists.

Removing the top element from the stack requires moving out all the elements in the stack.

a. True b. False
What is the output of the following code?

myStack = Stack()
myStack.push("A")
myStack.push("B")
myStack.pop()
myStack.push("C")
myStack.push("D")
myStack.pop()
myStack.pop()
print(myStack.peek())

What are the basic operations of a stack?

A) 
push()
pop()

B)
push()
pop()
isEmpty()
peek()

C)
push()
pop()
isEmpty()
peek()
get_stack()

Conclusion :

In this tutorial, you learnt stack data structure & Stack Operations and how it is implemented in Python,

Next Coming Up :

Commonly asked Stacked Interview questions step by step implementation with Algorithms
How to reverse a string using a stack with step by step implementation with Algorithms
How to Convert Decimal Integer to Binary Using Stack

If this article was helpful, please share and also subscribe to my newsletter to be notified when I ever post a new subject.