Programming Concepts: Stacks

From Wikibooks, open books for an open world
Jump to: navigation, search

UNIT 3 - ⇑ Programming Concepts ⇑

← Abstract data types and data structures Stacks Queues →


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:

CPT-ADT-stacks-real-life.svg
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)
Data stack.svg

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:

  1. Push 'Annabelle'
  2. Push 'Chris'
  3. Push 'Hemingway'
  4. Push 'James'
  5. Pop
  6. Pop
  7. Pop
  8. 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 :

  1. Pop
  2. Pop
  3. Push 'Sand'
  4. 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()