Data structures are what we create out of data and Python has some good standard data structures. Find out how it all works in this extract from Programmer's Python: Everything is Data.

Programmer's Python
Everything is Data

Is now available as a print book: Amazon

Contents

1. Python – A Lightning Tour
2. The Basic Data Type – Numbers
      Extract: Bignum
   
3. Truthy & Falsey
4. Dates & Times
5. Sequences, Lists & Tuples
      Extract Sequences 
6. Strings
      Extract Unicode Strings
7. Regular Expressions
8. The Dictionary
      Extract The Dictionary 
9. Iterables, Sets & Generators
      Extract  Iterables 
10. Comprehensions
       Extract  Comprehensions 
11. Data Structures & Collections
       Extract Stacks, Queues and Deques ***NEW!!!
12. Bits & Bit Manipulation
       Extract Bits and BigNum 
13. Bytes
       Extract Bytes And Strings
       Extract Byte Manipulation 
14. Binary Files
15. Text Files
16. Creating Custom Data Classes
        Extract A Custom Data Class 
17. Python and Native Code
        Extract   Native Code
    Appendix I Python in Visual Studio Code
    Appendix II C Programming Using Visual Studio Code

<ASIN:1871962765>

<ASIN:1871962749>

<ASIN:1871962595>

<ASIN:B0CK71TQ17>

<ASIN:187196265X>

Data Structures & Collections

So far we have focused on the inbuilt data structures that Python provides as part of the core language – the list, tuple, set and dictionary. There are also data structures that are fundamental to programming that do not correspond to Python’s built-in data structures, but they are very easy to implement or they are implemented for you in a suitable module. In this chapter we look at the stack, the queue and the deque, which are supplied structures in other languages but not in Python. Most of the additional data structures are in the collections module – but it also has a number of classes – OrderedDict, defaultdict, UserDict, UserList and UserString – which aren’t particularly useful in modern Python 3 and hence are not covered in this chapter.

As an example of implementing a data structure making use of the supplied data structures we create a binary tree class. This is a good example of using both stacks and queues, but turns out to be more complicated than you might expect. It is re-used in later chapters as an example of how to add your own data structures.

The Stack

The stack or more correctly, the LIFO stack, is a simple data structure with only two operations, referred to in the jargon as “push” and “pop”. You can think of it as a stack of pile of things that you only access via the top of the stack using two natural operations push and pop. Push stores something on the top of the stack and pop retrieves something from the top of the stack. It doesn’t have to be top of the stack – the bottom will do as well – but push and pop have to operate on the same location.

LIFO stands for Last In First Out and it has the important property of reversing the order of things. If you push three items, A, B and C on the stack in that order then when you pop them off you will receive them in the order C, B and A. The last item pushed on the stack is the first item to be popped from the stack – hence its name. You can think of a stack as a pile of books – you put the latest book on the top of the pile – that’s a push – and you take the next book to read from the top of the pile – that’s a pop.

Python doesn’t have a specific implementation of a stack as standard, but the list does the job so well it doesn’t need one. In place of “push” you can use append which stores an item at the end of the list. Python’s pop removes an item from the end of the list. So instead of push and pop we have append and pop and they work at the end of the list.

For example:

stack = []
stack.append("A")
stack.append("B")
stack.append("C")
print(stack.pop())
print(stack.pop())
print(stack.pop())

Each append adds the string to the end of the list and each pop retrieves an item from the end of the list. The print instructions display:

C
B
A

demonstrating that this really is a LIFO stack. After the print statements, stack is an empty list because everything has been removed from it. If you try to pop from an empty list then you will generate an IndexError exception.

Although append and pop are the only operations you generally need for a stack-like list it is sometime useful to be able to examine the top item and you can do this in Python using stack[-1]. Also notice that you can specify a particular element to pop using pop(i) which returns and removes the ith item in the list. You could use this to implement multiple stacks in a single list, each stack having its own starting location.