Programming Concepts: Stacks

A stack is an ADT that might involve a dynamic or static implementation. A stack is a last-in-first-out (LIFO) or first-in-last-out (FILO) ADT. Implementations should include two operations, pushing and popping, and a pointer to the top of the stack.

A real life example is a stack of books you might have on your desk:

In this example we keep adding (pushing) books to the stack. If we want to get at the bottom book about Cars, we must first remove (pop) all the books above it. Hence First In Last Out (FILO)

Let's take a look at a computer implementation of a stack:

• Pushing: Adds a new specified item to the top of the stack
• Popping: Removes the item from the top of the stack.

State 1	State 2	State 3	State 4	State 5
Push 'elephant'	Push 'hippo'	Push 'zebra'	Pop	Push 'flamingo'
memloc data TopOfStack 4 3 2 1 elephant <--	memloc data TopOfStack 4 3 2 hippo <-- 1 elephant	memloc data TopOfStack 4 3 zebra <-- 2 hippo 1 elephant	memloc data TopOfStack 4 3 zebra 2 hippo <-- 1 elephant Note the data isn't 'deleted' The TopOfStack pointer moves to show it is no longer in the stack	memloc data TopOfStack 4 3 flamingo <-- 2 hippo 1 elephant

Stacks have several uses:

• Reversing queues (as seen above with the Alphabetised names)
• Performing Reverse Polish Calculations (see ....)
• Holding return addresses and system states for recursive function calls

Exercise: Stacks Draw the stack after each of the following commands, starting with an empty stack. What does the stack achieve: Push 'Annabelle' Push 'Chris' Push 'Hemingway' Push 'James' Pop Pop Pop Pop Answer: Command 1 Command 2 Command 3 Command 4 memloc data TopOfStack 4 3 2 1 Annabelle <-- memloc data TopOfStack 4 3 2 Chris <-- 1 Annabelle memloc data TopOfStack 4 3 Hemingway <-- 2 Chris 1 Annabelle memloc data TopOfStack 4 James <-- 3 Hemingway 2 Chris 1 Annabelle Command 5 Command 6 Command 7 Command 8 memloc data TopOfStack 4 James 3 Hemingway <-- 2 Chris 1 Annabelle Output: James memloc data TopOfStack 4 James 3 Hemingway 2 Chris <-- 1 Annabelle Output: Hemingway memloc data TopOfStack 4 James 3 Hemingway 2 Chris 1 Annabelle <-- Output: Chris memloc data TopOfStack 4 James 3 Hemingway 2 Chris 1 Annabelle Output: Annabelle Top of Stack = 0 The stack is empty This set of instructions used the stack to input data in order and then output it in reverse order Give the set of instructions required to get from State 1 to State 2 as shown below: State 1 State 2 memloc data TopOfStack 4 3 Sharks <-- 2 Chalk 1 Cheese memloc data TopOfStack 4 3 Witches <-- 2 Sand 1 Cheese Answer: Pop Pop Push 'Sand' Push 'Witches' If we have an empty Stack what do we set the pointer TopOfStack to? Answer: 0 or null Describe the Stack data type: Answer: A stack is a First In Last Out or Last In First Out data type Give two uses for a Stack in a computer: Answer: Reversing queues (as seen above with the Alphabetised names) Performing Reverse Polish Calculations (see ....) Holding return addresses of recursive function calls

Dim myStack(10) as string
Dim ToS as integer = 0 'this is our pointer
Dim item as string

While item <> “#”
  Console.writeline(“please insert item ” & ToS & “ into the stack: ”)
  item = Console.readline()
  myStack(ToS) = item
  ToS = ToS + 1
End While

For x = ToS to 0 step -1
  Console.writeline(“Stack item: ” & x & “ = ”  & myStack(x) )
Next

console.readline()