Skip to content

DA3. Stack and Queue

Statement

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.

Solution

Similarities

  • Stacks and Queues are both data structures that allow users to store and retrieve a collection of data in a specific order.
  • The word collection here indicates multiple data items or objects, and not related to the Collection class in Java.
  • The closest definition of Stacks and Queues that are List-like data structures (Shaffer, 2011).
  • Both allow for basic operation such as insert, remove, clear, size or length with each of them having their own specific implementation and own rules for how the data is stored and retrieved (Barnett & Del Tongo, 2008).
  • Both differ from list that they do not allow random access or random insertion of data (insertion at any index).
  • Both can be implemented using an array or a linked list.
  • Both are very efficient data structures to the extends that they are used in building the core functions of all operating systems (Barnett & Del Tongo, 2008).
  • Both Array-Based and Linked-List-Based implementations of Stacks are very efficient in terms of time complexity for almost all operations which is O(1) in good implementation (Shaffer, 2011), however, Array-Based stacks are slightly more storage efficient if the number of items known in advance (Barnett & Del Tongo, 2008).

Stacks

  • Stacks are a data structure that follows the LIFO (Last In First Out) principle.
  • Stacks retrieve data in the reverse order of how they were inserted.
  • Stacks allow inserting and removing data from one end only, which is the top of the stack.
  • Stacks have special names for inserting and removing data, push and pop respectively.
  • Stack are very helpful in building recursive algorithms (Shaffer, 2011).

Queues

  • Queues are a data structure that follows the FIFO (First In First Out) principle.
  • Queues retrieve data in the same order of how they were inserted.
  • Queues allow inserting and removing data from two ends, which are the front and rear of the queue.
  • Queues have special names for inserting and removing data, enqueue and dequeue respectively (Barnett & Del Tongo, 2008).
  • Items are inserted (enqueued) at the rear of the queue and removed (dequeued) from the front of the queue.
  • Queues are the base for more advanced data structures such as priority queues and double-ended queues (Barnett & Del Tongo, 2008).

References

  • Shaffer, C. (2011). A Practical Introduction to Data Structures and Algorithm Analysis. Blacksburg: Virginia. Tech. https://people.cs.vt.edu/shaffer/Book/JAVA3e20130328.pdf. Chapter 4.
  • Barnett, G. & Del Tongo, L. (2008). Data Structures and Algorithms: An Annotated Reference with Examples. Chapter 6: Queues.