Stack and Queue are abstract data types in Computer Science. In this short post, I’ll try to cover them in as few words as possible.
Stack has a LIFO concept (last in first out). The last item that goes in is the first item that goes out. Example: A stack of books or plates.
While Queue has a FIFO concept (first in first out). The first item that goes in is the first item that goes out. Example: A queue of people at a counter.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Stack implementation | |
| class Stack(object): | |
| def __init__(self): | |
| self.items = [] | |
| def isEmpty(self): | |
| return self.items == [] | |
| def push(self, item): | |
| self.items.append(item) #imp | |
| def pop(self): | |
| return self.items.pop() #imp | |
| def peek(self): | |
| return self.items[-1] | |
| def size(self): | |
| return len(self.items) | |
| # Queue implementation | |
| class Queue(object): | |
| def __init__(self): | |
| self.items = [] | |
| def isEmpty(self): | |
| return self.items == [] | |
| def enqueue(self, item): | |
| self.items.append(item) #imp | |
| def dequeue(self): | |
| return self.items.pop(0) #imp | |
| def size(self): | |
| return len(self.items) | |
| # implementing a queue with 2 stacks | |
| class QueueTwoStacks(object): | |
| def __init__(self): | |
| self.in_stack = [] | |
| self.out_stack = [] | |
| def enqueue(self, item): | |
| self.in_stack.append(item) | |
| def dequeue(self): | |
| if len(self.out_stack) == 0: | |
| # Move items from in_stack to out_stack, reversing order | |
| while len(self.in_stack) > 0: | |
| newest_in_stack_item = self.in_stack.pop() | |
| self.out_stack.append(newest_in_stack_item) | |
| # If out_stack is still empty, raise an error | |
| if len(self.out_stack) == 0: | |
| raise IndexError("Can't dequeue from empty queue!") | |
| return self.out_stack.pop() |
I hope this helps to refresh your knowledge on Stack and Queues in under a minute (or a few minutes).
CS Mumbai 