This approach has the upside that we always know where the top element is - it'll always be in cell 0, no matter what. We'd presumably also need to keep track of how many elements were stored (necessary if we had an array, done automatically by std::vector if we use it). If we store the elements in top-to-bottom order, that means the top of the stack would always be stored in cell 0 of the array, the element just beneath the top would be stored in cell 1, and so on. It seems sensible that we'd want to store the elements in the order in which they appear in the stack, though an open question is whether they should be stored in top-to-bottom or bottom-to-top order. Let's first consider how you might implement a stack using an array-based data structure, such as an array or a std::vector. Implementing a stack using an array or std::vector There are two obvious choices: an array (or an array-based structure, like a std::vector) and a linked list. If we have a stack-shaped problem and we need to implement one, we have a sequence of elements to store our first order of business is choosing an underlying data structure in which to store them. In a practical implementation, you might find other operations, like one that tells you how many elements are in the stack, or one that tells you whether the stack is empty, but push, pop, and top are the most important ones, so we'll focus on those.
The common operation pop removes an element from the top.The common operation push adds a new element to the top.The most important element is the one on top.The diagram shows the most important conceptual ideas underlying stacks: If we were to draw a diagram of a stack, which focused on the key concepts, it might look something like this: To get our minds around this kind of analysis, let's consider a few of the classic linear data structures, which let you store and manipulate sequences of elements, with the understanding that certain ones, at any given time, are more important than the others.Ī stack is a data structure that stores a sequence of elements, with the key property being that the most important one, at any given time, is the one that was stored the most recently. If we can get a handle on all of those issues, we'll have a good understanding of when our new data structure might solve a real problem we have, as well as how we should build it (if our preferred programming language doesn't provide one), and how well it will perform in the ways that we plan to use it. How well would the implementation of the common operations work? We should do some analysis (e.g., asymptotic analysis) of our implementation choices, to be sure that we've made good ones, and to be able to compare different implementations, so we can select one that performs well enough for our needs.How would the implementation of the common operations actually work? If you need to store data in memory, for example, how would you organize it, and how would you find and manipulate it as it changes?.What are the common operations (i.e., the things that any reasonable implementation of the data structure would provide), and what do they do, from a conceptual perspective?.What kinds of problems is it intended to solve? What does it look like, from a conceptual perspective?.Generally, then, when we learn about a new data structure we've not seen before, there are a few things we want to understand about it: If you want to keep track of information about students, each indexed uniquely by an ID, in C++, you might choose a std::map, with the keys being the IDs and the values being objects of a Student class. If you want to store a sequence of values in Python, a list is a good choice. None of these is definitively better than any of the others the objective is to choose the data structure that best matches the "shape" of the problem you're trying to solve. Python, meanwhile, provides choices like lists, sets, tuples, and dictionaries. For example, C++ provides a number of data structures: arrays, std::vector, std::list, and std::map, to name a few. In previous coursework, you've no doubt used at least one programming language - C++ or something else - enough that you've been exposed to the data structures that are provided by the language or its standard library.
0 kommentar(er)
