Hey, Mom! Talking to My Mother #925 - Stack Data Structure part one

Hey, Mom! Talking to My Mother #925 - Stack Data Structure part one

Hi Mom,

Here's my prep for talking about stack data structures at tomorrow's Code and Learn Meet Up.

I offered to present and so now I am trying to prepare. I chose something I know a little about but that, also, I am working on, actively.

Also, I wanted to share something that might have universal appeal to the people who attend Code and Learn as well as serving as a review for me. I am hoping that this subject and what I have to share meets that goal.

In this presentation, I will describe stack data structures in general, then I will describe in brief a somewhat complicated example that uses interfaces in Java. I will show the code and show the program running. I will also provide a Git Hub link for the code repository. Lastly, I will show a C program I wrote to implement a stack and see if we can fix it as a group as the code is currently throwing various errors. I may spread this prep over two parts today's, this one, and tomorrow's. Unless I make it longer... :-)

I am hoping that these two posts will be useful resources for people who search the web for content on stack data structures in various languages and may come across my entries via that search. I also plan to share these two posts with the Vantechy Code and Learn group.

Another ulterior motive for these posts is to support "my study" as much as "my teaching." I wrote both the Java and the C programs, and I am about to claim on documents like a résumé that I understand these languages, and I can read code, understand it, and explain it. So I am testing that claim.

STACK DATA STRUCTURES

A stack data structure is a design for using code to store data. As the name implies, imagine anything stacked, like a set of plates or tennis balls in a tube. Consider each item, such as the tennis balls, to be a piece of data. With the tennis balls, the stack of balls can only be modified from the top as in a new ball can be added to the top or removed from the top, but the order matters. This ordering is known most commonly as LIFO -- Last In, First Out -- though sometimes as FILO -- First In, Last Out.

Given these restrictions, programmers use this data structure when order matters, such as parsing text. A classic example, which is handled in my Java program, is reversing a string. To perform that operation, the order must be taken into account, but it is easy enough to move letters out of a word or a phrase (a string) one at a time and re-assemble the letters in reverse order. Thus, "Hello World" becomes "dlroW olleH."

Such a system would be applied for web pages, as a user clicks links, the browser stores the history of the pages, and if the user wishes to back up, the "back" direction button can be employed. Similarly, a word processor (or even the text edit feature of Blogger where I draft these posts) saves the most recent keystrokes up to a certain number designated to store such data ("the stack"), so that a user my click the "undo" button to reverse changes to a document in the order the changes were made.

Expression evaluation would also be an instance to use a stack data structure because the order of operations in the evaluation of the expression matters, such as A * (B + C) / D: add B and C, then multiply by A and divide by D. Order matters! One can see how such expression evaluation would be performed by a calculator and how the machine would have to be pre-programmed to evaluate the expression entered by the user and then how to return the proper result.

As such, there are two main functions that must be programmed to make the stack work. Commonly these are called PUSH and POP.

Push adds data to the top or front of the stack, like dropping a new tennis ball into the tube. Pop removes the top item from the stack, akin to reaching into the tube and taking out the top most tennis ball.

Additionally, most stack programs use a few other functions, such as a check to see if the stack is empty and a PEEK method to look at the top of the stack to see what is there.

In most languages, a programmer would have two choices to create a stack data structure, using arrays and using a similar data storage unit called a linked list.

Most languages have an array data structure, a collection of elements that can be counted by an index number. Python calls this data structure a list, but it's the same as an array.

Though an array is easy to create for this type of data structure, it has the drawback of not growing as the number of data elements grows: what is known as dynamic growth.

The dynamic growth issue is one solved by higher programming languages. As we will see with my program in the C language, as the array (linked list) grows, new memory has to be allocated for the size of the data structure. In the Python example below, list re-size dynamically without the need to for the programmer to write code that increases the memory size. This re-sizing is written into the list object in Python (which is written in C), and so it takes place "under the hood." See the LIST OBJECT CODE IN PYTHON here.

