Stack & Queue Implementation

Posted on | In , |

Stack and queue abstract data types implementation with Python.

Stack

  • LIFO structure
  • Graph algorithm: depth-first search can be implemented with Stack
  • Finding Euler-cycles in a Graph
  • Finding strongly connected components in a graph
  • If we use recursion, the OS will use stacks
  • Most important application of stacks: stack memory
    • it is a special region of the memory (in the RAM)
    • it keeps track of the point to which each active subroutine should return control when it finishes executing
    • store temporary variables created by each function
    • stack memory is limited

Heap Memory

  • The heap is a region that is not automatically arranged for you
  • This is a large region of memory, unlike stack memory
  • C: malloc() and calloc() function, with pointers
  • Java: reference types and objects are on the Heap
  • We have to deallocate these memory chunks as it it not managed automatically. If not, memory leak!
  • Slower than stack memory because of pointers
stack memory heap memory
limited in size no size limit
fast access slow access
local variables objects
space is managed efficiently by CPU memory may be fragmented
variables cannot be resized variables can be resized // realloc()

Queue

  • FIFO structure
  • It can be implemented with linked lists
  • application: BFS
  • Operational research applications or stochastic models relies heavily on queues

Implementation

Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# stack is an abstract data type (interface), LIFO
# there are 3 operations: push(), pop(), peek()


class Stack:

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

    def isEmpty(self):
        return self.stack == []

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

    def pop(self):
        data = self.stack[-1]
        del self.stack[-1]
        return data

    def peek(self):
        return self.stack[-1]

    def sizeStack(self):
        return len(self.stack)


# test
stack = Stack()

stack.push(1)
stack.push(2)
stack.push(3)

print(stack.sizeStack())
print('popped: ', stack.pop())
print(stack.sizeStack())

print('peeked: ', stack.peek())
print(stack.sizeStack())

Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# queue is an abstract data type (interface) FIFO
# operations: enqueue(), dequeue(), peek()
# e.g: CPU scheduling, IO buffer


class Queue:

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

    def isEmpty(self):
        return self.queue == []

    def enqueue(self, data):
        self.queue.append(data)

    def dequeue(self):
        data = self.queue[0]
        del self.queue[0]
        return data

    def peek(self):
        return self.queue[0]

    def sizeQueue(self):
        return len(self.queue)


# test
queue = Queue()

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)

print('dequeue: ', queue.dequeue())
print(queue.sizeQueue())

print('peek: ', queue.peek())
print(queue.sizeQueue())
0%