List Data Type Stack and Queue in Python

 

List Stack and Queue Data Type

Stack: A stack is a linear data structure in which all the insertion and deletion of data or you can say its values are done at one end only, rather than in the middle. Stacks can be implemented by using arrays of type linear.

Stack works on the principle of “Last-in, first-out” (LIFO) or “First-in, Last-out” (FILO). Also, the inbuilt functions in Python make the code short and simple. To add an item to the top of the list, i.e., to push an item, we use append() function and to pop out an element we use pop() function. These functions work quiet efficiently and fast in end operations.

Stack operations

1.     Push – (Insert an element in Stack)

2.     Pop – (Delete an element from Stack)

3.     Peek – (Display the last element of Stack)

4.     Display – (Display list or Stack)

5.     Exit – (Quit program)

 

Example

look at an example and try to understand the working of push() and pop() function:

# Python code to demonstrate Implementing 

# stack using list

st = ["Red", "Green", "Blue"]

stack.append("Yellow")

stack.append("Pink")

print(st)

  

# Removes the last item

print(st.pop())

  

print(st)

  

# Removes the last item

print(st.pop())

  

print(st)

Output:

[‘Red’, ‘Green’, ‘Blue’, ‘Yellow’, ‘Pink’]

Pink

[‘Red’, ‘Green’, ‘Blue’, ‘Yellow’]

Yellow

[‘Red’, ‘Green’, ‘Blue’]

 Queue: A queue is a linear list of elements in which deletion of an element can take place only at one end called the front and insertion can take place on the other end which is termed as the rear. The term front and rear are frequently used while describing queues in a linked list. In this chapter, you will deal with the queue as arrays.

Queue works on the principle of “First-in, first-out” (FIFO). Below is list implementation of queue. We use pop(0) to remove the first item from a list.

Queue operations

1.      Enqueue – (Add an item to the queue)

2.      Dequeue – (Remove an item from the queue)

3.      Front – (Get the front item from queue)

4.      Rear – (Get the last item from queue)

 

Example

Queue works on the principle of “First-in, first-out” (FIFO). Below is list implementation of queue. We use pop(0) to remove the first item from a list.

# Python code to demonstrate Implementing 

# Queue using list

qu = ["Red", "Green", "Blue"]

qu.append("Yellow")

qu.append("Pink")

print(qu)

  

# Removes the first item

print(qu.pop(0))

  

print(qu)

  

# Removes the first item

print(qu.pop(0))

  

print(qu)

Output:

[‘Red’, ‘Green’, ‘Blue’, ‘Yellow’, ‘Pink’]

Red

[‘Green’, ‘Blue’, ‘Yellow’, ‘Pink’]

Green

[‘Blue’, ‘Yellow’, ‘Pink’]

Using Dque

In case of stack, list implementation works fine and provides both append() and pop() in O(1) time. When we use deque implementation, we get same time complexity.

# Python code to demonstrate Implementing 

# Stack using deque

from collections import deque

qu = dq(["Apple", "Banana", "Kivi", "Orange"])

print(qu)

qu.append("Grapes")

print(queue)

qu.append("Papaya")

print(queue)

print(qu.pop())                 

print(qu.pop())                 

print(qu)

Output:

deque([‘Apple’, ‘Banana’, ‘Kivi, ‘Orange’])

deque([‘Apple’, ‘Banana’, ‘Kivi’, ‘Orange’, ‘Grapes’])

deque([‘Apple’, ‘Banana’, ‘Kivi’, ‘Orange’, ‘Grapes’, ‘Papaya’])

Papaya

Grapes

deque([‘Apple’, ‘Banana’, 'Asif', ‘Orange’])

But when it comes to queue, the above list implementation is not efficient. In queue when pop() is made from the beginning of the list which is slow. look at an example and try to understand queue using collections.deque:

# Python code to demonstrate Implementing 

# Queue using deque

from collections import deque

qu = dq(["Apple", "Banana", "Kiwi", "Orange"])

print(qu)

qu.append("Papaya")

print(qu)

qu.append("Grapes")

print(qu)

print(qu.popleft())                 

print(qu.popleft())                 

print(qu)

Output:

deque([‘Apple’, ‘Banana’, ‘Kiwi’, ‘Orange’])

deque([‘Apple’, ‘Banana’, ‘Kiwi’, ‘Orange’, ‘Papaya’])

deque([‘Apple’, ‘Banana’, ‘Kiwi’, ‘Orange’, ‘Papaya’, ‘Grapes’])

Apple

Banana

deque([‘Kiwi’, ‘Orange’, ‘Papaya’, ‘Grapes’])

Exercise 1

Stack Operation

a=[]
while True:
    b=int(input('''
    1 Push item
    2 pop item
    3 peek display last item
    4 display - display stack
    5 exit
    '''))
    if b==1:
        n=input("Enter Value: ");
        a.append(n)
        print(a)
    elif b==2:
        if len(a)==0:
            print("Empty list")
        else:
            p=a.pop()
            print(p)
            print(a)
    elif b==3:
        if len(a)==0:
            print("Empty list")
        else:
            print("This is last Stack value: ",a[-1])
    elif b==4:
        print("Display stack",a)
    elif b==5:
        break;
    else:
        print("Invalid Choice")

Exercise 2

Queue Operation

a=[]
while True:
    b=int(input('''
    1 enqueue item
    2 dequere item
    3 front display front item from quere
    4 rear - display last item form quere
    5 display
    6 exit
    '''))
    if b==1:
        n=input("Enter Value: ");
        a.append(n)
        print(a)
    elif b==2:
        if len(a)==0:
            print("Empty list")
        else:
            del a[0]
            print(a)
    elif b==3:
        if len(a)==0:
            print("Empty list")
        else:
            print("This is first queue value: ",a[0])
    elif b==4:
        print("Display last queue",a[-1])
    elif b==5:
        print(a)
    elif b==6:
        break;
    else:
        print("Invalid Choice")

<<Previous                                                  Next>>