CS 2201 Program Design & Data Structures Fall 2024 PDF

CS 2201 Program Design & Data Structures Fall 2024 Success Talent Hard work HW Projects Reading Lectures Announcements What you should do… Project #4 – due Monday, 10/14,...

CS 2201 Program Design & Data Structures Fall 2024 Success Talent Hard work HW Projects Reading Lectures Announcements What you should do… Project #4 – due Monday, 10/14, at 9pm Reading: zyBooks, Chap 5 ZY-4 – due Sunday, 10/06, at 11:59pm ZY-5 – due Sunday, 10/20, at 11:59pm Auxiliary Reading: Lafore, Chap 4 (optional) On your radar: Exam #2 on Wednesday, 10/9. We will discuss it next Anyone planning to take the final exam at SAO should schedule that exam now. Our final exam is Tuesday 12/10/24, 7-10pm. Schedule for 6:00- 10:30pm. Exam #2 Overview When: Wednesday, Oct 9, in class You will have 50 minutes. What topics will be covered? Everything since the beginning of class through today’s lecture (but not next Monday’s lecture) The focus will be on material since the first exam, i.e., lectures 10-19. This correlates to Chapters 3-4 in zyBooks, and introduction to Chapter 5. Topical list on next slide Exam #2 Learning Objectives All the stuff for exam #1 Big-O analysis Dynamic memory allocation, arrays vs. linked lists General linked list items: linking nodes, dot notation, traversing a list, inserting/deleting nodes, sorted vs. unsorted lists, edge conditions while processing lists Special list structures: tail pointers, circular linked lists, doubly linked lists The TweetMgr class of projects 1-3, the BigNum class of lecture Recursion: understanding/tracing/writing a recursive method, comparing recursion vs. iteration, divide-n-conquer, Quicksort – recommend that you get started on project #4 Basics of stacks Exam #2 Format Some short answer Multiple choice, fill-in-the-blank, T/F Some code tracing What does this print out? What’s wrong with this? How much work does this do? Some code writing Fill in the blank coding Short code segments (e.g., function header, etc.) Small methods You will not have a syntax reference sheet Keep Pushing Yourself… Here’s an email from a past student who took CS2201 online during COVID: Dr. Roth, I hope you're having a great weekend. My name is xxxxxx and I took your 2201 class spring semester 2021. I wanted to reach out and thank you. I'm trying not to sound too dramatic, but your class has really shifted my perception of myself. Since childhood, I was discouraged from taking STEM courses because I was a “humanities kid.” Even after taking CS1101 with Prof. Arena, I felt very hesitant about taking another CS course, especially one that my STEM-oriented friends said was pretty challenging. And they were right! Your class definitely challenged me; I had to watch your lectures several times (on 0.75 speed sometimes... hahaha), and I very often frequented TA office hours. As difficult as I found the content to be, your delivery of the content was so clear and effective that I was motivated to keep pushing and asking questions. As I kept trying and as the red underlines on CLion slowly faded on each PA, your class slowly opened something within me; not only an excitement to learn something new but also a realization that the label, “humanities kid,” is ridiculous and narrow- minded. This realization had large impacts on me and my path. It encouraged me to challenge myself to try things beyond the realm of what I perceived myself to be capable of, whether it be trying new hobbies, experiences, etc., all opening new opportunities for me. And now, as I am embarking on an uncertain transition from xxxxxxxxx to another career path, I frequently think of what I learned from your class to remind myself that with consistent work and persistence, I can achieve my goals. To summarize, thank you, Dr. Roth, you gave me an opportunity to feel excited about learning and taught me the value of challenging myself. I hope this email serves as a reminder that your impact on students is wide and large! Fact n=3 Fact(n – 1)= Box Trace Call Stack: Fact(3) return= Fact Fact n=3 n=2 Fact(n – 1)= Fact(n – 1)= return= return= Fact Fact Fact n=3 n=2 n=1 Fact(n – 1)= Fact(n – 1)= Fact(n – 1)= return= return= return= Fact Fact Fact Fact n=3 n=2 n=1 n=0 Fact(n – 1)= Fact(n – 1)= Fact(n – 1)= return= return= return= return=1 Fact Fact Fact Fact n=3 n=2 n=1 n=0 Fact(n – 1)= Fact(n – 1)= Fact(n – 1)= return= return= return= return=1 Fact Fact Fact n=3 n=2 n=1 Fact(n – 1)= Fact(n – 1)= Fact(n – 1)=1 return= return= return=1 Fact Fact n=3 n=2 Fact(n – 1)= Fact(n – 1)=1 return= return=2 Fact n=3 Fact(n – 1)=2 return=6 Stacks When we traced our recursive functions using a box trace, the boxes were added and deleted only one at a time. The box that was added last was the first one removed. This is known as a “call stack” Stacks A stack is a list in which we always add to one end and remove from the same end. This distinguished ‘end’ is known as the top of the stack Stacks are very common in CS. Compilers use stacks to maintain the execution of functions in a program. Undo command in an editor Backtracking in a maze or card game Stacks are LIFO data structures Last In First Out (e.g., stack of cafeteria trays) Stacks Let’s define a stack ADT (Abstract Data Type) Define the interface Design the implementation What kinds of operations do we want to do with our stack? Create a new empty stack Push (add an item) an item onto the stack Pop (remove an item) an item off the stack Retrieve the top item without popping it off Test if the stack is empty Retrieve the size of the stack Optional: display the entire stack (debugging) Brainstorm: Stacks Let’s write a Java program to see if all parentheses, braces, and brackets are properly nested and matched. Requirements: 1. Each time you encounter a closing struct, it matches the last unmatched open struct 2. When you reach the end of the file, all open structs have been matched. Brainstorm: Stacks Let’s write a Java program to see if all parentheses, braces, and brackets are properly nested and matched. Requirements: 1. Each time you encounter a closing struct, it matches the last unmatched open struct 2. When you reach the end of the file, all open structs have been matched. Examples of balanced (“properly nested and matched”) delimiters {a} balanced {a not balanced [d]() balanced [ d}() not balanced {({}[])[]} balanced {({}[])[]] not balanced ( [ [ [ ] ( { } ) ] { } ] ) { { } } balanced ( [ [ [ ] ( { } ) ] { } not balanced {(a{}[])[b]} balanced { ( a { } [ ] ) [b ] ] not balanced Brainstorm: Stacks Let’s write a Java program to see if all parentheses, braces, and brackets are properly nested and matched. Requirements: 1. Each time you encounter a closing struct, it matches the last unmatched open struct 2. When you reach the end of the file, all open structs have been matched. Approach: Each time we see an open struct, we push it onto the stack. Each time we see a closing struct, we make sure it matches the top of the stack. FileReader inputStream = new FileReader("example.txt"); int c; Example: Stacks CharStack stk = new CharStack(); – First Pseudo-Draft while ((c = inputStream.read()) != -1) { // while not end of file char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { // opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol verify(stk.top(), ch); // verify ch is correct closing symbol // if ch == ')' then stk.top should equal '(' // ditto for '}' and '{', and ']' and '[' stk.pop(); // remove matched symbol from stack } // ignore all other chars If verify(stk.top(), ch) returns false } // end while at any point, indicate NOT balanced Example: Stacks – First Draft First draft: what things did we not think about? 1. What if we try to look at something on the stack but the stack is empty? 2. What if we hit end of file and there are still some items left on the stack Let’s try a second draft… FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { System.out.println("File does not have balanced symbols"); } Example: Stacks – verify() public static boolean verify(char open, char close) { return ((open == '(' && close == ')') || (open == '[' && close == ']') || (open == '{' && close == '}')); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { true balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { [ System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { ( System.out.println("File has balanced symbols"); } else { [ System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { ( System.out.println("File has balanced symbols"); } else { [ System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { true balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { ( System.out.println("File has balanced symbols"); } else { [ System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { [ System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { true balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { [ System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)] // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; What if this is our input? while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { false balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } {a}[( b)} // ignore all other chars } // end while if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { [ System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } // ignore all other chars Q: Find test inputs that would } // end while exercise the highlighted code if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { System.out.println("File does not have balanced symbols"); } FileReader inputStream = new FileReader("example.txt"); int c; CharStack stk = new CharStack(); boolean balanced = true; while (balanced && (c = inputStream.read()) != -1) { char ch = (char) c; if ((ch == '(') || (ch == '{') || (ch == '[')) { //opening symbol stk.push(ch); // push onto stack } else if ((ch == ')') || (ch == '}') || (ch == ']')) { //closing symbol if (stk.isEmpty()) { // no matching symbol balanced = false; } else { balanced = verify(stk.top(), ch); // verify correct stk.pop(); // remove matched symbol from stack } } // ignore all other chars Q: Find test inputs that would } // end while exercise the highlighted code if (balanced && stk.empty()) { System.out.println("File has balanced symbols"); } else { System.out.println("File does not have balanced symbols"); } Stacks: Implementation Options Given that the idea of maintaining a stack can be useful, what are the options for implementing a stack? It should allow us… Create a new empty stack Push (add an item) an item onto the stack Pop (remove an item) an item off the stack Retrieve the top item without popping it off Test if the stack is empty Retrieve the size of the stack Optional: display the entire stack (debugging) Stacks: Implementation Options Array implementation Linked list implementation Stacks: Array Implementation How should we store the stack data in an array? Which end is the “top”? If the top-of-stack is at position 0, then we need to… Shift data up to a higher index on a push() to make room for the new item. Shift data down to a lower index on a pop() to remove the element. Push(a) Push(b) Push(c) a a b a b c TopHat Q! Stacks: Array Implementation How should we store the stack data in an array? Which end is the “top”? If the top-of-stack is at position 0, then we need to… Shift data up to a higher index on a push() to make room for the new item. Shift data down to a lower index on a pop() to remove the element. Push(a) Push(b) Push(c) a a b a b c The Big-O of push & pop is O(N) Stacks: Array Implementation How should we store the stack data in an array? Which end is the “top”? If the top-of-stack is at position 0, then we need to… Shift data up to a higher index on a push() to make room for the new item. Shift data down to a lower index on a pop() to remove the element. What if the stack grows at the other end of the array? Does it matter if the top is always a certain location? Can we just keep track of “where” the top of the stack is currently located? Even better…maybe the top should point to the next open position. Then it not only helps us find the top of the stack, but it also represents how many items are in the stack. Stacks: Array Implementation Push(a) Push(b) Push(c) c b b a a a What if the stack grows at the other end of the array? Does it matter if the top is always a certain location? Can we just keep track of “where” the top of the stack is currently located? Even better…maybe the top should point to the next open position. Then it not only helps us find the top of the stack, but it also represents how many items are in the stack. The Big-O of push & pop is O(1)