Outline

Linear Structures

Linear data structures refer to data collections whose items are ordered depending on how they are added or removed. Examples include stacks, queues, deques and lists.

Stacks

Examples of stacks occur in everyday situations, like the stack of trays or plates in canteens.

A stack is an ordered collection where the order that its items are removed is exactly the reverse of the order that they were placed.

Such ordering principle is called LIFO (last-in first-out)

Define the stack as an abstract data type

The stack abstract data type is defined by the following structure and operations:

Stack() creates a new empty stack.
push(item) adds an item to the top of the stack
pop() returns and removes the item on the top of the stack
peek() returns but not removes the item on the top of the stack
isEmpty() check whether a stack is empty
size() returns the number of items in a stack

Python implementation

Following are 2 versions to implement using a list.

The first one assumes the end of the list to hold the top item of the stack, while the second one uses a list where the top is at the beginning.

# Implementation 1: the top of stack is at the beginning of the list
class Stack:
    def __init__(self):
        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 isEmpty(self):
        return self.items == []

    def size(self):
        return len(self.items)

# Implementation 2: the top of stack is at the end of the list
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.insert(0,item)

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

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

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

    def size(self):
        return len(self.items)

Performance of the 2 implementations above differs.

append() and pop() are O(1), so that implementation 1 performs push and pop in constant time no matter how many items the stack has.

In implementation 2, insert(0) and pop(0) are O(n) for a stack of size n.

Stack applications in real-world

Check whether symbols in a string are balanced

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index=0
    while index<len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "([{":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop()
                if not matches(top, symbol):
                    balanced = False

        index += 1

    if balanced and s.isEmpty():
        return True
    else:
        return False

def matches(o, c):
    os = "({["
    cs = ")}]"
    return os.index(o) == cs.index(c)

print(parChecker('{{([][])}()}'))

True

print(parChecker('[{()]'))

False

Convert decimal numbers for other bases

def baseConverter(decNumber, base):
    digits = "0123456789ABCDEF"
    remStack = Stack()

    while decNumber > 0:
        rem = decNumber % base
        remStack.push(rem)
        decNumber = decNumber // base

    result = ""
    while not remStack.isEmpty():
        result = result + digits[remStack.pop()]

    return result

baseConverter(25,16)

'19'

Stack