In your own words, describe the structure and function of both the stack and queue data structure and discuss how they are different from the perspective of how they are used.

ANS (Shaffer, C. 2011):

The stack is a first-in-last-out data structure. The queue is a first-in first-out data structure.

For example, there is a one-person wide path, which can only enter and exit from one side. The first person to go in is always the last to come out. This is the stack structure. On the other hand, a person who is queuing to board the plane comes first to board the plane first, and next one board the plane later. This is the queue data structure.

In computer science , you can use sequential storage (that is, array-based list) and non-sequential storage (that is，linked list) to store and implement these two data structures (stack and queque).

An array is a collection of elements of the same data type arranged in a certain order; the storage range of the array is continuous, and it takes up a lot of memory, so the space is very complicated. However, the binary search time complexity of the array is small, all are O(1). As for implementation of an array, there are following several characters: the query is simple, and it is difficult to add and delete.(Shaffer, C. ,2011)

Comparatively, a linked list is a non-contiguous, non-sequential storage structure on a physical storage unit, and the logical sequence of data elements is achieved through the link order of pointers in the linked list. The linked list is composed of a series of nodes, which can be dynamically generated at runtime. Compared with the linear table sequence structure, the operation is complicated. Because it does not have to be stored in order, the linked list can reach O(1) complexity when inserting. We can tell that it is much faster than another linear list sequence table in this side. However, it takes O(n) to find a node or access a node with a specific number. The time complexity of the linear table and sequence table are O(logn) and O(1) respectively.(Shaffer, C. ,2011)

Additionally, the storage interval of the linked list is discrete, and the memory is relatively loose, so the space complexity is small. Moreover, the time complexity is very large, which reaches O(N). Compared with arrays, its query function is difficult, and it is easy to add and delete.(Shaffer, C. ,2011)

Conclusion:

Arrays are suitable for situations in which data needs to be quickly queried, and operations of inserting and deleting elements are not common. On the contrary, it is better to choose a linked list storage structure when the timeliness requirements for accessing elements are not high, and elements need to be inserted and deleted frequently.

Reference:

Shaffer, C. (2011). A Practical Introduction to Data Structures and Algorithm Analysis.

490 words