As we will see with my Java code, I was not allowed to use an Array List, which is a resizable array Java pre-written function (actually, it's a class or object in Java). The purpose of the program was to write the stack implementation similar to the code for the Array List class.

But to start, let's dissect the Python version with an array as it is the easier to understand.

In the Python code, the basics are laid out simply. a createStack function creates a stack list object.

Look at the simple code for the Push function:

# Function to add an item to stack. It increases size by 1

def push(stack, item):

    stack.append(item)

    print("pushed to stack " + item)

The list called "stack" and the item to be added are passed in as arguments. The "append" method is called on the list object, passing in the item as the argument. In Python, this code is very simple and streamlined:

stack.append(item)

Then the item is printed out as a way to update and data check.

These two functions are called from the main part of the Python program:

stack = createStack()

push(stack, str(10))

A stack is created called "stack."

The string data "10" is pushed onto the stack.

The use of Python to show a stack implementation is a a bit disingenuous as the code shown here is not written from "scratch." As an object, Python's lists have many methods. Though there is no "push" method, there is both append and insert to add items to the list. Here the code uses "append" to add an item to the list rather than writing the code for what's happening when "append" is called on the list. But at least in this code, push is somewhat its own function. However, Pop( ) is not.

Here, the coder simply calls the pre-defined Pop( ) function on the list. When Pop is called on the stack, first, the code calls the isEmpty function. The isEmpty function simply checks if the stack's length property is zero and will return "true" if the list is empty. In the pop function, if the list is empty, the program returns "minus infinite," which on my machine when I ran it was the number = -2147483648.

If not empty, the code calls the predefined Pop( ) function on the stack, which returns the item popped. So, if pop(stack) is called after just "10" is pushed, then it will return "10." But this is all very easy, and not at all like writing the code to perform the "pop" operation.

And so, the Python program performs the basic operations of adding items to the stack and removing items in a LIFO order. Visually, if printed, the list would be like this:

[10, 20, 30]

and items removed from right to left, which may be counter-intuitive to the way you may visualize a stack based on the description and the idea that the stack has a top. You may be thinking left to right.

I added three pop calls (four total) to the code and this was the output:


C:\Users\GalacticMonkeyWrench\Desktop\Python_work>python stack.py
pushed to stack 10
pushed to stack 20
pushed to stack 30
30 popped from stack
20 popped from stack
10 popped from stack
-2147483648 popped from stack

Still, this Python code gives a good sense for a stack implementation in its basic form.

This is the Python version of a stack program with an array (called a list in Python) from
https://www.geeksforgeeks.org/stack-data-structure-introduction-program/

# Python program for implementation of stack # import maxsize from sys module # Used to return -infinite when stack is empty from sys import maxsize # Function to create a stack. It initializes size of stack as 0 def createStack():     stack = []     return stack # Stack is empty when stack size is 0 def isEmpty(stack):     return len(stack) == 0 # Function to add an item to stack. It increases size by 1 def push(stack, item):     stack.append(item)     print("pushed to stack " + item)       # Function to remove an item from stack. It decreases size by 1 def pop(stack):     if (isEmpty(stack)):         return str(-maxsize -1) #return minus infinite           return stack.pop() # Driver program to test above functions    stack = createStack() push(stack, str(10)) push(stack, str(20)) push(stack, str(30)) print(pop(stack) + " popped from stack")

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

To create a linked list format, which is the more common means to implement a stack data structure among programmers as far as I can tell from reading.

Again, like with the list implementation, the Python code for linked list uses established methods, in this case an object. However, in this code, more of it is written as less can rely on pre-written methods.

Here, the program works much like the Java and C versions I am planning to share. The StackNode class initializes a node, one data unit, in the stack data structure. The node has two values: the data and the value of the next item in the "list," -- quoted because this Python program does not use the list object pre-written in Python --  hence the list is linked.

The other methods are much like in the previous examples except that there are no pre-written methods to fall back on as with the list object. Here, the coder must write how each method operates.

For instance, with push the method must first initialize a new node by calling the Stacknode constructor and passing in the data, storing the return value in "newNode" to represent the new piece of data. Note that the Push method takes two arguments: "self" (the stack, more on this in a minute) and the data to be added.

Then, the code sets the next value of the new node (NewNode.next) equal to the current top of the stack, which is called self.root. "The "root" attribute is shown in the Stack class that holds all the nodes. It is initialized in the constructor of that class with the first call. To understand more about "self" as the commonly used word (not a reserved keyword) in Python to refer to the object itself, see my post HERE on "A case for self in classes."

After the new node is created and the next value aimed at the current top of the stack, then the new node is pushed on to the stack and made to be the new root:

self.root = newNode

The New node overwrites the current self.root (former top) and its next attribute still contains the value of the former top, self.root.

Then, there's a print statement to show the user what has been done.

def push(self, data):

        newNode = StackNode(data)

        newNode.next = self.root

        self.root = newNode

        print "%d pushed to stack" %(data)

Similarly, the pop method only needs to take the "self" parameter as an argument, which is the stack object defined by the Stack class.

Like the pop in the other example, this one first checks if the stack is empty because then there is nothing to pop.

The isEmpty method is even simpler here than in the other program:

def isEmpty(self):

        return True if self.root is None else  False

The method will return true if the the root is "none" as in there's no data there; otherwise it returns false.

Back in the pop method, if the program gets true back, it performs that same minus infinity thing. But this time, the program throws an error because the coder cast the "minus infinity" to a float. See the output below after I added enough pop statements to call pop on an empty stack. I think I could fix this issue, but I am not inclined to work on it right now.

If there is an element to pop (IE. the stack contains elements), then a "temp" variable is used to hold the current top value, the value to be popped, which is what the code that runs the pop method in Python's list object must do.

With the item to be popped stored in temp, the new "self.root" or top value is created with this statement:

 self.root = self.root.next

In so doing, the new self.root (top) becomes the previous next value for that item = self.root.next.

With a new top established, the popped item (temp.data) is stored in a variable called "popped" and returned to the calling function.

Here's the pop code.

def pop(self):

        if (self.isEmpty()):

            return float("-inf")

        temp = self.root

        self.root = self.root.next

        popped = temp.data

        return popped

Here's the output for crashing the program with too many calls to isEmpty.

OUTPUT
C:\Users\GalacticMonkeyWrench\Desktop\Python_work>python stackLink.py
10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20
20 popped from stack
Top element is 10
10 popped from stack
Traceback (most recent call last):
  File "stackLink.py", line 50, in
    print("Top element is %d " %(stack.peek()))
OverflowError: cannot convert float infinity to integer

+++++++++++++++

The program also has a peek method to allow the coder to look at what's on top, which you can see works from the output above.

This is the Python version of a stack program with an linked list from
https://www.geeksforgeeks.org/stack-data-structure-introduction-program/

# Python program for linked list implementation of stack # Class to represent a node class StackNode:     # Constructor to initialize a node     def __init__(self, data):         self.data = data         self.next = None class Stack:           # Constructor to initialize the root of linked list     def __init__(self):         self.root = None     def isEmpty(self):         return True if self.root is None else  False     def push(self, data):         newNode = StackNode(data)         newNode.next = self.root         self.root = newNode         print "%d pushed to stack" %(data)           def pop(self):         if (self.isEmpty()):             return float("-inf")         temp = self.root         self.root = self.root.next         popped = temp.data         return popped           def peek(self):         if self.isEmpty():             return float("-inf")         return self.root.data # Driver program to test above class stack = Stack() stack.push(10)        stack.push(20) stack.push(30) print "%d popped from stack" %(stack.pop()) print "Top element is %d " %(stack.peek()) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

So, there's the basics of a stack data structure in two forms in Python. In tomorrow's post, I will describe my Java implementation of the stack, though quickly, and then focus on the C program I have written in an attempt for us to find the bug.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
MORE RESOURCES

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Here's one description of Stack Data Structures:

http://www.studytonight.com/data-structures/stack-data-structure

Here's another:

https://www.geeksforgeeks.org/stack-data-structure-introduction-program/

ALSO these resources:

This YOU Tube video cannot be embedded:

Data structures: Array implementation of stacks

 

mycodeschool

https://youtu.be/sFVxsglODoo

Data structures: Array implementation of stacks in C

http://www.c4learn.com/c-programs/c-program-to-implement-stack-operations-using-array.html

Write a c program to implement a stack using an array and linked list

http://www.firmcodes.com/write-a-c-program-to-implement-a-stack-using-an-array-and-linked-list/

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Reflect and connect.

Have someone give you a kiss, and tell you that I love you, Mom.

I miss you so very much, Mom.

Talk to you tomorrow, Mom.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

- Days ago = 927 days ago

- Bloggery committed by chris tower - 1801.16 - 10:10

NEW (written 1708.27) NOTE on time: I am now in the same time zone as Google! So, when I post at 10:10 a.m. PDT to coincide with the time of your death, Mom, I am now actually posting late, so it's really 1:10 p.m. EDT. But I will continue to use the time stamp of 10:10 a.m. to remember the time of your death, Mom. I know this only matters to me, and to you, Mom.