A-level Computing 2009/AQA/Problem Solving, Programming, Operating Systems, Databases and Networking/Programming Concepts/Stacks

Abstract data types and data structures 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: center 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) 150px|rightLet'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 1 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 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 Pop Pop Push 'Sand' Push 'Witches' If we have an empty Stack what do we set the pointer TopOfStack to? 0 or null Describe the Stack data type: A stack is a First In Last Out or Last In First Out data type Give two uses for a Stack in a computer: 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()