<< Chapter < Page Chapter >> Page >

node := stack.stackPointer

stack.stackPointer := node.next

element := node.data

return element

}

function top(Stack stack) { // return 'top' node

return stack.stackPointer.data

}

function length(Stack stack) { // return the amount of nodes in the stack

length := 0

node := stack.stackPointer

while node not null {

length := length + 1

node := node.next

}

return length

}

As you can see, these functions pass the stack and the data elements as parameters and return values, not the data nodes that, in this implementation, include pointers. A stack may also be implemented as a linear section of memory (i.e. an array), in which case the function headers would not change, just the internals of the functions.

Implementation

A typical storage requirement for a stack of n elements is O(n). The typical time requirement of O(1) operations is also easy to satisfy with a dynamic array or (singly) linked list implementation.

C++'s Standard Template Library provides a "stack" templated class which is restricted to only push/pop operations. Java's library contains a Stack class that is a specialization of Vector. This could be considered a design flaw because the inherited get() method from Vector ignores the LIFO constraint of the Stack.

Here is a simple example of a stack with the operations described above in Python. It does not have any type of error checking.

class Stack:

def __init__(self):

self.stack_pointer = None

def push(self, element):

self.stack_pointer = Node(element, self.stack_pointer)

def pop(self):

(e, self.stack_pointer) = (self.stack_pointer.element, self.stack_pointer.next)

return e

def peek(self):

return self.stack_pointer.element

def __len__(self):

i = 0

sp = self.stack_pointer

while sp:

i += 1

sp = sp.next

return i

class Node:

def __init__(self, element=None, next=None):

self.element = element

self.next = next

if __name__ == '__main__':

# small use example

s = Stack()

[s.push(i) for i in xrange(10)]

print [s.pop() for i in xrange(len(s))]

The above is admittedly redundant as Python supports the 'pop' and 'append' functions to lists.

3.1.2. application

(From Wikipedia, the free encyclopedia)

Stacks are ubiquitous in the computing world.

Expression evaluation and syntax parsing

Calculators employing reverse Polish notation use a stack structure to hold values. Expressions can be represented in prefix, postfix or infix notations. Conversion from one form of the expression to another form needs a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages are context-free languages allowing them to be parsed with stack based machines.

For example, The calculation: ((1 + 2) * 4) + 3 can be written down like this in postfix notation with the advantage of no precedence rules and parentheses needed:

1 2 + 4 * 3 +

The expression is evaluated from the left to right using a stack:

  • push when encountering an operand and
  • pop two operands and evaluate the value when encountering an operation.
  • push the result

Like the following way (the Stack is displayed after Operation has taken place):

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Data structures and algorithms. OpenStax CNX. Jul 29, 2009 Download for free at http://cnx.org/content/col10765/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Data structures and algorithms' conversation and receive update notifications?

Ask