# Data Structure Elements

(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?

© BrainMass Inc. brainmass.com October 9, 2019, 4:26 pm ad1c9bdddfhttps://brainmass.com/computer-science/arithmetic-and-logic-structures/data-structure-elements-32440

#### 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 ...

#### Solution Summary

The expert examines data structure elements for implementation.