Data Structure Elements
Not what you're looking for?
(a) Describe and illustrate how elements are normally added and removed from an efficient
implementation of the stack ADT, as defined in class, which is implemented using linked
lists.
(b) A stack is used to evaluate the following postfix expression. Show the state of the stack after
the minus sign is processed and its state after the multiplication sign is processed.
3 5 3 + 4 + - 6 *
(c) An array can be used to hold a complete or full binary tree. Explain how this data structure
would be set up and how a node's left and right children could be reached. What changes
would be needed if there was a requirement to handle non-full, non-complete binary trees?
Can you please explain these?
Purchase this Solution
Solution Summary
The expert examines data structure elements for implementation.
Solution Preview
(a) Describe and illustrate how elements are normally added and removed from an efficient implementation of the stack ADT, as defined in class, which is implemented using linked lists.
A stack is a last-in/first-out (LIFO) structure for containing data. This means that when data is retrieved from the stack, the packet of data most recently put into the stack is the first one that will be retrieved. The next oldest will be the next to be retrieved, etc. Putting data into a stack is commonly referred to as pushing data onto the stack. Retrieving data from a stack is commonly referred to as popping data from the stack. Popping data from a stack physically removes it from the stack. A given data item can only be popped once unless it is pushed it back onto the stack.
A linked-list is commonly thought of as a data structure consisting of one or more nodes, deposited somewhere in memory, with links connecting each node to the next node. Sometimes, links are also provided to connect each node to the previous node. This is a structure as something like a string of beads where each bead contains some data, and they are linked together by the string. However, the physical locations of the nodes in memory may be very haphazard and not nearly as neat as the physical arrangement of a typical string of beads.
A linked-list is a reasonably good structure for implementing a stack. To implement a stack with a ...
Purchase this Solution
Free BrainMass Quizzes
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.
Excel Introductory Quiz
This quiz tests your knowledge of basics of MS-Excel.
Word 2010: Table of Contents
Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.
Basic UNIX commands
Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.