3. Basic Data Structures

Book URL

3.2. What Are Linear Structures?

Stacks, queues, deques, and lists are examples of data collections whose items are ordered depending on how they are added or removed. Once an item is added, it stays in that position relative to the other elements that came before and came after it. Collections such as these are often referred to as linear data structures.
Linear structures can be thought of as having two ends. Sometimes these ends are referred to as the “left” and the “right” or in some cases the “front” and the “rear.” You could also call them the “top” and the “bottom.” The names given to the ends are not significant.
What distinguishes one linear structure from another is the way in which items are added and removed, in particular the location where these additions and removals occur. For example, a structure might allow new items to be added at only one end. Some structures might allow items to be removed from either end.

3.3. What is a Stack?

A stack (sometimes called a “push-down stack”) is an ordered collection of items where the addition of new items and the removal of existing items always takes place at the same end.
This end is commonly referred to as the “top.” The end opposite the top is known as the “base.”
LIFO, last-in first-out.
Stacks are fundamentally important, as they can be used to reverse the order of items. The order of insertion is the reverse of the order of removal.

3.4. The Stack Abstract Data Type

The stack operations are given below:

Stack() creates a new stack that is empty. It needs no parameters and returns an empty stack.
push(item) adds a new item to the top of the stack. It needs the item and returns nothing.
pop() removes the top item from the stack. It needs no parameters and returns the item. The stack is modified
peek() returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
isEmpty() tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
size() returns the number of items on the stack. It needs no parameters and returns an integer.

3.5. Implementing a Stack in Python



In [3]:

    
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)
    
# Testing client
s = Stack()

print(s.isEmpty())

s.push(4)
s.push('dog')
print(s.peek())

s.push(True)
print(s.size())

print(s.isEmpty())

s.push(8.4)

print(s.pop())
print(s.pop())
print(s.size())









    



True
dog
3
False
8.4
True
2

Stack examples

3.10. What Is a Queue?

A queue is an ordered collection of items where the addition of new items happens at one end, called the “rear,” and the removal of existing items occurs at the other end, commonly called the “front.”.
This ordering principle is sometimes called FIFO, first-in first-out. It is also known as “first-come first-served”.

3.11. The Queue Abstract Data Type

The queue operations are given below.

Queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.
enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing.
dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.
isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
size() returns the number of items in the queue. It needs no parameters and returns an integer.

3.12. Implementing a Queue in Python



In [5]:

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

#simple testing

q = Queue()
q.enqueue('hello')
q.enqueue('dog')
q.enqueue(3)
q.dequeue()









    Out[5]:





'hello'

3.15. What Is a Deque?



In [ ]: