Understanding Stacks and Queues in python

Question

So i was given this question. Consider the Stack and the Queue class with standard set of operations. Using the Stack and Queue class, what items are contained in them just before the mysteryFunction is called AND just after the mysteryFunction is called?

Here is the code:

def mysteryFunction(s, q):
    q.enqueue('csc148')
    q.enqueue(True)
    q.enqueue(q.front())
    q.enqueue('abstract data type')

    for i in range(q.size()):
        s.push(q.dequeue())

    while not s.is_empty():
        q.enqueue(s.pop())


if __name__ == '__main__':
    s=Stack()
    q=Queue()

#About to call mysteryFunction
#What are contents of s and q at this point?
    mysteryFunction(s, q)
#mysteryFunction has been called.
#What are contents of s and q at this point?

I'm having trouble understanding object oriented programming as i'm new to this topic. Is there any link that breaks down Stacks and Queues and what they do?

Answer 1

class stack:
    def __init__(self,n):  #constructor
        self.no = n  # size of stack
        self.Stack = []  # list for store stack items
        self.top = -1

    def push(self): # push method
        if self.top == self.no - 1:  # check full condition
            print("Stack Overflow.....")
        else:
            n = int(input("enter an element :: "))
            self.Stack.append(n)  # in list add stack items use of append method
            self.top += 1.  # increment top by 1

    def pop(self):  # pop method

        if self.top == -1:  # check empty condition
            print("Stack Underflow....")
        else:
            self.Stack.pop(). # delete item from top of stack using pop method
            self.top -= 1  # decrement top by 1

    def peep(self):  #peep method
        print(self.top,"\t",self.Stack[-1])  #display top item

    def disp (self):  # display method
        if self.top == -1:  # check empty condition
            print("Stack Underflow....")
        else:
            print("TOP \tELEMENT")
            for i in range(self.top,-1,-1):  # print items and top
                print(i," \t",self.Stack[i])


n =  int(input("Enter Size :: "))  # size of stack
stk = stack(n)  # object and pass n as size

while(True):  # loop for choice as a switch case
    print(" 1: PUSH ")
    print(" 2: POP ")
    print(" 3: PEEP ")
    print(" 4: PRINT ")
    print(" 5: EXIT ")

    option = int(input("enter your choice :: "))
    if option == 1:
        stk.push()
    elif option == 2:
        stk.pop()
    elif option == 3:
        stk.peep()
    elif option == 4:
        stk.disp()
    elif option == 5:
        print("you are exit!!!!!")
        break
    else:
        print("Incorrect option")

Answer 2

The first code explains about the stack , we need to create a list and while pushing the element use append and fill the list , similar to what we have in array stack. While pop , pop out the end from where you pushed it.

class Stack:

def __init__(self):
    self.stack = []

def push_element(self,dataval):
    self.stack.append(dataval)
    return self.stack


def pop_element(self):
    if len(self.stack) ==0:
        print("Stack is empty")
    else:
        self.stack.pop()
    return self.stack

def peek_element(self):
    return self.stack[0]

class Queue:

 def __init__(self):
   self.stack = []

 def push_ele(self,data):
   self.stack.append(data)

def pop_ele(self):
   self.stack.pop(0)

def display(self):
   print(self.stack)

Answer 3

STACK #LIFO

class stack(object):
 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.pop()
 def peek(self):
    return self.items[len(self.items) - 1]
 def size(self):
    return (len(self.items))
s = stack()
print (s.isEmpty())
>> True
s.push(1)
s.push('3')
s.peek()
>>'3'
s.size()
>> 2

Queue #FIFO

class Queue(object):
 def __init__(self):
    self.items = []
 def isEmpty(self):
    return self.items==[]
 def enqueue(self,item):
    self.items.insert(0,item)
 def dequeue(self):
     return self.items.pop()
 def size(self):
    return (len(self.items))
q = Queue()
q.isEmpty()
>>True
q.enqueue(1)
q.enqueue(2)
q.dequeue()
>>1

Answer 4

See following links for more information:

Stack
Queue

Visually these two data structures can be seen in a following way:

Stack:

Description:

There are variations of this data structure. However, in simple terms - as one can observe in the image provided, when you add to this data structure you place on top of what is already there and when you remove you also take from the top. You can view it as a stack of books which you go through one by one starting from the top and all the way down.

Queue

Description:

There are also variations on this particular data structure, however in simple terms - as you can see in the image provided, when you add to this data structure the new element goes in the begining and when you remove its the last element from the list which is being removed. You can imagine it as a queue you got in a shop where you stand behind a lot of people waiting for your turn to come to the counter to pay for your items.

Answer 5

To test this line by line, here are implementations of the classes (wrappers around deque) that are used in the task:

from collections import deque

class Queue(deque):
    enqueue = deque.append
    dequeue = deque.popleft
    def front(self):
        return self[-1]
    def size(self):
        return len(self)

class Stack(deque):
    push = deque.append
    def is_empty(self):
        return not self

Answer 6

In general, stacks are LIFO and queues are FIFO.

In Python, you can use the collections module to experiment with stacks and queues:

>>> from collections import deque
>>> stack = deque()
>>> stack.append(10)
>>> stack.append(20)
>>> stack.append(30)
>>> stack
deque([10, 20, 30])
>>> stack.pop()           # LIFO
30
>>> stack.pop()
20
>>> 
>>> queue = deque()
>>> queue.append(10)
>>> queue.append(20)
>>> queue.append(30)
>>> queue
deque([10, 20, 30])
>>> queue.popleft()       # FIFO
10
>>> queue.popleft()
20